1、下面的图均为隐式的状态空间图，图中边上标明的数字是
1、下面的图均为隐式的状态空间图，图中边上标明的数字是指边所联接的两个状态的转换代价，节点中的数字是对应状态的启发函数值，
（1）假设要在图 1 中找到一条从 H 到 G 的最短路径，对于图 1 的 a,b 两个图，请分别说明为什么两个图中的启发函数值都不符合 A*算法的要求，请注意两图中节点 F 和 E 的区别。
（2）考虑如图 2 的搜索树，请写出按照下列不同的搜索策略，下一个该扩展的节点是谁？并解释为什么。
i. 宽度优先
ii. 等代价搜索
iii. A*搜索
答案
（1）图 1(a)：E 的启发函数值为 15，E 到 G 的最短路径实际代价为 14，不满足可纳性条件 图 1(b)：F 的启发函数值为 32，F 到 G 的最短路径为 F-E-G，实际代价为 31，不满足可纳性条件 （2）i. C,宽度优先搜索按节点生成的层次顺序扩展，扩展完A、B后，队列首节点为C。 ii. D,等代价搜索扩展路径代价g(n)最小的节点，D的路径代价g(D)=5，小于其他待扩展节点。 iii. G,A*搜索扩展评估函数f(n)=g(n)+h(n)最小的节点，E的f(E)=7+10=17，为当前最小。