再上一篇: 第 2 章  启发式搜索方法
上一篇:2. 2  启发函数
主页
下一篇:2. 4  习题
再下一篇: 第 3 章  霍普费尔德神经网络
文章列表

2. 3  * 搜索算法

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

A

定义2.8  A算法在启发函数h(n)满足

h(n) ≤h* (n),对所有节点n (2.4)的条件下被称为 * 算法。

A

这也就是说A* 算法的启发函数值永远低估了实际最小代价。A* 算法的重要意义在于,当 * 算法结束时,它一定已经找到了一条从起始节点到目标节点的最小代价路径。

A

关于 * 算法的完整理论推导可参见文献[26]、[118]和[127]。这一节综述其中一些主要

A

结论。

结论2.1  若存在从起始节点到目标节点的路径,A* 算法一定会终止。

结论2.2  A* 算法是可容(许)的。也就是说,如果存在一条从起始节点到目标节点的路径, * 算法以发现最优解而终止。

A

结论2.1表明,如果存在从起始节点到目标节点的解答路径,A* 算法一定能找到它。结论2.2更进一步指出,A* 算法找到的解答路径一定具有从起始节点到目标节点的最小代价。

作为一个例子,在这里我们用 * 算法解决以图2.8中起始节点 和终止节点 所给

A s g出的8数码问题。

2 8 3 1 2 3

s= 1 6 4 g= 8 4

7 5 7 6 5

图2.8  8数码问题的起始布局和目标布局

在从一个布局转换为另一个布局时,付出的代价是一步移动。我们要找出的是从s到g 的最少移动步数走法。正如在前一节中所讨论过的,我们以Misplaced(n)亦即不在目标布局给出的位置上的离家将牌数为启发函数。图2.9示出了 * 算法展开的节点及相应

A

的f(n)计算值。在展开了6个节点后,到达终止节点。

图2.9中,九宫格左侧的黑体数码表示节点展开的顺序,右侧的数码则是该节点的f值。最小代价路径由加重的连线表示。

虽然A* 算法保证可以发现最优解,但它的性能与启发函数的选择有很大关系。如果启发函数严重低估实际的 * ,算法退化为宽度优先搜索。如果问题规模较大,对用于保存

h

搜索图和解树的资源要求也就相当高。

#第12页-

图2.9  8数码问题的结果