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