启发式搜索.doc

A*在游戏中有它很典型的用法,是人工智能在游戏中的代表。 A*算法在人工智能中是一种典型的启发式搜索算法,为了说清楚A*算法,先说说何谓启发式算法。一、何谓启发式搜索算法在说它之前先提提状态空间搜索。状态空间搜索,如果按专业点的说法,就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说,就是在解一个问题时,找到一个解题的过程,应用这个过程可以从求解的开始得到问题的结果。由于求解问题的过程中分支有很多,主要是求解过程中求解条件的不确定性、不完备性造成的,使得求解的路径很多,这样就构成了一个图,我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标为止。深度优先是按照一定的顺序,先查找完一个分支,再查找另一个分支,直至找到目标为止。这两种算法在数据结构书中都有描述,可以参看这些书得到更详细的解释。前面说的广度和深度优先搜索有一个很大的缺陷就是:他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不可预测的情况下就不可取了。他们的效率实在太低,甚至不可完成。在这里就要用到启发式搜索了。启发式搜索就是在状态空间中搜索时,对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直至找到目标。这样可以省略大量无谓的搜索路径,提高了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。启发中的估价是用估价函数表示的,如: f(n)=g(n)+h(n) 其中f(n)是节点n的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n节点到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息,因为g(n)是已知的。二、初识A*算法启发式搜索其实有很多的算法,比如:局部择优搜索法(如爬山法)、最好优先搜索法(Best-first)等等,当然A*也是。这些算法都使用了启发函数,但在具体选取最佳搜索节点时,使用的策略不同。比如局部择优搜索法,就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点、父节点,而一直搜索下去。这种搜索的结果很明显,由于舍弃了其他的节点,可能也把最好的节点都舍弃了,因为求解的最佳节点只是在该阶段的最佳(局部的),并不一定是全局的最佳。最好优先(Best-first)就聪明多了,他在搜索时,便没有舍弃节点(除非该节点是死节点),在每一步的估价中,把当前节点和以前节点的估价值作比较,得到一个“最佳的节点”。这样可以有效的防止“最佳节点”的丢失。那么A*算法又是一种什么样的算法呢?其实A*算法也是一种最好优先(Best-first)的算法。只不过要加上一些约束条件罢了。由于在一些问题求解时,我们希望能够求解出状态空间搜索的最短路径,也就是用最快的方法求解问题,A*就是干这种事情的!我们先下个定义,如果一个估价函数可以找出最短的路径,我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为:f'(n)=g'(n)+h'(n)这里,f'(n)是估价函数,g'(n)是起点到当前节点的最短路径值,h'(n)是n到目标的最短路经的启发值。g'(n)的值实际上很容易从到目前为止的搜索树上计算出来,不必专门定义计算公式,也就是根据搜索历史情况对g'(n)作出计算,显然g(n)>=g'(n)。h'(n)则依赖于启发信息,通常称为启发函数,是要对未来扩展的方向作出估计。A*算法是按f'(n)递增的顺序来排列可能被扩展的节点,因而优先扩展f'(n)值最小的节点,体现了最好优先(Best-first)的搜索思想。但有一点:h(n)<=h'(n)才可(这一点特别的重要)。可以证明应用这样的估价函数是可以找到最短路径的,也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。举一个例子,其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数,h(n)=0,这种h(n)肯定小于h'(n),所以由前述可知广度优先算法是一种可采纳的算法。实际也是。当然它是一种最臭的A*算法。再说一个问题,就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件,如果信息越多或约束条件越多则排除的节点就越多,估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了,谁叫它的h(n)=0,一点启发信息都没有。但h(n)的信息越多,它的计算量就越大,耗费的时间就越多。就应该适当的减小h(n)的信息,即减小约束条件。但算法的准确性就差了,这里就有一个平衡的问题。这是一个矛盾体