与或图搜索问题

《与或图搜索问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章与或图搜索问题与或图搜索问题－对问题进行分割后进行搜索1梵塔难题123CBA2解题过程（3个圆盘问题）1231231231231231231231233与/或(AND/OR)图表示与图、或图、与或图ABCD与图ABC或图与图或图4BCDEFGAHMBCDEFGAN与或图5一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点6梵塔问题与或图（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321

2、）（331）（322）（321）（331）（333）72.1基本概念与或图是一个超图，节点间通过连接符连接。K-连接符：…...K个8耗散值的计算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集Cn为连接符的耗散值…...i个nn1n2ni9目标目标初始节点sabc10解图：11能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。12不能解节点没有后裔的非终节点是不能解节

3、点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。13f(n)=g(n)+h(n)对n的评价实际是对从s到n这条路径的评价ns2.2与或图的启发式搜索算法AO*普通图搜索的情况14与或图:对局部图的评价目标目标初始节点abc15两个过程图生成过程，即扩展节点从最优的局部途中选择一个节点扩展计算耗散值的过程对当前的局部图重新新计算耗散值16AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=

4、4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n817目标目标初始节点n0n1n2n3n4n5n6n7n8n4(1)红色：4黄色：3初始节点n0n1(2)n5(1)18目标目标初始节点n0n1n2n3n4n5n6n7n8红色：4黄色：6n3(4)初始节点n0n4(1)n5(1)n1n2(4)519目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)

5、5n6(2)n7(0)n8(0)220目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2121AO*算法AO*算法可划分成两个操作阶段：第一阶段是完成自顶向下的图生成操作,先通过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终结点进行扩展，并对其后继结点赋估计耗散值和加能解标记。22AO*算法第二阶段是完成自下向上的耗散值修正计算、连接符(即指针)的标记以及结点的能解标记。耗散值的修正从刚被

6、扩展的结点n开始，其修正耗散值q(n)取估计h(n)的所有值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈结点的耗散值，只有下层耗散值修正后，才可能影响上一层结点的耗散值，因此必须自底向上一直修正到初始结点。这由算法中的内循环过程完成。23AO*算法与A算法的区别AO*算法不能像A算法那样，单纯靠评价某一个结点来评价局部图。AO*算法由于k-连接符连接的有关子结点，对父结点能解与否以及耗散值都有影响，因而显然不能像A算法那样优先扩展其中具有最小耗散值的结点。24AO*算法仅适用于无环图的假设，否则耗散值

7、递归计算不能收敛，因而在算法中还必须检查新生成的结点已在图中时，是否是正被扩展结点的先辈结点。AO*与A的区别25A算法有OPEN表和CLOSED表，而AO*算法只用一个与或图结构，它代表到目前为止已显式生成的部分搜索图，图中每一个结点的h(n)值是估计最佳解图，而不是估计解路径。AO*与A的区别26