文档介绍：与或图的启发式搜索算法AO*
算法类似于普通图搜索中的算法。在算法中,对当前搜索图的"前沿"(即在OPEN表中的节点)节点进行评价,选取f值最小的节点进行扩展。回想一下,f是如何定义的?
f(n) = g(n) + h(n)
其中g(n)表示的是已经求得的从初始节点到当前节点n的路径耗散值,h(n)表示的是从n到目标节点的最优路径耗散值的估计值。所以对节点n的评价,实际上是对"初始节点--节点n--目标节点"这一条路径的评价。
在与或图搜索中,由于"与"节点的存在,单纯对一个节点的评价已经不能反映解图的全面情况。与或图中的解图相当于普通图中的解路径。从上边所分析的,"对节点n的评价,实际上是对'初始节点--节点n--目标节点'这一条路径的评价"这一思路出发,我们可以很容易的想到,能否通过对局部解图进行评价,来达到类似于普通图中A*搜索的目的。AO*算法,正是这样的一种适用于与或图的搜索算法。
启发式的与或图搜索过程和普通图类似,也是通过评价函数f(n)来引导搜索过程。
对于与或图来说,由于局部图中有多个叶节点,不能像普通图搜索那样,通过对某一个节点的评价来实现对整个局部图的评价。在普通图搜索中,f(n)=g(n)+h(n),表面上是对n的评价,实际上是对通过n的这条路径的评价。因此对于与或图搜索来说,就是通过对局部图的评价来选择待扩展的节点。
下面首先讨论算法本身,然后再通过示例说明搜索过程以及与算法的某些差别。
算法可以划分为两个阶段。
第一阶段:图生成过程,即扩展节点。
对于每一个已经扩展了的节点,算法都有一个指针,指向该节点的后继节点中,耗散值小的那个连接符。图生成过程,就是从初始节点出发,按照该指针向下搜索,一直到找到一个未扩展的节点为止。然后扩展该节点。从下面的讨论可以知道,这实际上扩展的是一个耗散值最小的局部图。
第二阶段:耗散值计算过程。
这是一个逆向的计算过程。设n为最新被扩展的节点,该节点有m个外向连接符连接n的所有后继节点。则根据耗散值的计算公式,可以计算出节点n相对于每一个外向连接符的耗散值。从中选择一个最小值作为n的耗散值。并标记一个指针指向产生最小耗散值的外向连接符。对于n的父节点,进行同样的计算。重复这一过程,直到初始节点s为止。这时,从s出发,选择那些指针所指向的连接符得到的局部图,为当前耗散值最小的局部图。
当连接符全部为1-连接符时,局部图就是一个路径,选择一个耗散值最小的局部图扩展,与第二章中从OPEN表中选择一个f值最小的节点扩展是一致的。
过程:
1、建立一个搜索图G,G:=s,计算q(s)=h(s),IF GOAL(s)THEN M(s,SOLVED);开始时图G只包括s,耗散值估计为h(s),若s是终节点,则标记上能解。
2、Until s已标记上SOLVED,do:
3、begin
4、G′:=FIND(G);根据连接符标记(指针)找出一个待扩展的局部解图G′。
5、n:=G′中的任一非终节点;选一个非终节点作为当前节点。
6、EXPAND(n),生成子节点集{nj},计算q(nj)=h(nj),其中nj G,G:=ADD({nj},G),IF GOAL(nj) THEN M(nj, SOLVED);对G中未出现的子节点计算耗散值,若有终节点则