人工智能a算法.doc

1．启发式搜索算法A 　　启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。其基本思想 是：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展 。 评价函数的形式如下： f（n）＝g（n）＋h（n） 其中n是被评价的节点。 f（n）、g（n）和h（n）各自表述什么含义呢？我们先来定义下面几个函数的含义，它 们与f（n）、g（n）和h（n）的差别是都带有一个"*"号。 g*(n)：表示从初始节点s到节点n的最短路径的耗散值； h*(n)：表示从节点n到目标节点g的最短路径的耗散值； f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。 　　而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值 的的估计值。是一种预测。A算法就是利用这种预测，来达到有效搜索的目的的。它每次 按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点 则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展 。 利用评价函数f（n）＝g（n）