AO*算法

（1） G={s}，q（s）＝h（s），
      if  s∈t 目标集　then SOLVED（s）←T；建立一个搜索图G，它仅含有一个初始结点s，
      q（s）为相应于结点s的耗散值。如果s 是一个目标结点，则把s标以SOLVED。

（2） untill SOLVED（s），do；外循环，直到s被标以SOLVED。

（3）　begin

（4）  计算局部解图G＇（通过在G中从s往下跟踪标记的连接符）。

（5）　选出一个非终叶结点n∈G＇；n为待扩展的结点。

（6）　P←expand（n）
      if p=φ then q（n）← ∞
      else  p∈P if p G then q(p)←h(p)
                 if p∈目标集 then SOLVED(p)←T
      G←{G，P}；
      扩展结点n，将其所有的后继结点的集合记为P。如果P=φ，即n没有后继点，则记
            q(n)    为     ∞。如果P≠φ，则对P中的每一个结点p，检查其是否在G中，若
      不在G中则为其耗散值q(p)赋值h(p)。若p为目标结点，则将结点p标以SOLVED。最
      后，将P中结点并入搜索图G。

（7）　S←{n}；建立一个结点集合S，它只有一个元素n.

（8） untill S=φ，do；内循环，直到集合S为空。

（9）　　　　begin

（10）  　　 从S中移出一个结点m，该结点在G中所有的后代都不在S中。

（11）　　　 q＇(m)←q(m)
             q_i(m)=c_i+q(n_i1)+…+q(n_ik)
             q(m)=  q_i(m)
             标记对应于q(m)的连接符r，抹掉不同的连接符标记。
   　　　　　If   j  SOLVED（n_rj）=T then SOLVED(m)←T；对m的所有外向连接符计算
             q_i(m)，　取q(m)为其中最小的一个，并标记相应的连接符r。如果与连接符
             r相连的所有结点都已标以SOLVED(m)←，则对结点m标以SOLVED.

（12）        if SOLVED(m)∨q(m)≠q＇(m) then 将向m发出标记的连接符的那些父辈结
     点加入到S中。

（13）　　　　end

（14）        end

             可以看出，AQ*算法可以看成是两个主要操作的循环。外循环是自顶向下的图生长操作（第4至6步）。它根据标记得到最佳的局部解图，挑选一个非终叶结点进行扩展，并对它的后继结点计算耗散值及进行标记。内循环是自底向上的操作（第10步到第12步）。进行修改耗散值、标记连接符、标记SOLVED的操作。它修改被扩展结点的耗散值，对该结点发出的连接符进行标记，并修改该结点祖先结点的耗散值。第10步中令考察的结点m在G中所有的后代都不在S中，这就保证了修改过程是自下而上的。

   算法示例