《搜索(与或图搜索实例ao算法)》由会员分享，可在线阅读，更多相关《搜索(与或图搜索实例ao算法)（34页珍藏版）》请在金锄头文库上搜索。
1、与或图搜索与或图表示HMBC DEFGAN父节点与节 点弧线或节 点子节 点终结点与或图是一个超图，节点间通过连 接符连接。 K-连接符：.K个与或图搜索问题目标目标初始节点sabcn0 n7,n8的3个解图目标n7目标n8初始节 点n0目标n7目标n8初始节 点n0目标n7目标n8初始节 点n0(a)(b)(c)ttttttttt（a）（b）有解节点无解节点终结点能解节点 终节点是能解节点 若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才 能解。 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。 不能解节点 没有后裔的非终节点是不能解节点。 若
2、非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能 解。 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能 解。耗散值的计算1.若n是N的一个元素, 则k(n, N) =0 2.若n是一个外向连接符指向后继结点n1,ni k(n, N) = Cn+k(n1, N)+k(ni, N)其中：N为终节点集Cn为连接符的耗散值.i个nn1n2ni搜索解图耗散值的递归计算: n0=2+k(4, N)+k(5, N)k(5, N)= min(2+k(7,N)+k(8, N),)= 2 k(4, N)= min(1+k(5, N), 1+k(8,N)= min(3
3、, 1)=1 N0= 2+1+2=5 (a)的解图耗散值为8 (b)的解图耗散值为7具有最小耗散值的解图称为最佳 解图,其值也用h*(n)标记.上例中的 h*(n)=5(c)n4n5目标n7目标n8初始节 点n0普通图搜索的情况f(n) = g(n) + h(n) 对n的评价实际是对从s经过n到目的地这条路径的评价ns与或图: 对局部图的评价目标目标初始节点abc与或图搜索:AO*算法两个过程 图生成过程，即扩展节点自顶向下, 从最优的局部途中选择一个节点扩展 计算耗散值的过程自下向顶, 对当前的局部图重新计算耗散值AO*算法搜索例子其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=
4、4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符 的耗散值为K目标目标初始节点n0n1 n2n3n4n5n6n7n8AO*算法搜索例子G中只有一个结点n0 第一个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图Gn0 2. n=G中任意结点, 此时n=n0 3. 扩展结点n=n0, 生成后继结点集合n1,n4,n5, q(n4)=1, q(n5)=1, q(n1)=2, 都不是终结点, 把结点加到G中 4. 小循环(修改结点耗散值),直到S为空:a. S=n=n0b. 保证n的后代不在S中c. m=n0的连接符有两条,计算q1(m)=1
5、+q(n1)=1+2=3q2(m)=2+q(n5)+q(n4)=2+1+1=4令q(m)=q(n0)=min(q1,q2)=3d.修改指针到q1对应的连结符上去e.如果n1为非SOLVED,则m=n0也为非SOLVEDf.如果m=n0为SOLVED,或者q(m)被修改过,则需 要也对m的父结点进行修改, 即将m的父结点加 到S中g.小循环结束 5.大循环结束初始节点n0n1n4n5连接符1连接符2q=3AO*算法搜索例子G=n0,n1,n4,n5 第二个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图Gn0,n1 2. n=G中非终结点, 此时n=n1 3. 扩展结点n=
6、n1, 生成后继结点集合n2,n3, q(n2)=4, q(n3)=4, 都不是终结点,把结点加到 G中 4. 小循环(修改结点耗散值),直到S为空:a. S=n=n1b. 保证n的后代不在S中c. m=n1的连接符有两条,计算q1(m)=1+q(n3)=1+4=5q2(m)=1+q(n2)=1+4=5令q(m)=q(n0)=min(q1,q2)=5d.修改指针到q1对应的连结符上去e.如果n3非SOLVED,则m=n1也为非SOLVEDf. q(m=n1)被修改过,则需要也对m的父结点进 行修改, 即将m=n1的父结点n0加到S中g.小循环结束 5.大循环结束初始节点n0n1n4n5连接符1
7、连接符2n2n3q=5继续小循环: c. m=n0的连接符有两条,计算q1(m)=1+h(n1)=1+5=6 q2(m)=1+h(n5)+h(4)=4令 q(m)=q(n1)=min(q1,q2)=4 d.修改指针到q2对应的连结符上去q=4q=3AO*算法搜索例子G=n0,n1,n2,n3,n4,n5 第三个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图Gn0,n4,n5 2. n=G中非终结点, 此时n=n5 3. 扩展结点n=n5, 生成后继结点集合 n6,n7,n8, q(n6)=2, q(n7)=0, q(n8)=0 把结点加到G中 4. 小循环(修改结点耗散
8、值),直到S为空:a. S=n=n5b. 保证n的后代不在S中c. m=n5的连接符有两条,计算q1(m)=1+q(n6)=1+2=3q2(m)=1+q(n7)+q(n8)=2+0+0=2令q(m)=q(n5)=min(q1,q2)=2d.修改指针到q2对应的连结符上去e.n7,n8为SOLVED,则m=n5也为SOLVEDf. q(m=n5)被修改过,则需要也对m的父结 点进行修改, 即将m=n5的父结点n0加到S中g.小循环结束 5.大循环结束初始节点n0n1n4n5连接符1连接符2n2n3q=5q=4n6n7n8q=1q=2q=5AO*算法搜索例子 G=n0,n1,n2,n3,n4,n5
9、,n6,n7,n8 第四个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图Gn0,n4,n5,n7,n8 2. n=G中非终结点, 此时n=n4 3. 扩展结点n=n4, 生成后继结点集合n5, n8, q(n5)=2, q(n8)=0 4. 小循环(修改结点耗散值),直到S为空:a. S=n=n4b. 保证n的后代不在S中c. m=n5的连接符有两条,计算q1(m)=1+q(n5)=1+2=3q2(m)=1+q(n8)=1+0=1令q(m)=q(n4)=min(q1,q2)=1d.修改指针到q2对应的连结符上去e. n8为SOLVED,则m=n4也为SOLVEDf. m
10、=n4也为SOLVED,则需要也对m的父结点 进行修改, 即将m=n1的父结点n0加到S中g.小循环结束 5.大循环结束初始节点n0n1n4n5连接符1连接符2n2n3q=5n6n7n8q=2q=5q=1在重新计算n0耗散的小循环中: 由于n4,n5为SOLVED, 则n0为SOLVED q(n0)=5, 找到解AO*算法的最优性:若s N存在解图,当h(n)h*(n),且h(n)满足单调限制条件,则AO* 一定能够找到最佳解图, 即AO*具有可采纳性单调限制条件指对于图中从结点到nn1,nk的每一个连接符都 施加限制h(n)C+ h(n1)+ h(nk),如果同时有h(ti)=0(tiN),
11、那 么单调限制意味着h是h*的下界范围,即对所有的结点n有h(n)h*(n)与或图搜索与或图表示HMBC DEFGAN父节点与节 点弧线或节 点子节 点终结点与或图是一个超图，节点间通过连 接符连接。 K-连接符：.K个与或图搜索问题目标目标初始节点sabcn0 n7,n8的3个解图目标n7目标n8初始节 点n0目标n7目标n8初始节 点n0目标n7目标n8初始节 点n0(a)(b)(c)ttttttttt（a）（b）有解节点无解节点终结点能解节点 终节点是能解节点 若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才 能解。 若非终节点有“与”子节点时，当且仅当其子节点均
12、能解时，该非终节点才能解。 不能解节点 没有后裔的非终节点是不能解节点。 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能 解。 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能 解。耗散值的计算1.若n是N的一个元素, 则k(n, N) =0 2.若n是一个外向连接符指向后继结点n1,ni k(n, N) = Cn+k(n1, N)+k(ni, N)其中：N为终节点集Cn为连接符的耗散值.i个nn1n2ni搜索解图(c)耗散值的递归计算: n0=2+k(4, N)+k(5, N)k(5, N)= min(2+k(7,N)+k(8, N),)=
13、2 k(4, N)= min(1+k(5, N), 1+k(8,N)= min(3, 1)=1 N0= 2+1+2=5 同理可计算得： (a)的解图耗散值为8 (b)的解图耗散值为7具有最小耗散值的解图称为最佳 解图,其值也用h*(n)标记.上例中的 h*(n)=5解图(c)n4n5目标n7目标n8初始节 点n0普通图搜索的情况f(n) = g(n) + h(n) 对n的评价实际是对从s经过n到目的地这条路径的评价nst与或图: 对局部图的评价目标目标初始节点abc与或图搜索:AO*算法两个过程 图生成过程，即扩展节点自顶向下, 从最优的局部途中选择一个节点扩展 计算耗散值的过程自下向顶, 对
14、当前的局部图重新计算耗散值AO*算法搜索例子其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符 的耗散值为K目标目标初始节点n0n1 n2n3n4n5n6n7n8AO*算法搜索例子G中只有一个结点n0 第一个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图Gn0 2. n=G中任意结点, 此时n=n0 3. 扩展结点n=n0, 生成后继结点集合n1,n4,n5, q(n4)=1, q(n5)=1, q(n1)=2, 都不是终结点, 把结点加到G中 4. 小循环(修改结点耗散值),
15、直到S为空:a. S=n=n0b. 保证n的后代不在S中c. 取出m=n0的连接符有两条,计算q1(m)=1+q(n1)=1+2=3q2(m)=2+q(n5)+q(n4)=2+1+1=4令q(m)=q(n0)=min(q1,q2)=3d.修改指针到q1对应的连结符上去e.如果n1为非SOLVED,则m=n0也为非SOLVEDf.如果m=n0为SOLVED,或者q(m)被修改过,则需 要也对m的父结点进行修改, 即将m的父结点加 到S中g.小循环结束 5.大循环结束初始节点n0n1n4n5连接符1连接符2q=3即h(n)AO*算法搜索例子G=n0,n1,n4,n5 第二个大循环(扩展结点),直到
16、n0是SOLVED: 1. 找到待扩展的局部图Gn0,n1 2. n=G中非终结点, 此时n=n1 3. 扩展结点n=n1, 生成后继结点集合n2,n3, q(n2)=4, q(n3)=4, 都不是终结点,把结点加到 G中 4. 小循环(修改结点耗散值),直到S为空:a. S=n=n1b. 保证n的后代不在S中c. 取出m=n1的连接符有两条,计算q1(m)=1+q(n3)=1+4=5q2(m)=1+q(n2)=1+4=5令q(m)=q(n0)=min(q1,q2)=5d.修改指针到q1对应的连结符上去e.如果n3非SOLVED,则m=n1也为非SOLVEDf. q(m=n1)被修改过,则需要也对m的父结点进 行修改, 即将m=n1的父结点n0加到S中g.小循环结束 5.大循环结束初始节点n0n1n4n5连接符1连接符2n2n3
