AO*算法详解，附例子和算法详细步骤

Procedure AO*1&＃xff0e;建立一个只由根节点构成的搜索图G&＃xff0e;s的费用 q(s) :&＃61; h(s), G’:&＃61;G&＃xff0e;如果s是目标&＃xff0c;标记s为SOLVED.2&＃xff0e;Until s被标记为 SOLVED&＃xff0c;do&＃xff1a;3&＃xff0e;begin4&＃xff0e; 通过跟踪从s出发的有标记的连接符计算部分解图G’&＃xff08;G的连接符将在以后的步骤中标记&＃xff09;5&＃xff0e; 在G’中选一个非终止的叶节点n.6&＃xff0e; 扩展节点n产生n的所有后继&＃xff0c;并把它们连到图G上&＃xff0c;对于每一个不曾在G中出现的后继nj&＃xff0c;q(nj) :&＃61;h(nj)&＃xff0c;如果这些后继中某些节点是终止节点&＃xff0c;则用SOLVED标记。7&＃xff0e; S:&＃xff1d;{n}&＃xff1b;建立一个只由n构成的单元素集合S。8&＃xff0e; Until S变空&＃xff0c;do&＃xff1a;9&＃xff0e; begin10&＃xff0e; 从S中删除节点m&＃xff0c;满足 m在G中的后裔不出现在 S中11&＃xff0e; 按以下步骤修改m的费用q(m)&＃xff1a;对于每一从m出发的指向节点集合{n1i&＃xff0c;…&＃xff0c;nki}的连接符&＃xff0c;计算qi(m)&＃61;ci&＃43;q(n1i)&＃43;…&＃43;q(nki)&＃xff0c;q(m):&＃xff1d;min {qi(m)}。(1)将指针标记加到实现此最小值的连接符上。(2)如果本次标记与以前的不同&＃xff0c;抹去先前的标记。(3)如果这个连接符指向的所有后继节点都标记了SOLVED&＃xff0c;则把m标上SOLVED&＃xff0e;12&＃xff0e; 如果m标记了SOLVED 或者如果m的修改费用与以前的费用不同&＃xff0c;则把m的通过指针标记的连接的所有父节点加到S中&＃xff0e;13&＃xff0e; end14&＃xff0e;end

 例子详解和概念详解&＃xff0c;附笔记内容&＃xff1a;

以上以我笔记展示了AO*详细步骤&＃xff0c;如有不对&＃xff0c;请指正&＃xff0c;感谢&＃xff01;