资源描述：
《搜索(与或图搜索实例AO算法).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、与或图搜索与或图表示HMBCDEFGAN父节点与节点弧线或节点子节点终结点与或图是一个超图，节点间通过连接符连接。K-连接符：…...K个与或图搜索问题目标目标初始节点sabcn0→{n7,n8}的3个解图目标n7目标n8初始节点n0目标n7目标n8初始节点n0目标n7目标n8初始节点n0(a)(b)(c)ttttttttt（a）（b）有解节点无解节点终结点能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时
2、，该非终节点才能解。不能解节点没有后裔的非终节点是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。耗散值的计算1.若n是N的一个元素,则k(n,N)=02.若n是一个外向连接符指向后继结点{n1,..ni}k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集Cn为连接符的耗散值…...i个nn1n2ni搜索解图耗散值的递归计算:n0=2+k(4,N)+k(5,N)k(5,N)
3、=min(2+k(7,N)+k(8,N),…)=2k(4,N)=min(1+k(5,N),1+k(8,N))=min(3,1)=1N0=2+1+2=5(a)的解图耗散值为8(b)的解图耗散值为7具有最小耗散值的解图称为最佳解图,其值也用h*(n)标记.上例中的h*(n)=5(c)n4n5目标n7目标n8初始节点n0普通图搜索的情况f(n)=g(n)+h(n)对n的评价实际是对从s经过n到目的地这条路径的评价ns与或图:对局部图的评价目标目标初始节点abc与或图搜索:AO*算法两个过程图生成过程，即扩展节点自顶
4、向下,从最优的局部途中选择一个节点扩展计算耗散值的过程自下向顶,对当前的局部图重新计算耗散值AO*算法搜索例子其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n8AO*算法搜索例子G中只有一个结点n0第一个大循环(扩展结点),直到n0是SOLVED:找到待扩展的局部图G’{n0}n=G’中任意结点,此时n=n0扩展结点n=n0,生成后继结点集合{n1,n4
5、,n5},q(n4)=1,q(n5)=1,q(n1)=2,都不是终结点,把结点加到G中小循环(修改结点耗散值),直到S为空:a.S={n=n0}b.保证n的后代不在S中c.m=n0的连接符有两条,计算q1(m)=1+q(n1)=1+2=3q2(m)=2+q(n5)+q(n4)=2+1+1=4令q(m)=q(n0)=min(q1,q2)=3d.修改指针到q1对应的连结符上去e.如果n1为非SOLVED,则m=n0也为非SOLVEDf.如果m=n0为SOLVED,或者q(m)被修改过,则需要也对m的父结点进行修改
6、,即将m的父结点加到S中g.小循环结束5.大循环结束初始节点n0n1n4n5连接符1连接符2q=3AO*算法搜索例子G={n0,n1,n4,n5}第二个大循环(扩展结点),直到n0是SOLVED:找到待扩展的局部图G’{n0,n1}n=G’中非终结点,此时n=n1扩展结点n=n1,生成后继结点集合{n2,n3},q(n2)=4,q(n3)=4,都不是终结点,把结点加到G中小循环(修改结点耗散值),直到S为空:a.S={n=n1}b.保证n的后代不在S中c.m=n1的连接符有两条,计算q1(m)=1+q(n3)
7、=1+4=5q2(m)=1+q(n2)=1+4=5令q(m)=q(n0)=min(q1,q2)=5d.修改指针到q1对应的连结符上去e.如果n3非SOLVED,则m=n1也为非SOLVEDf.q(m=n1)被修改过,则需要也对m的父结点进行修改,即将m=n1的父结点n0加到S中g.小循环结束5.大循环结束初始节点n0n1n4n5连接符1连接符2n2n3q=5继续小循环:…c.m=n0的连接符有两条,计算q1(m)=1+h(n1)=1+5=6q2(m)=1+h(n5)+h(4)=4令q(m)=q(n1)=min
8、(q1,q2)=4d.修改指针到q2对应的连结符上去…q=4q=3AO*算法搜索例子G={n0,n1,n2,n3,n4,n5}第三个大循环(扩展结点),直到n0是SOLVED:找到待扩展的局部图G’{n0,n4,n5}n=G’中非终结点,此时n=n5扩展结点n=n5,生成后继结点集合{n6,n7,n8},q(n6)=2,q(n7)=0,q(n8)=0把结点加到G中小循环(修改结点耗散值),直到S为空
