姓名

年级

指导老师

日期

实验目 熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用 A*算法求解 N 数码难题，理解求 的 解流程和搜索顺序。 使用的是实验环境中已经建立好的“多重路径修建”搜索图

搜索图

算法比

深度优先

Best First 贪婪算 (

A*算法

较 {0} {1.3.4} {3.4.2} {4.2.6} {2.6.5.7.8} {6.5.7.8} {5.7.8} {7.8} {8} {空}

法) {0} {1.3.4} {3.4.2} {4.2.6} {2.6.5.7.8} {6.5.7.8} {5.7.8} {7.8} {8} {空} {0} {1.3.4} {3.4.2} {4.2.6} {2.6.5.7.8} {6.5.7.8} {5.7.8} {7.8} {8} {空} {空} {0} {0.1} {0.1.3} {0.1.3.4} {0.1.3.4.2} {0.1.3.4.2.6} {0.1.3.4.2.6.5} {0.1.3.4.2.6.5.7} {0.1.3.4.2.6.5.7.8} f(x)*=g(x)*+h(x)*

Open 表

Close 表

{空} {空} {0} {0} {0.1} {0.1} {0.1.3} {0.1.3} {0.1.3.4} {0.1.3.4} {0.1.3.4.2} {0.1.3.4.2} {0.1.3.4.2.6} {0.1.3.4.2.6} {0.1.3.4.2.6.5} {0.1.3.4.2.6.5} {0.1.3.4.2.6.5.7} {0.1.3.4.2.6.5.7} {0.1.3.4.2.6.5.7. {0.1.3.4.2.6.5.7.8} 8} f(x)=g(x) f(x)=h(x)

估价函 数

节点 0->节点 1-> 节点 3->节点 4-> 搜索节 节点 2->节点 4-> 点次序 节点 6->节点 4-> 记录 节点 7->节点 5-> 节点 6->节点 8

节点 0->节点 1->节 点 3->节点 4->节点 2->节点 4->节点 6- 节点 0->节点 1->节点 3->节点 4->节点 2->节点 4->节 >节点 4->节点 7-> 点 6->节点 5->节点 7->节点 6->节点 8 节点 5->节点 6->节 点8 最终路径是 节点 0->节点 4->节点 8A*算法结合了启发式方法 (这种方法通过充分利用图给出的信 息来动态地作出决定而使搜索次数大大降低)和形式化方法 (这种方法不利用图给出的信息，而仅通过数学的形式分析， 如 Dijkstra 算法)。 它通过一个估价函数(Heuristic Function) f(h)来估计图中的当前点 p 到终点的距离(带权值),并由此决 定它的搜索方向，当这条路径失败时，它会尝试其它路径。

最终路径是 最终路径是 观测结 节点 0->节点 4->节点 节点 0->节点 4->节 果 8 点8 广度优先搜索算法是 一种搜索策略， 与之相 贪婪算法是一种 对应的还有深度优先 不追求最优解， 只希 搜索算法。 广度优先是 望得到较为满意解 的方法。 贪婪算法一 指从图 G 中 的某点为 般可以快速得到满 始点出发， 标记出所有 意的解， 因为它省去 学生结 与之相邻的点， 并再以 了为找最优解要穷 论 所有与之相邻的点为 尽所有可能而必须 始点， 搜索所有与这些 耗费的大量时间。 贪 点相邻的点， 从而逐层 婪算法常以当前情 向下扩展， 实现对图的 况为基础作最优选 遍历。 同理， 深度优 先 择， 而不考虑各种可 搜索是指从某点出发，能的整体情况， 所以 逐层向下扩展， 直到无 贪婪法不要回溯。 路可扩展时向上回溯，

我们说如果在一般的图搜索算法中应用了上面的估价函数对 OPEN 表进行排序的，就称 A 算法。在

A 算法之上，如果加上

一个条件，对于所有的结点 x,都有 h(x)<=h*(x),那就称为 A*算法。如果取 h(n)=0 同样是 A*算法，这样它就退化成了 有序算法。

它是优先考虑图的深 度 (指从某点的扩展深 度) ,而广度优先则优 先考虑图的广度 (指从 某点 的可扩展量) 。

A*算法是否成功，也就是说是否在效率上胜过蛮力搜索算法， 就在于 h(n)的选取，它不能大于实际的 h*(n),要保守一点， 但越接近 h*(n)给我们的启发性就越大， 是一个难把握的东西。