|
与或图的搜索
一、与或图的概念
与或图示例
定义
： 对一个与或图G，从结点n到结点集合Ｎ的一个解图记为G＇，G＇是G的一个子图。
当n是Ｎ的一个元素时，G＇由单一结点n组成。当n不是Ｎ的元素时，如果n有一个指向结点﹛n1，…，nk﹜的外向连接符Ｋ，使得从每一个ni到Ｎ有一个解图，（i=１,…，k），则G＇由结点n、连接符Ｋ、结点{n1，…，nk}中的每一个结点到N的解图所组成；否则从n
到N不存在解图。
二、AO*算法
类似于普通图的A*算法，与或图相应的启发式搜索算法称为AO*算法。
在搜索过程中使用的启发函数h（n）定义为对从结点n到一组终结点的最佳解图的耗散值h*（n）的一个估计。为了简化搜索过程，可以规定单调限制，即对隐含图中每一个从结点n指向其后继结点n1，…，nk的连接符，有
h（n）≤c+h(n1)+...+h(nk)
其中c为该连接符的耗散值。
如果对每一个终结点t，都有h（t）＝0，则上述单调限制就意味着函数h（n）是
h*（n）的一个下界，即对所有的结点n，有
h（n）≤h*（n）
AO*算法的过程
下一讲
返回主页
|