第二章与或图搜索问题ppt课件.ppt

第二章第二章 与或图搜索问题与或图搜索问题与或图搜索问题－与或图搜索问题－对问题进展分割后进展搜索对问题进展分割后进展搜索l梵塔难题梵塔难题123CBA解题过程〔解题过程〔3个圆盘问题〕个圆盘问题〕123123123123123123123123与与/ /或或(AND/OR)(AND/OR)图表示图表示l与图、或图、与或图与图、或图、与或图ABCD与图ABC或图与图与图或图或图BCDEFGAHMBCDEFGAN与或图与或图一些关于与或图的术语一些关于与或图的术语HMBCDEFGAN父节点与节点弧线或节点子节点终叶节点梵塔问题与或图梵塔问题与或图〔〔〔〔113113〕〕〕〕 〔〔〔〔123123〕〕〕〕ÞÞ 〔〔〔〔111111〕〕〕〕 〔〔〔〔113113〕〕〕〕ÞÞ 〔〔〔〔123123〕〕〕〕 〔〔〔〔122122〕〕〕〕ÞÞ 〔〔〔〔111111〕〕〕〕 〔〔〔〔333333〕〕〕〕ÞÞ 〔〔〔〔122122〕〕〕〕 〔〔〔〔322322〕〕〕〕ÞÞ 〔〔〔〔111111〕〕〕〕 〔〔〔〔122122〕〕〕〕ÞÞ 〔〔〔〔322322〕〕〕〕 〔〔〔〔333333〕〕〕〕ÞÞ 〔〔〔〔321321〕〕〕〕 〔〔〔〔331331〕〕〕〕ÞÞ 〔〔〔〔322322〕〕〕〕 〔〔〔〔321321〕〕〕〕ÞÞ 〔〔〔〔331331〕〕〕〕 〔〔〔〔333333〕〕〕〕ÞÞ 2.1 根本概念根本概念l与或图是一个超图，节点间经过衔接符衔接。

与或图是一个超图，节点间经过衔接符衔接lK-衔接符：衔接符：…...K个耗散值的计算耗散值的计算k(n, N) = Cn+k(n1, N)+…+k(ni, N)其中：其中：N为终节点集为终节点集 Cn为衔接符的耗散值为衔接符的耗散值…...i个nn1n2ni目的目的目的目的初始节点初始节点sabc• 解图：解图：能解节点能解节点l终节点是能解节点终节点是能解节点l假设非终节点有假设非终节点有“或〞子节点时，当且仅当其或〞子节点时，当且仅当其子节点至少有一能解时，该非终节点才干解子节点至少有一能解时，该非终节点才干解l假设非终节点有假设非终节点有“与〞子节点时，当且仅当其与〞子节点时，当且仅当其子节点均能解时，该非终节点才干解子节点均能解时，该非终节点才干解不能解节点不能解节点l没有后裔的非终节点是不能解节点没有后裔的非终节点是不能解节点l假设非终节点有假设非终节点有“或〞子节点，当且仅当一切或〞子节点，当且仅当一切子节点均不能解时，该非终节点才不能解子节点均不能解时，该非终节点才不能解l假设非终节点有假设非终节点有“与〞子节点时，当至少有一与〞子节点时，当至少有一个子节点不能解时，该非终节点才不能解。

个子节点不能解时，该非终节点才不能解f(n) = g(n) + h(n)对n的评价实践是对从s到n这条途径的评价ns2.2 与或图的启发式搜索算法与或图的启发式搜索算法AO*普通图搜索的情况普通图搜索的情况与或图与或图: 对部分图的评价对部分图的评价目的目的目的目的初始节点初始节点abc两个过程两个过程l图生成过程，即扩展节点图生成过程，即扩展节点l从最优的部分途中选择一个节点扩展从最优的部分途中选择一个节点扩展l计算耗散值的过程计算耗散值的过程l对当前的部分图重新新计算耗散值对当前的部分图重新新计算耗散值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目的目的目的目的初始节点初始节点n0n1n2n3n4n5n6n7n8目的目的目的目的初始节点初始节点n0n1n2n3n4n5n6n7n8n4(1)红色：红色：4黄色：黄色：3初始节点初始节点n0n1(2)n5(1)目的目的目的目的初始节点初始节点n0n1n2n3n4n5n6n7n8红色：红色：4黄色：黄色：6n3(4)初始节点初始节点n0n4(1)n5(1)n1n2(4)5目的目的目的目的初始节点初始节点n0n1n2n3n4n5n6n7n8红色：红色：5黄色：黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目的目的目的目的初始节点初始节点n0n1n2n3n4n5n6n7n8红色：红色：5黄色：黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21AO*算法算法 AO*算法可划分成两个操作阶段：算法可划分成两个操作阶段： 第一阶段是完成自顶向下的图生成操作第一阶段是完成自顶向下的图生成操作,先经先经过有标志的衔接符，找到目前为止最好的一个过有标志的衔接符，找到目前为止最好的一个部分解图，然后对其中一个非终结点进展扩展，部分解图，然后对其中一个非终结点进展扩展，并对其后继结点赋估计耗散值和加能解标志。

并对其后继结点赋估计耗散值和加能解标志AO*算法算法 第二阶段是完成自下向上的耗散值修正计算、衔接第二阶段是完成自下向上的耗散值修正计算、衔接符符(即指针即指针)的标志以及结点的能解标志的标志以及结点的能解标志 耗散值的修正从刚被扩展的结点耗散值的修正从刚被扩展的结点n开场，其修正耗散开场，其修正耗散值值q(n)取估计取估计h(n)的一切值中最小的一个，然后根据的一切值中最小的一个，然后根据耗散值递归计算公式逐级向上修正其先辈结点的耗耗散值递归计算公式逐级向上修正其先辈结点的耗散值，只需下层耗散值修正后，才能够影响上一层散值，只需下层耗散值修正后，才能够影响上一层结点的耗散值，因此必需自底向上不断修正到初始结点的耗散值，因此必需自底向上不断修正到初始结点这由算法中的内循环过程完成这由算法中的内循环过程完成AO*算法与算法与A算法的区别算法的区别AO*算法不能像A算法那样，单纯靠评价某一个结点来评价部分图AO*算法由于k-衔接符衔接的有关子结点，对父结点能解与否以及耗散值都有影响，因此显然不能像A算法那样优先扩展其中具有最小耗散值的结点lAO*AO*算算法法仅仅适适用用于于无无环环图图的的假假设设，，否否那那么么耗耗散散值值递递归归计计算算不不能能收收敛敛，，因因此此在在算算法法中中还还必必需需检检查查新新生生成成的的结结点点已已在在图图中中时时，，能能否否是正被扩展结点的先辈结点。

是正被扩展结点的先辈结点AO*与与A的区别的区别lA A算算法法有有OPENOPEN表表和和CLOSEDCLOSED表表，，而而AO*AO*算算法法只只用用一一个个与与或或图图构构造造，，它它代代表表到到目目前前为为止止已已显显式式生生成成的的部部分分搜搜索索图图，，图图中中每每一一个个结结点点的的h(n)h(n)值值是是估估计计最最正正确确解解图图，，而而不不是是估估计计解途径AO*与与A的区别的区别。