人工智能-搜索----启发式搜索

article/2025/10/24 2:42:12

搜索算法的形式化描述：

<状态state、动作motion、状态转移state transition、路径path、测试目标test target>

一、启发式搜索(有信息搜索)（Heuristic Search）

代表算法：贪婪最佳优先搜索（Greedy best-first search）、A*搜索

启发式搜索需要有：

1、辅助信息，也就是与求解问题相关的额外信息，就跟做数学题时的已知条件一样，根据已知条件求解。

2、评价函数（evaluation function）f(n)，从当前节点n出发，根据评价函数来选择后续节点。

3、启发函数（heuristic function）h(n),计算从节点n到目标节点所形成路径的最小代价值。

例如下图所示的一个城市路线图，要求搜索目标为找到一条从Arad-->Buchareat的最短路径

辅助信息：任意一个城市与Bucharest的直线距离

利用GBFS算法：

f(n)=h(n)：下一个节点=当前节点到目标节点为最小代价的节点

过程：从起始状态（start state）Arad根据辅助信息寻找下一个可能成为最短路径的城市，也就是寻找与Arad相邻的城市中与Buchareat的直线距离最短的那个城市作为下一个状态（state），也就是Sibiu,依次往下寻找，最后找到最短路径：

Arad-->Sibu-->Fagaras-->Bucharest

因为这个搜索过程每次在确定下一个候选节点的时候，总是选择那个到达目标城市直线距离最短的节点，所以称其为贪婪最佳优先搜索。但是通过结果我们可以发现，算法得到的路线Arad-->Sibu-->Fagaras-->Bucharest比Arad-->Rimnicu Vilcea-->Pitesti-->Bucharest路线还多出32公里，因此GBFS算法不是最优的，而且也是不完备的。因为它可能沿着一条无限路径走下去而不回来做其他尝试，距离目标节点直线距离最近的节点组成的路径不可能都是最短路径，这种搜索算法得到的实际路线可能会绕路，或者根本到达不了目标节点。比如，搜索从Iasi-->Fagaras的最短路径，根据GBFS算法由启发式建议需先扩展Neamt，这样就形成了一条死循环路径。最坏的情况下，GBFS算法的时间复杂度和空间复杂度都是O(b^m)，其中b是节点的分支因子数目，m是搜索空间的最大深度。因此，需要设计一个良好的启发式函数（Heuristic Function）。

为了解决GBFS算法的不足，A*算法被提出。

下面我们介绍一下A*算法：

评价函数：f(n)=g(n)+h(n)

其中，g(n) 表示从起始节点到节点n的开销代价值，

h(n) 表示从节点n到目标节点路径中所估算的最小开销代价值，

f(n) 视为经过节点n、具有最小开销代价值的路径。

为了保证A*算法是最优(optimal),需要启发函数 h(n) 是可容的（admissible heuristic）和一致的（consistency,或者也称单调性，即 monotonicity）

算法过程;

以上我们可以得出A*算法是最优的，其保持最优的条件就是启发函数具有可溶性（admissible）和一致性 (aconsistency)。

上述将直线距离作为启发函数h(n),则启发函数一定是可容的，因为直线距离最短，不会高估开销代价。

g(n) 是从起始节点到节点n的实际代价开销，且f(n) = g(n) + h(n),因为g(n)是确定的，我们预估的是h(n),h(n)是不会高估开销代价的，因此f(n)不会高估经过节点n路径的实际开销。

一致性条件：h(n) <= c(n,a,n')+h(n')构成了三角不等式。这里节点n、节点n'和目标节点Gn之间组成了一个三角形。如果存在一条经过节点n',从节点n到目标节点Gn的路径，其代价开销小于h(n),则破坏了h(n)是从节点n到目标节点Gn所形成的具有最小开销代价的路径这一定义。