与或图的搜索算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 与或图搜索问题,与或图搜索问题对问题进行分割后进行搜索,1,梵塔难题,1,2,3,C,B,A,2,解题过程（3个圆盘问题）,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,3,与/或(AND/OR)图表示,与图、或图、与或图,A,B,C,D,与图,A,B,C,或图,与图,或图,4,B,C,D,E,F,G,A,H,M,B,C,D,E,F,G,A,N,与或图,5,一些关于与或图的术语,H,M,B,C,D,E,F,G,A,N,父节点,与节点,弧线,或节点,子节点,终叶节点,6,梵塔问题与或图,（113）（123）,（111）（113）,（123）（122）,（111）（333）,（122）（322）,（111）（122）,（322）（333）,（321）（331）,（322）（321）,（331）（333）,7,2.1 基本概念,与或图是一个超图，节点间通过连接符连接。,K-连接符：,.,K,个,8,耗散值的计算,k(n,N)=C,n,+k(n,1,N)+k(n,i,N),其中：N为终节点集,C,n,为连接符的耗散值,.,i,个,n,n,1,n,2,n,i,9,目标,目标,初始节点s,a,b,c,10,解图：,11,能解节点,终节点是能解节点,若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。,若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。,12,不能解节点,没有后裔的非终节点是不能解节点。,若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。,若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。,13,f(n)=g(n)+h(n),对n的评价实际是对从s到n这条路径的评价,n,s,2.2 与或图的启发式搜索算法AO*,普通图搜索的情况,14,与或图:对局部图的评价,目标,目标,初始节点,a,b,c,15,两个过程,图生成过程，即扩展节点,从最优的局部途中选择一个节点扩展,计算耗散值的过程,对当前的局部图重新新计算耗散值,16,AO*算法举例,其中：,h(n,0,)=3,h(n,1,)=2,h(n,2,)=4,h(n,3,)=4,h(n,4,)=1,h(n,5,)=1,h(n,6,)=2,h(n,7,)=0,h(n,8,)=0,设：K连接符,的耗散值为K,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,17,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,n,4,(1),红色：4,黄色：3,初始节点,n,0,n,1,(2),n,5,(1),18,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,红色：4,黄色：6,n,3,(4),初始节点,n,0,n,4,(1),n,5,(1),n,1,n,2,(4),5,19,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,红色：5,黄色：6,初始节点,n,0,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),2,20,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,红色：5,黄色：6,初始节点,n,0,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),2,1,21,AO*算法,AO*算法可划分成两个操作阶段：,第一阶段是完成,自顶向下,的图生成操作,先通过有标记的连接符，找到目前为止最好的一个局部解图，然后对其中一个非终结点进行扩展，并对其后继结点赋估计耗散值和加能解标记。,22,AO*算法,第二阶段是完成,自下向上,的耗散值修正计算、连接符(即指针)的标记以及结点的能解标记。,耗散值的修正从刚被扩展的结点n开始，其修正耗散值q(n)取估计h(n)的所有值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈结点的耗散值，只有下层耗散值修正后，才可能影响上一层结点的耗散值，因此必须自底向上一直修正到初始结点。这由算法中的内循环过程完成。,23,AO*算法与A算法的区别,AO*算法不能像A算法那样，单纯靠评价某一个结点来评价局部图。,AO*算法由于k-连接符连接的有关子结点，对父结点能解与否以及耗散值都有影响，因而显然不能像A算法那样优先扩展其中具有最小耗散值的结点。,24,AO*算法仅适用于无环图的假设，否则耗散值递归计算不能收敛，因而在算法中还必须检查新生成的结点已在图中时，是否是正被扩展结点的先辈结点。,AO*与A的区别,25,A算法有OPEN表和CLOSED表，而AO*算法只用一个与或图结构，它代表到目前为止已显式生成的部分搜索图，图中每一个结点的h(n)值是估计最佳解图，而不是估计解路径。,AO*与A的区别,26,