1.4 启发式搜索
启发式搜索算法是在搜索时利用问题定义本身之外的知识来引导搜索的算法。启发式搜索算法依赖于启发式代价函数h，其定义为每个节点到达目标节点代价的估计值。启发式搜索算法通过代价函数h的估计获得一种搜索策略。当代价函数的估计值比较精准的时候，该算法往往能较快地找到目标节点。相比于盲目搜索，启发式搜索能够减少搜索范围，提高搜索效率。
启发函数需要根据具体问题设计。例如在图1.9的搜索例子中，一个启发函数可以是当前城市到台北的直线距离。设计启发函数是启发式搜索的核心。如果启发函数带来的信息过弱，搜索算法在找到一条路径之前将扩展过多的节点，则无法有效地降低算法的复杂度；反之，如果启发函数引入的启发信息过强，虽然能大大降低搜索工作量，但可能导致无法找到最佳路径。因此，在实际应用中，往往希望能引入适量启发信息以降低搜索工作量，同时不牺牲找到最佳路径的保证。
下面将介绍两种启发式搜索方法，贪婪搜索（Greedy Search）和A*图搜索算法（A* Graph-Search，简称A*算法）。我们沿用图1.9所示的例子，搜索从乌鲁木齐（A）到台北（T）的最短路径。
1.4.1 贪婪搜索
在贪婪搜索中，总是优先扩展可达节点中启发函数最小的节点，以期望能尽快到达目标。在图1.3的例子中，最理想的h函数为当前节点至目标节点的真实旅行距离。但在实践中，如此理想的启发式函数很难得到，我们往往只能通过经验估计一个启发函数。当启发函数不准确时，可能无法得到问题的最优解。例如，若取h为图1.9中给出的评估函数，则贪婪搜索扩展节点的顺序为A→X→B→T。
图1.9 带有启发函数的地图路径搜索问题
在这个情况下，贪婪搜索无需任何的回溯就到达了目标节点。因此算法的时间复杂度很低。然而，算法找到的并不是最优路径，A→X→C→W→T是一条更优的路径。这是由评估函数不精确导致的。从这个例子也可以看出算法的“贪婪”性，即算法每一步都仅考虑启发式函数估计离目标最近的节点，而没有考虑从起始节点到该节点的已知真实损耗。
贪婪搜索的伪代码如下：
算法3：贪婪搜索
下面将以图1.9中的例子具体说明贪婪搜索算法的执行过程。为了简化说明，后继节点集合N只显示不在访问表V中的节点。假设初始节点为A，目标节点为T。
初始化时，优先队列为空Q={}，访问表为空V={}。然后算法执行过程如下：
（1）初始节点A放入优先队列Q，Q={A}。
（2）优先队列Q不为空，继续执行。弹出优先队列中h值最小的节点A，且A不是目标、不在访问表中。扩展A，其后继集合为N={X}。将A放入访问表得到V={A}。将N中的节点放入优先队列得到Q={X}。对应图1.10（1）。
（3）优先队列Q不为空，继续执行。弹出优先队列中h值最小的节点X，且X不是目标、不在访问表中。扩展X，其后继集合为N={B，C}。将X放入访问表得到V={A，X}。将N中的节点放入优先队列得到Q={B，C}。对应图1.10（2）。
（4）优先队列Q不为空，继续执行。弹出优先队列中h值最小的节点B，且B不是目标、不在访问表中。扩展B，其后继集合为N={T，W，S}。将B放入访问表得到V={A，X，B}。将N中的节点放入优先队列得到Q={T，W，S，C}。对应图1.10（3）。
（5）优先队列Q不为空，继续执行。弹出优先队列中h值最小的节点T，且T是目标。结束搜索，返回成功。对应图1.10（4）。
对应该问题的搜索过程，如图1.10所示。
图1.10 贪婪搜索节点的扩展顺序
1.4.2 A*算法
A*算法是启发式搜索算法中最广为人知的算法。其在解决路径搜索相关问题中应用十分广泛，包括网络路由算法、机器人探路、游戏设计以及地理信息系统的交通路线导航和路径分析领域。
相比贪婪搜索，A*算法采用更为精确的评价函数对扩展节点进行评估，因为其评价函数不仅利用启发函数，而且还包含从起始节点到目前节点的已知真实损耗。令g（n）表示算法所找到的从起始节点s到节点n的实际代价；令h（n）表示启发函数，它定义从当前节点到目标节点最佳路径的代价估计；然后令f（n）=g（n）+h（n）表示评价函数。相对的，贪婪搜索采用f（n）=h（n）。实际代价g（n）可以在搜索中计算得到，即g（n）=g（p）+c（p，a，n），其中g（p）为起始节点到父节点p的实际代价，而c（p，a，n）是父节点p通过动作a转移到节点n的代价。
A*算法的实现需要两个列表，一个是优先队列表，一个是访问表。优先队列表是一个以节点的f函数为升序排列的优先列表，其目的是为每一次搜索提供经验上“最优”的节点，以帮助A*算法更有效率地找到从起点到终点的最短路径。访问表是一个普通的列表，用来保存已经扩展过且无需再访问的节点，以避免节点的重复访问。
A*算法的伪代码如下：
算法4：A*算法
下面以图1.9中的问题为例，说明A*算法的执行过程。同样取图1.9中的启发代价函数h，并假设初始节点为A，目标节点为T。与之前介绍的算法一样，A*算法在搜索过程中也能产生一棵搜索树。我们在图1.11中展示了A*算法在执行中产生的搜索过程。为了简化说明，后继节点集合N只显示不在访问表中的后继节点。
初始化时，优先队列为空Q={}，访问表V={}。然后算法执行过程如下：
（1）将初始节点A放入优先队列得到Q={A}。
（2）优先队列Q不为空，继续执行。弹出优先队列中f值最小的节点A，且A不是目标、不在访问表中。扩展A，其后继集合为{X}。将A放入访问表得到V={A}。将后继集合中的节点放入优先队列得到V={X}。对应图1.11（1）。
（3）优先队列Q不为空，继续执行。弹出优先队列中f值最小的节点X，且X不是目标、不在访问表中。扩展X，其后继集合为{B，C}。将X放入访问表得到V={A，X}。将后继集合中的节点放入优先队列得到Q={B，C}。对应图1.11（2）。
（4）优先队列Q不为空，继续执行。弹出优先队列中h值最小的节点C，且C不是目标、不在访问表中。扩展C，其后继集合为{L，W}。将C放入访问表得到V={A，X，C}。将后继集合中的节点放入优先队列得到Q={W，B，L}。对应图1.11（3）。
（5）优先队列Q不为空，继续执行。弹出优先队列中f值最小的节点W，且W不是目标、不在访问表中。扩展W，其后继集合为{T，K}。将W放入访问表V={A，X，C，W}。将后继集合中的节点放入优先队列Q={T，B，K，L}。对应图1.11（4）。
（6）优先队列Q不为空，继续执行。弹出优先队列中f值最小的节点T，且T是目标。结束搜索，返回成功。对应图1.11（5）。
A*算法的最优性：A*算法在一定的条件下能保证其返回的解是最优的。保证A*算法最优性的一个条件是h（n）是一个一致性启发函数（也称单调性启发函数）。其具体定义如下：如果对所有节点ni和nj，其中nj是ni的后继节点，函数h（n）均满足
图1.11 A*算法在地图搜索问题上产生的搜索树
其中，c（ni，a，nj）表示的是执行动作a从ni到nj的单步代价，G为最近的目标节点，则称h（n）为一致性启发函数。启发函数的一致性可以用图1.12中的三角不等式形象地表示出来。
图1.12 启发函数一致性的形象表示
如前所述，A*算法有如下性质。
定理：如果h（n）是一致的，那么A*算法找到的解是最优的。
证明：
第一步，需要证明如果h（n）是一致的，那么沿着任何路径上的节点f（n）值是非递减的。这步证明可以用一致性的定义得到。具体来说，假设nj是ni的后继节点，那么g（nj）=g（ni）+c（ni，a，nj），其中a是ni到nj的动作。然后可以得到
f（nj）=g（nj）+h（nj）=g（ni）+c（ni，a，nj）+h（nj）≥g（ni）+h（ni）
第二步，需要证明当A*算法选择扩展节点ni时，到达节点ni的最优路径已经找到。这一步可以用反证法。假设到达节点ni的最优路径还没有找到，那么在这个最优路径上必然有一个没有扩展开的节点
在优先队列表里。因为沿着任何路径上的节点的f（n）值是非递减的，那么
，
必然会先于ni扩展，这个与假设矛盾。
从以上两步证明可以得出，A*算法以f（n）值的非递减顺序扩展节点。因为目标节点的h=0，f在目标节点的值就是实际总损耗。因此第一个被选择扩展的目标节点的路径一定是最优解。