启发式算法在计算机程序搜索中的简单应用

李晓宇　秦文杰

摘 要：对于不能直接计算求解的问题，往往需要搜索算法在解空间中寻找最优解或更优解。为了高效地搜索，加入了启发式算法，让机器程序像人一样作出更优的决策。阐述了启发式算法中的作用原理，介绍了启发式算法与搜索的联系，讲解了启发式算法在计算机程序搜索中的简单应用的案例，对比分析了启发式算法与普通宽度优先搜索或深度优先搜索算法的优势与不足。

关键词：启发式算法，解空间，搜索，更优解，估价函数

0、引言 搜索是用计算机解决问题时常用的算法策略。但往往相对于要求的最优解或次优解而言，解空间很大。直接简单地运用搜索解决问题，往往会花费大量的时间，因为无用的搜索方向或问题状态相对目标解来说太多。在已知目标状态或如何衡量待求解的优劣时，利用减枝技巧可以避免搜索部分无用解空间，但是计算机搜索仍然会试探一些无用的解空间。启发式算法可以估计当前状态到目标状态的代价，从而作出好的策略，帮助机器像人一样聪明地向更优解目标方向搜索。

1、启发式算法的作用原理

启发式算法是根据机器计算当前状态到目标状态的所有可能性或所需花费，从中选出到达目标状态可能性最高的或者花费最少的下一步。就这样不断地计算概率花费，不断迭代优化更优解，进而得到更优解或者最优解。计算机程序可能并不会准确地计算出到达目标解的代价，但是可以利用数学计算进行估计。若要得估价接近实际花费，就得设计好评价函数。这也是启发性的关键。

2、启发式算法应用在搜索中

机械的搜索算法会浪费大量时间等计算机资源在无用状态转换上。若要让计算机程式像人拥有感觉作出合理的判断，就是给程序使用启发式算法了。让机器智能地搜索下一个状态。本科期间常见或用到的启发式算法有A*算法，遗传算法，蚁群算法，BP神经网络等。BP神经网络可用于仿真机器人学习上，在大学上机器人竞赛中常用。让机器人不断地学习，修改参数，作出更优的策略。A*算法可用于ACM大学生程序设计竞赛中，比较容易实现，常用于搜索。

3、启发式算法应用于搜索中的案例

3.1 计算机软件能力认证-游戏[3]

题目转述：在N行M列的棋盘上，计算玩家从左上角移动到右下角所需的最少时间，期间某些位置在一段连续时间不能移动到（危险）。详细描述请参照原题[3]。

分析：这是一道棋盘搜索题，求解最短时间。很容易想到宽度优先搜索，可以利用三维数组来表示棋盘状态（根据数组在内存中是线性存储的，所以也可以将三维数组转化为一维。但是内存消耗是一样的，所以没有必要转化。三维数组的维度分别表示位置横坐标，纵坐标，时间戳）。直接宽度优先搜索可以解决改问题，只是搜索了大量的无用的棋盘状态，效率不高。

虽然可以在该题时间限制内解决问题，但是若用了A*算法，加入启发式思想。从当前搜索过的状态中选择到目标状态的曼哈顿距离最小的位置状态开始搜索，因为玩家每秒都要移动，所以曼哈顿距离越小的状态到达目标的用时最少。在保证结果正确的前提下，提高了解决问题的效率。

给出估价函数：

从当前状态（x， y）到目标状态（m， n）的估价函数 h = abs（x - m） + abs（y - n），即當前位置到目标位置的曼哈顿距离。

初始状态到当前状态的实际代价：每移动一次，该代价g 加1。

初始状态经当前状态到达目标状态的估价：f = h + g。

实际测试用时比较：普通BFS[4]用时109ms， 启发式算法A*算法[5]用时62ms。可见启发式算法有方向地搜索比较省时。

具体算法实现见附解（参考文献）。北大测评系统1077也可用A*算法解答。

3.2 启发式算法在机器人中的应用

在大学生机器人竞赛中，在对机器人进行策略安排时，有的同学是把机器人场地进行划分，对每个机器人都设计一套策略。根据不同的局面状态，调整机器人的策略。总的来说就是判断判断再判断，根据判断作出反应。这样直接的判断状态的策略，机器人下一步该怎样做，设计者可以预测个大概。这并不能说是人工智能。机器人缺少随机应变的启发性决策。

西北工业大学的机器人配合得很好，很好地根据对手机器人的动作作出适当的改变。若不加入启发性算法、机器学习，很难得到好的策略。

利用BP神经网络，让机器人自主学习，不断地修改参数，做到更优。蚁群算法，模拟自然界中蚂蚁寻找食物，在路上留下信息素。信息素在一段时间内逐渐消散。其他蚂蚁可以根据信息素的分布情况作出相应的动作。可以运用到11V11机器人轮式足球比赛上面。

其他启发式算法，例如遗传算法等也常用到机器人策略编写上。

4、启发式搜索与普通宽度优先搜索的比较

启发式搜索每次有向着更接近目标解的状态搜索，避免了大量无效解空间的试探。如案例1测试结构，启发式搜索提高了解决问题的效率。

普通宽度优先搜索相对来说比较容易实现，若对时间要求不是很严格，BFS编写简单，搜索策略更易理解。而应用启发式搜索时需要使用数据结构优先队列，需要重载运算符。

应用启发式搜索时，需要注意评价函数的选择，这个直接关系着搜索的效率。估价函数不是一成不变的，不同的问题需要设计不同的估价函数。

5、总结

启发式算法应用到搜索策略中，可以避免不必要的搜索，大大减小了解空间。程序一直向着有希望的方向搜索，在一定程度上可以解决状态空间爆炸式增加的现象。解决不同的问题，往往需要不同的估价函数。在机器人策略实现方便，利用启发式算法不断地尝试学习，不断地修改参数，可以使得机器人做出更好的策略。

注解：

[1] 李晓宇 郑州大学信息工程学院老师

[2] 秦文杰 郑州大学信息工程学院软件工程系2015级2班的一个学生，学号20152480225

[3] 计算机软件能机认证试题CCF CSP 201604-4 游戏，原题链接（需要登录）

http：//118.190.20.162/view.page？gpid=T39

[4] 普通BFS解法

https：//github.com/zzuwenjie/coding18/blob/master/OJ/CCFCSP201604_4_BFS.cpp

[5] 启发式算法A*算法解法

https：//github.com/zzuwenjie/coding18/blob/master/OJ/CCFCSP201604_4_Astar.cpp