人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习

人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习

的全部节点，所以它称为全局最佳优先搜索或全局择优搜索。

全局最佳优先搜索实际是对宽度优先搜索和代价树的宽度优先搜索的扩展，而宽度优先搜索和代价树的宽度优先搜索则是它的两个特例(这时可分别令f(x)等于d(x)或g(x)，d(x)表示节点x的深度，而g(x)则表示初始节点S0到节点x的代价)。

在启发式搜索中，估价函数的定义是非常重要的，如果定义得不好，则上述的搜索算法不一定能找到问题的解，即便找到解，也不一定是最优解。所以，有必要讨论如何对估价函数进行限制或定义。

A*启发式搜索算法就使用了一种特殊定义的估价函数。 A*算法具有下列一些性质：

①可采纳性。所谓可采纳性是指对于可求解的状态空间图(即从状态空间图的初始节点到目标节点有路径存在)来说，如果一个搜索算法能在有限步内终止，并且能找到最优解，则称该算法是可采纳的。

②单调性。所谓单调性是指在A*算法中，如果对其估价函数中的h(x)部分即启发性函数，加以适当的单调性限制条件，就可以使它对所扩展的一系列节点的估价函数值单调递增(或非递减)，从而减少对OPEN表或CLOSED表的检查和调整，提高搜索效率。

③信息性(又称最优性)。A*算法的搜索效率主要取决于启发函数h(x)，在满足h(x)≤h*(x)的前提下，h(x)的值越大越好。h(x)的值越大，表明它携带的与求解问题相关的启发信息越多，搜索过程就会在启发信息指导下朝着目标节点前进，所走的弯路越少，搜索效率就会提高。

6 / 6