搜索(与或图搜索实例AO算法).ppt

与或图搜索与或图搜索与或图表示与或图表示HMBCDEFGAN父节点与节点弧线或节点子节点终结点与或图是一个超图，节点间通过连与或图是一个超图，节点间通过连接符连接。接符连接。K-K-连接符：连接符：.K个与或图搜索问题与或图搜索问题目标目标初始节点sabcn0 n7,n8的的3个解图个解图目标目标n7目标目标n8初始节初始节点点n0目标目标n7目标目标n8初始节初始节点点n0目标目标n7目标目标n8初始节初始节点点n0(a)(b)(c)ttttttttt（a）（b）有解节点有解节点无解节点无解节点终结点终结点能解节点能解节点终节点是能解节点终节点是能解节点若非终节点有若非终节点有“或或”子节点时，当且仅当其子节点至少有一能解时，该非终节点子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。才能解。若非终节点有若非终节点有“与与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。子节点时，当且仅当其子节点均能解时，该非终节点才能解。不能解节点不能解节点没有后裔的非终节点是不能解节点。没有后裔的非终节点是不能解节点。若非终节点有若非终节点有“或或”子节点，当且仅当所有子节点均不能解时，该非终节点才不子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。能解。若非终节点有若非终节点有“与与”子节点时，当至少有一个子节点不能解时，该非终节点才不子节点时，当至少有一个子节点不能解时，该非终节点才不能解。能解。耗散值的计算耗散值的计算1.1.若若n n是是N N的一个元素的一个元素,则则k(n,N)=0k(n,N)=02.2.若若n n是一个外向连接符指向后继结点是一个外向连接符指向后继结点n1,.nin1,.nik(n,N)=Ck(n,N)=Cn n+k(n+k(n1 1,N)+,N)+k(n+k(ni i,N),N)其中：其中：N N为终节点集为终节点集 C Cn n为连接符的耗散值为连接符的耗散值.i个个nn1n2ni搜索解图耗散值的递归计算搜索解图耗散值的递归计算:n0=2+k(4,N)+k(5,N)n0=2+k(4,N)+k(5,N)k(5,N)=min(2+k(7,N)+k(8,N),k(5,N)=min(2+k(7,N)+k(8,N),)=2 =2k(4,N)=min(1+k(5,N),1+k(8,N)k(4,N)=min(1+k(5,N),1+k(8,N)=min(3,1)=1 =min(3,1)=1N0=2+1+2=5N0=2+1+2=5(a)(a)的解图耗散值为的解图耗散值为8 8(b)(b)的解图耗散值为的解图耗散值为7 7 具有最小耗散值的解图称为最佳具有最小耗散值的解图称为最佳解图解图,其值也用其值也用h*(n)h*(n)标记标记.上例中的上例中的h*(n)=5h*(n)=5(c)n4n5目标目标n7目标目标n8初始节初始节点点n0普通图搜索的情况普通图搜索的情况f(n)=g(n)+h(n)f(n)=g(n)+h(n)对对n n的评价实际是对从的评价实际是对从s s经过经过n n到目的地这条路径的评价到目的地这条路径的评价ns与或图与或图:对局部图的评价对局部图的评价目标目标初始节点abc与或图搜索与或图搜索:AO*:AO*算法算法两个过程两个过程图生成过程，即扩展节点图生成过程，即扩展节点 自顶向下自顶向下,从最优的局部途中选择一个节点扩展从最优的局部途中选择一个节点扩展计算耗散值的过程计算耗散值的过程 自下向顶自下向顶,对当前的局部图重新计算耗散值对当前的局部图重新计算耗散值AO*算法搜索例子算法搜索例子其中：其中：h(nh(n0 0)=3)=3 h(n h(n1 1)=2)=2 h(n h(n2 2)=4)=4 h(n h(n3 3)=4)=4 h(n h(n4 4)=1)=1 h(n h(n5 5)=1)=1 h(n h(n6 6)=2)=2 h(n h(n7 7)=0)=0 h(n h(n8 8)=0)=0设：设：K K连接符连接符的耗散值为的耗散值为K K目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8AO*算法搜索例子算法搜索例子G G中只有一个结点中只有一个结点n0n0第一个大循环第一个大循环(扩展结点扩展结点),),直到直到n0n0是是SOLVED:SOLVED:1.1.找到待扩展的局部图找到待扩展的局部图G Gn0n02.2.n=Gn=G中任意结点中任意结点,此时此时n=n0n=n0扩展结点扩展结点n=n0,n=n0,生成后继结点集合生成后继结点集合n1,n4,n5,n1,n4,n5,q(n4)=1,q(n5)=1,q(n1)=2,q(n4)=1,q(n5)=1,q(n1)=2,都不是终结点都不是终结点,把结点加到把结点加到G G中中1.1.小循环小循环(修改结点耗散值修改结点耗散值),),直到直到S S为空为空:a.S=n=n0 a.S=n=n0 b.b.保证保证n n的后代不在的后代不在S S中中 c.m=n0c.m=n0的连接符有两条的连接符有两条,计算计算q1(m)=1+q(n1)=1+2=3q1(m)=1+q(n1)=1+2=3 q2(m)=2+q(n5)+q(n4)=2+1+1=4 q2(m)=2+q(n5)+q(n4)=2+1+1=4 令令q(m)=q(n0)=min(q1,q2)=3q(m)=q(n0)=min(q1,q2)=3 d.d.修改指针到修改指针到q1q1对应的连结符上去对应的连结符上去 e.e.如果如果n1n1为非为非SOLVED,SOLVED,则则m=n0m=n0也为非也为非SOLVEDSOLVED f.f.如果如果m=n0m=n0为为SOLVED,SOLVED,或者或者q(m)q(m)被修改过被修改过,则需则需要也对要也对m m的父结点进行修改的父结点进行修改,即将即将m m的父结点加的父结点加到到S S中中 g.g.小循环结束小循环结束5.5.大循环结束大循环结束初始节点初始节点n0n1n4n5连接符连接符1连接符连接符2q=3AO*算法搜索例子算法搜索例子G=n0,n1,n4,n5G=n0,n1,n4,n5第二个大循环第二个大循环(扩展结点扩展结点),),直到直到n0n0是是SOLVED:SOLVED:1.1.找到待扩展的局部图找到待扩展的局部图G Gn0,n1n0,n12.2.n=Gn=G中非终结点中非终结点,此时此时n=n1n=n1扩展结点扩展结点n=n1,n=n1,生成后继结点集合生成后继结点集合n2,n3,n2,n3,q(n2)=4,q(n3)=4,q(n2)=4,q(n3)=4,都不是终结点都不是终结点,把结点加到把结点加到G G中中1.1.小循环小循环(修改结点耗散值修改结点耗散值),),直到直到S S为空为空:a.S=n=n1 a.S=n=n1 b.b.保证保证n n的后代不在的后代不在S S中中 c.m=n1c.m=n1的连接符有两条的连接符有两条,计算计算q1(m)=1+q(n3)=1+4=5q1(m)=1+q(n3)=1+4=5 q2(m)=1+q(n2)=1+4=5 q2(m)=1+q(n2)=1+4=5 令令q(m)=q(n0)=min(q1,q2)=5q(m)=q(n0)=min(q1,q2)=5 d.d.修改指针到修改指针到q1q1对应的连结符上去对应的连结符上去 e.e.如果如果n3n3非非SOLVED,SOLVED,则则m=n1m=n1也为非也为非SOLVEDSOLVED f.q(m=n1)f.q(m=n1)被修改过被修改过,则需要也对则需要也对m m的父结点进的父结点进行修改行修改,即将即将m=n1m=n1的父结点的父结点n0n0加到加到S S中中 g.g.小循环结束小循环结束5.5.大循环结束大循环结束初始节点初始节点n0n1n4n5连接符连接符1连接符连接符2n2n3q=5 继续小循环继续小循环:c.m=n0 c.m=n0的连接符有两条的连接符有两条,计算计算 q1(m)=1+h(n1)=1+5=6 q1(m)=1+h(n1)=1+5=6 q2(m)=1+h(n5)+h(4)=4q2(m)=1+h(n5)+h(4)=4 令令 q(m)=q(n1)=min(q1,q2)=4q(m)=q(n1)=min(q1,q2)=4d.d.修改指针到修改指针到q2q2对应的连结符上去对应的连结符上去 q=4q=3AO*算法搜索例子算法搜索例子G=n0,n1,n2,n3,n4,n5G=n0,n1,n2,n3,n4,n5第三个大循环第三个大循环(扩展结点扩展结点),),直到直到n0n0是是SOLVED:SOLVED:1.1.找到待扩展的局部图找到待扩展的局部图G Gn0,n4,n5n0,n4,n52.2.n=Gn=G中非终结点中非终结点,此时此时n=n5n=n5扩展结点扩展结点n=n5,n=n5,生成后继结点集合生成后继结点集合n6,n7,n8,q(n6)=2,q(n7)=0,q(n8)=0n6,n7,n8,q(n6)=2,q(n7)=0,q(n8)=0把结点加到把结点加到G G中中1.1.小循环小循环(修改结点耗散值修改结点耗散值),),直到直到S S为空为空:a.S=n=n5 a.S=n=n5 b.b.保证保证n n的后代不在的后代不在S S中中 c.m=n5c.m=n5的连接符有两条的连接符有两条,计算计算q1(m)=1+q(n6)=1+2=3q1(m)=1+q(n6)=1+2=3 q2(m)=1+q(n7)+q(n8)=2+0+0=2 q2(m)=1+q(n7)+q(n8)=2+0+0=2 令令q(m)=q(n5)=min(q1,q2)=2q(m)=q(n5)=min(q1,q2)=2 d.d.修改指针到修改指针到q2q2对应的连结符上去对应的连结符上去 e.n7,n8e.n7,n8为为SOLVED,SOLVED,则则m=n5m=n5也为也为SOLVEDSOLVED f.q(m=n5)f.q(m=n5)被修改过被修改过,则需要也对则需要也对m m的父结的父结点进行修改点进行修改,即将即将m=n5m=n5的父结点的父结点n0n0加到加到S S中中 g.g.小循环结束小循环结束5.5.大循环结束大循环结束初始节点初始节点n0n1n4n5连接符连接符1连接符连接符2n2n3q=5q=4n6n7n8q=1q=2q=5AO*算法搜索例子算法搜索例子G=n0,n1,n2,n3,n4,n5,n6,n7,n8G=n0,n1,n2,n3,n4,n5,n6,n7,n8第四个大循环第四个大循环(扩展结点扩展结点),),直到直到n0n0是是SOLVED:SOLVED:1.1.找到待扩展的局部图找到待扩展的局部图G Gn0,n4,n5,n7,n8n0,n4,n5,n7,n82.2.n=Gn=G中非终结点中非终结点,此时此时n=n4n=n4扩展结点扩展结点n=n4,n=n4,生成后继结点集合生成后继结点集合n5,n5,n8,q(n5)=2,q(n8)=0n8,q(n5)=2,q(n8)=0小循环小循环(修改结点耗散值修改结点耗散值),),直到直到S S为空为空:a.S=n=n4 a.S=n=n4 b.b.保证保证n n的后代不在的后代不在S S中中 c.m=n5c.m=n5的连接符有两条的连接符有两条,计算计算q1(m)=1+q(n5)=1+2=3q1(m)=1+q(n5)=1+2=3 q2(m)=1+q(n8)=1+0=1 q2(m)=1+q(n8)=1+0=1 令令q(m)=q(n4)=min(q1,q2)=1q(m)=q(n4)=min(q1,q2)=1 d.d.修改指针到修改指针到q2q2对应的连结符上去对应的连结符上去 e.n8e.n8为为SOLVED,SOLVED,则则m=n4m=n4也为也为SOLVEDSOLVED f.m=n4 f.m=n4也为也为SOLVED,SOLVED,则需要也对则需要也对m m的父结点的父结点进行修改进行修改,即将即将m=n1m=n1的父结点的父结点n0n0加到加到S S中中 g.g.小循环结束小循环结束5.5.大循环结束大循环结束初始节点初始节点n0n1n4n5连接符连接符1连接符连接符2n2n3q=5n6n7n8q=2q=5q=1 在重新计算在重新计算n0n0耗散的小循环中耗散的小循环中:由于由于n4,n5n4,n5为为SOLVED,SOLVED,则则n0n0为为SOLVEDSOLVEDq(n0)=5,q(n0)=5,找到解找到解 AO*AO*算法的最优性算法的最优性:若若s s N N存在解图存在解图,当当h(n)h*(n),h(n)h*(n),且且h(n)h(n)满足单调限制条件满足单调限制条件,则则AO*AO*一定能够找到最佳解图一定能够找到最佳解图,即即AO*AO*具有可采纳性具有可采纳性 单调限制条件指对于图中从结点到单调限制条件指对于图中从结点到n nn1,n1,nk,nk的每一个连接符都的每一个连接符都施加限制施加限制h(n)C+h(n1)+.+h(nk),h(n)C+h(n1)+.+h(nk),如果同时有如果同时有h(ti)=0(tiN),h(ti)=0(tiN),那那么单调限制意味着么单调限制意味着h h是是h*h*的下界范围的下界范围,即对所有的结点即对所有的结点n n有有h(n)h*(n)h(n)h*(n)与或图搜索与或图搜索与或图表示与或图表示HMBCDEFGAN父节点与节点弧线或节点子节点终结点与或图是一个超图，节点间通过连与或图是一个超图，节点间通过连接符连接。接符连接。K-K-连接符：连接符：.K个与或图搜索问题与或图搜索问题目标目标初始节点sabcn0 n7,n8的的3个解图个解图目标目标n7目标目标n8初始节初始节点点n0目标目标n7目标目标n8初始节初始节点点n0目标目标n7目标目标n8初始节初始节点点n0(a)(b)(c)ttttttttt（a）（b）有解节点有解节点无解节点无解节点终结点终结点能解节点能解节点终节点是能解节点终节点是能解节点若非终节点有若非终节点有“或或”子节点时，当且仅当其子节点至少有一能解时，该非终节点子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。才能解。若非终节点有若非终节点有“与与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。子节点时，当且仅当其子节点均能解时，该非终节点才能解。不能解节点不能解节点没有后裔的非终节点是不能解节点。没有后裔的非终节点是不能解节点。若非终节点有若非终节点有“或或”子节点，当且仅当所有子节点均不能解时，该非终节点才不子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。能解。若非终节点有若非终节点有“与与”子节点时，当至少有一个子节点不能解时，该非终节点才不子节点时，当至少有一个子节点不能解时，该非终节点才不能解。能解。耗散值的计算耗散值的计算1.1.若若n n是是N N的一个元素的一个元素,则则k(n,N)=0k(n,N)=02.2.若若n n是一个外向连接符指向后继结点是一个外向连接符指向后继结点n1,.nin1,.nik(n,N)=Ck(n,N)=Cn n+k(n+k(n1 1,N)+,N)+k(n+k(ni i,N),N)其中：其中：N N为终节点集为终节点集 C Cn n为连接符的耗散值为连接符的耗散值.i个个nn1n2ni搜索解图搜索解图(c)(c)耗散值的递归计算耗散值的递归计算:n0=2+k(4,N)+k(5,N)n0=2+k(4,N)+k(5,N)k(5,N)=min(2+k(7,N)+k(8,N),k(5,N)=min(2+k(7,N)+k(8,N),)=2 =2k(4,N)=min(1+k(5,N),1+k(8,N)k(4,N)=min(1+k(5,N),1+k(8,N)=min(3,1)=1 =min(3,1)=1N0=2+1+2=5N0=2+1+2=5 同理可计算得：同理可计算得：(a)(a)的解图耗散值为的解图耗散值为8 8(b)(b)的解图耗散值为的解图耗散值为7 7 具有最小耗散值的解图称为最佳具有最小耗散值的解图称为最佳解图解图,其值也用其值也用h*(n)h*(n)标记标记.上例中的上例中的h*(n)=5h*(n)=5解图解图(c)n4n5目标目标n7目标目标n8初始节初始节点点n0普通图搜索的情况普通图搜索的情况f(n)=g(n)+h(n)f(n)=g(n)+h(n)对对n n的评价实际是对从的评价实际是对从s s经过经过n n到目的地这条路径的评价到目的地这条路径的评价nst与或图与或图:对局部图的评价对局部图的评价目标目标初始节点abc与或图搜索与或图搜索:AO*:AO*算法算法两个过程两个过程图生成过程，即扩展节点图生成过程，即扩展节点 自顶向下自顶向下,从最优的局部途中选择一个节点扩展从最优的局部途中选择一个节点扩展计算耗散值的过程计算耗散值的过程 自下向顶自下向顶,对当前的局部图重新计算耗散值对当前的局部图重新计算耗散值AO*算法搜索例子算法搜索例子其中：其中：h(nh(n0 0)=3)=3 h(n h(n1 1)=2)=2 h(n h(n2 2)=4)=4 h(n h(n3 3)=4)=4 h(n h(n4 4)=1)=1 h(n h(n5 5)=1)=1 h(n h(n6 6)=2)=2 h(n h(n7 7)=0)=0 h(n h(n8 8)=0)=0设：设：K K连接符连接符的耗散值为的耗散值为K K目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8AO*算法搜索例子算法搜索例子G G中只有一个结点中只有一个结点n0n0第一个大循环第一个大循环(扩展结点扩展结点),),直到直到n0n0是是SOLVED:SOLVED:1.1.找到待扩展的局部图找到待扩展的局部图G Gn0n02.2.n=Gn=G中任意结点中任意结点,此时此时n=n0n=n0扩展结点扩展结点n=n0,n=n0,生成后继结点集合生成后继结点集合n1,n4,n5,n1,n4,n5,q(n4)=1,q(n5)=1,q(n1)=2,q(n4)=1,q(n5)=1,q(n1)=2,都不是终结点都不是终结点,把结点加到把结点加到G G中中1.1.小循环小循环(修改结点耗散值修改结点耗散值),),直到直到S S为空为空:a.S=n=n0 a.S=n=n0 b.b.保证保证n n的后代不在的后代不在S S中中 c.c.取出取出m=n0m=n0的连接符有两条的连接符有两条,计算计算q1(m)=1+q(n1)=1+2=3q1(m)=1+q(n1)=1+2=3 q2(m)=2+q(n5)+q(n4)=2+1+1=4 q2(m)=2+q(n5)+q(n4)=2+1+1=4 令令q(m)=q(n0)=min(q1,q2)=3q(m)=q(n0)=min(q1,q2)=3 d.d.修改指针到修改指针到q1q1对应的连结符上去对应的连结符上去 e.e.如果如果n1n1为非为非SOLVED,SOLVED,则则m=n0m=n0也为非也为非SOLVEDSOLVED f.f.如果如果m=n0m=n0为为SOLVED,SOLVED,或者或者q(m)q(m)被修改过被修改过,则需则需要也对要也对m m的父结点进行修改的父结点进行修改,即将即将m m的父结点加的父结点加到到S S中中 g.g.小循环结束小循环结束5.5.大循环结束大循环结束初始节点初始节点n0n1n4n5连接符连接符1连接符连接符2q=3即即h(n)AO*算法搜索例子算法搜索例子G=n0,n1,n4,n5G=n0,n1,n4,n5第二个大循环第二个大循环(扩展结点扩展结点),),直到直到n0n0是是SOLVED:SOLVED:1.1.找到待扩展的局部图找到待扩展的局部图G Gn0,n1n0,n12.2.n=Gn=G中非终结点中非终结点,此时此时n=n1n=n1扩展结点扩展结点n=n1,n=n1,生成后继结点集合生成后继结点集合n2,n3,n2,n3,q(n2)=4,q(n3)=4,q(n2)=4,q(n3)=4,都不是终结点都不是终结点,把结点加到把结点加到G G中中1.1.小循环小循环(修改结点耗散值修改结点耗散值),),直到直到S S为空为空:a.S=n=n1 a.S=n=n1 b.b.保证保证n n的后代不在的后代不在S S中中 c.c.取出取出m=n1m=n1的连接符有两条的连接符有两条,计算计算q1(m)=1+q(n3)=1+4=5q1(m)=1+q(n3)=1+4=5 q2(m)=1+q(n2)=1+4=5 q2(m)=1+q(n2)=1+4=5 令令q(m)=q(n0)=min(q1,q2)=5q(m)=q(n0)=min(q1,q2)=5 d.d.修改指针到修改指针到q1q1对应的连结符上去对应的连结符上去 e.e.如果如果n3n3非非SOLVED,SOLVED,则则m=n1m=n1也为非也为非SOLVEDSOLVED f.q(m=n1)f.q(m=n1)被修改过被修改过,则需要也对则需要也对m m的父结点进的父结点进行修改行修改,即将即将m=n1m=n1的父结点的父结点n0n0加到加到S S中中 g.g.小循环结束小循环结束5.5.大循环结束大循环结束初始节点初始节点n0n1n4n5连接符连接符1连接符连接符2n2n3q=5 继续小循环继续小循环:c.m=n0 c.m=n0的连接符有两条的连接符有两条,计算计算 q1(m)=1+h(n1)=1+5=6 q1(m)=1+h(n1)=1+5=6 q2(m)=2+h(n5)+h(4)=4q2(m)=2+h(n5)+h(4)=4 令令 q(m)=q(n1)=min(q1,q2)=4q(m)=q(n1)=min(q1,q2)=4d.d.修改指针到修改指针到q2q2对应的连结符上去对应的连结符上去 q=4q=3AO*算法搜索例子算法搜索例子G=n0,n1,n2,n3,n4,n5G=n0,n1,n2,n3,n4,n5第三个大循环第三个大循环(扩展结点扩展结点),),直到直到n0n0是是SOLVED:SOLVED:1.1.找到待扩展的局部图找到待扩展的局部图G Gn0,n4,n5n0,n4,n52.2.n=Gn=G中非终结点中非终结点,此时此时n=n5n=n5扩展结点扩展结点n=n5,n=n5,生成后继结点集合生成后继结点集合n6,n7,n8,q(n6)=2,q(n7)=0,q(n8)=0n6,n7,n8,q(n6)=2,q(n7)=0,q(n8)=0把结点加到把结点加到G G中中1.1.小循环小循环(修改结点耗散值修改结点耗散值),),直到直到S S为空为空:a.S=n=n5 a.S=n=n5 b.b.保证保证n n的后代不在的后代不在S S中中 c.m=n5c.m=n5的连接符有两条的连接符有两条,计算计算q1(m)=1+q(n6)=1+2=3q1(m)=1+q(n6)=1+2=3 q2(m)=1+q(n7)+q(n8)=2+0+0=2 q2(m)=1+q(n7)+q(n8)=2+0+0=2 令令q(m)=q(n5)=min(q1,q2)=2q(m)=q(n5)=min(q1,q2)=2 d.d.修改指针到修改指针到q2q2对应的连结符上去对应的连结符上去 e.n7,n8e.n7,n8为为SOLVED,SOLVED,则则m=n5m=n5也为也为SOLVEDSOLVED f.q(m=n5)f.q(m=n5)被修改过被修改过,则需要也对则需要也对m m的父结的父结点进行修改点进行修改,即将即将m=n5m=n5的父结点的父结点n0n0加到加到S S中中 g.g.小循环结束小循环结束5.5.大循环结束大循环结束初始节点初始节点n0n1n4n5连接符连接符1连接符连接符2n2n3q=5q=4n6n7n8q=1q=2q=5AO*算法搜索例子算法搜索例子G=n0,n1,n2,n3,n4,n5,n6,n7,n8G=n0,n1,n2,n3,n4,n5,n6,n7,n8第四个大循环第四个大循环(扩展结点扩展结点),),直到直到n0n0是是SOLVED:SOLVED:1.1.找到待扩展的局部图找到待扩展的局部图G Gn0,n4,n5,n7,n8n0,n4,n5,n7,n82.2.n=Gn=G中非终结点中非终结点,此时此时n=n4n=n4扩展结点扩展结点n=n4,n=n4,生成后继结点集合生成后继结点集合n5,n5,n8,q(n5)=2,q(n8)=0n8,q(n5)=2,q(n8)=0小循环小循环(修改结点耗散值修改结点耗散值),),直到直到S S为空为空:a.S=n=n4 a.S=n=n4 b.b.保证保证n n的后代不在的后代不在S S中中 c.m=n5c.m=n5的连接符有两条的连接符有两条,计算计算q1(m)=1+q(n5)=1+2=3q1(m)=1+q(n5)=1+2=3 q2(m)=1+q(n8)=1+0=1 q2(m)=1+q(n8)=1+0=1 令令q(m)=q(n4)=min(q1,q2)=1q(m)=q(n4)=min(q1,q2)=1 d.d.修改指针到修改指针到q2q2对应的连结符上去对应的连结符上去 e.n8e.n8为为SOLVED,SOLVED,则则m=n4m=n4也为也为SOLVEDSOLVED f.m=n4 f.m=n4也为也为SOLVED,SOLVED,则需要也对则需要也对m m的父结点的父结点进行修改进行修改,即将即将m=n1m=n1的父结点的父结点n0n0加到加到S S中中 g.g.小循环结束小循环结束5.5.大循环结束大循环结束初始节点初始节点n0n1n4n5连接符连接符1连接符连接符2n2n3q=5n6n7n8q=2q=5q=1 在重新计算在重新计算n0n0耗散的小循环中耗散的小循环中:由于由于n4,n5n4,n5为为SOLVED,SOLVED,则则n0n0为为SOLVEDSOLVEDq(n0)=5,q(n0)=5,找到解找到解 AO*AO*算法的最优性算法的最优性:若若s s N N存在解图存在解图,当当h(n)h*(n),h(n)h*(n),且且h(n)h(n)满足单调限制条件满足单调限制条件,则则AO*AO*一定能够找到最佳解图一定能够找到最佳解图,即即AO*AO*具有可采纳性具有可采纳性 单调限制条件指对于图中从结点到单调限制条件指对于图中从结点到n nn1,n1,nk,nk的每一个连接符都的每一个连接符都施加限制施加限制h(n)C+h(n1)+.+h(nk),h(n)C+h(n1)+.+h(nk),如果同时有如果同时有h(ti)=0(tiN),h(ti)=0(tiN),那那么单调限制意味着么单调限制意味着h h是是h*h*的下界范围的下界范围,即对所有的结点即对所有的结点n n有有h(n)h*(n)h(n)h*(n)