作者:范大少微博劳 | 来源:互联网 | 2023-07-20 15:14
Procedure AO*1.建立一个只由根节点构成的搜索图G.s的费用 q(s) := h(s), G’:=G.如果s是目标,标记s为SOLVED.2.Until s被标记为 SOLVED,do:3.begin4. 通过跟踪从s出发的有标记的连接符计算部分解图G’(G的连接符将在以后的步骤中标记)5. 在G’中选一个非终止的叶节点n.6. 扩展节点n产生n的所有后继,并把它们连到图G上,对于每一个不曾在G中出现的后继nj,q(nj) :=h(nj),如果这些后继中某些节点是终止节点,则用SOLVED标记。7. S:={n};建立一个只由n构成的单元素集合S。8. Until S变空,do:9. begin10. 从S中删除节点m,满足 m在G中的后裔不出现在 S中11. 按以下步骤修改m的费用q(m):对于每一从m出发的指向节点集合{n1i,…,nki}的连接符,计算qi(m)=ci+q(n1i)+…+q(nki),q(m):=min {qi(m)}。(1)将指针标记加到实现此最小值的连接符上。(2)如果本次标记与以前的不同,抹去先前的标记。(3)如果这个连接符指向的所有后继节点都标记了SOLVED,则把m标上SOLVED.12. 如果m标记了SOLVED 或者如果m的修改费用与以前的费用不同,则把m的通过指针标记的连接的所有父节点加到S中.13. end14.end
例子详解和概念详解,附笔记内容:
以上以我笔记展示了AO*详细步骤,如有不对,请指正,感谢!