资源预览内容
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
第9页 / 共24页
第10页 / 共24页
亲,该文档总共24页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2.1 与或图(AND/OR Graph)的搜索,为严格描述AND/OR图,我们先推广弧的概念。在有向图中的弧是从一个父亲节点指向它的儿子节点的。 在AND/OR图中使用的弧叫做超弧,一个超弧可以把一个父亲节点和k个儿子节点同时连接起来,这样的弧也叫做k连弧,在AND/OR图中,k连弧用弧线连接起来。当k=1时,k连弧退化成通常的有向图中的弧。,k连弧,一般的弧,n7,n6,n3,n0,n1,n4,n2,n5,n8,与或图,n5,n1,n3,n6,n7,n8,n5,n0,n7,n8,n4,n0,三个解图,n5,n7,n8,n4,n0,在定义中假定AND/OR图不含回路,即是说, 图中不存在一个节点的后裔也是这个节点的祖先的情形。 不含回路保证了节点间具有部分序关系, 从而保证了下面定义的合理性。 设N是AND/OR图G的目标节点集合, 从图中任意一个节点n出发到N的一个解图是AND/OR图G的一个子图, 用G表示, 递归定义如下: 如果n是N中的一个节点, 则G只包括n. 如果n有一条从n出发的k连弧ai, 这个k连弧连接的儿子节点是n1, n2, ., nk, 则解图G由节点n, k连弧ai, 和由n1, n2, ., nk出发的解图构成。 否则, G没有从n出发到N的解图。,与或图,设从节点n到目标节点集合N的费用用c(n, N)表示, 则c(n, N)定义如下: 如果n是N中的一个节点, 则c(n, N)=0, 如果n有一条从n出发的k连弧ai, 这个k连弧连接的儿子节点是n1, n2, ., nk, 则解图G由节点n, k连弧ai, 和由n1, n2, ., nk出发的解图构成。这时,解图G的费用定义为 c(n, N)= c(ai)+ c(n, n1)+ c(n, nk), 其中c(ai)是k连弧ai的费用. 否则, G没有从n出发到N的解图。设其费用为无穷大.。 例如,如果假定k连弧的费用是k, 则图3.4 所示的 AND/OR图的两个解图中,左图的费用是8, 右图的费用是7。,2.2 与或图的启发式搜索,AND/OR图的启发搜索过程AO* 1. 建立一个只由根节点s构成的搜索图G, 设从s 出发的解图的费用为q(s)=h(s), 如果s是目标节点, 用SOLVED标记s. 2. until s 被标上SOLVED, do: 3. begin 4. 通过跟踪从s出发的有标记的超弧计算候选解图G(这些标记在后 面的步骤11中给出) 5. 在G中选一个不是目标节点的叶节点n, 6. 扩展节点n, 产生节点n的所有儿子n1, n2, ., nk, 并把这些儿子连到图G上,对于每一个不曾在G中出现的儿子nj, 设q(nj)=h(nj), 如果这些儿子节点中的某些节点是目标节点,则把这些节点标记为SOLVED.,7. 建立一个由n构成的单元素集合S. 8. 直到 S变空, do: 9. begin 10. 从S中删除其儿子节点不在S中的节点, 记此节点为m. 按以下步骤修改m的费用q(m), 对于每一个从m出发的 指向节点集合ni1, ni2, ., nik超弧ai,计算qi(m)= c(ai)+ q(ni1)+ q(nik), 这里的q( nij)或者是在本循环内部的前面步骤计算出的值,或者是在步骤6中指定的值。 设q(m)是所有qi(m)的最小者, 标记实现这个最小值的超弧,如果本次标记与以前的标记不同, 擦去以前的标记, 如果这些超弧指向的所有儿子节点都标记了SOLVED, 则把m也标上SOLVED. 12. 如果m标记了SOLVED或者m修改后的费用与以前的费用不同, 则把m通过标记的超弧连接的父亲节点加入到S中, 13 end 14. end,算法分为两个阶段 1. 4-6 步. 自顶向下的产生候补解图, 并扩展候补解图的过程. 2. 7-12, 自底向上修正费用值, 标记弧及的过程. 例 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,n1,n5,n4,1,2,1,5, n0,n1,n5,n4,5,1,n2,4,n7,0,3, n0,4,n8,0,n6,2,5, n0,n1,n5,n4,5,1,n2,4,n7,0,n8,0,n6,2,n3, 4,2,2,一次循环后,二次循环后,三次循环后,四次循环后,图3.5 AO*搜索算法的例子,n1,n5,n4,1,2,1,3, n0,n3,4,n2,4,5, n0,n5,n4,1,n7,0,n8,0,2,搜索得到的解图,2.3 博弈树的搜索 穷尽的极大极小过程。 两个游戏者分别为MAX 和MIN, MAX想取得高的分数, 而MIN想取得低的分数,把整个棋的状态以及所有可能的移动都用一个有与或图表示出来, 对于某一游戏者求出他的解图,就是为游戏者制定的赢的策略。 Nim 游戏,桌子上有 7 枚硬币, 由MAX 和MIN两个人分别把一堆硬币分成不相等的两堆,谁不能继续做下去,谁就算输, 为MAX制定一个赢的策略。 知识表示, 二元组s, p,其中s为一集合, 表示桌面上各堆的硬币数, p表示对当前状态应该移动的游戏者。例如 (2,3,2, MAX)表示现在桌面上有 3 堆硬币, 分别为2, 3, 2个, 此时应抡到MAX移动。,1,固定深度的极大极小过程。 实际的游戏的状态空间是非常大的, 例如国际象棋有 10120个状态, 要想把所有状态都列出来, 实际上是做不到的, 改进的处理方法是在当前状态下把游戏扩展到某一固定的深度, 对这个深度的树的叶节点进行状态估值,然后分别逐层地以取极大和取极小的方式上传, 最终给出对游戏者移动的最佳建议 例; 九宫游戏 估值函数: MAX所能占据的行, 列和对角线数 - MAX所能占据的行, 列和对角线数,如果MAX赢, 为无穷大 如果MIN赢, 为0 5-4=1,两步棋的例子,S,J,I,H,G,F,E,D,A,B,C,MAX取极大值,MIM取极小值,MAX,(-2),(-2),(0),(0),(-6),(9),(-4),(-3),(-4),(-2),(-6),MAX的移动,过程MINMAX: 算法分为两个阶段, 第一阶段用宽度优先产生给定深度内的所有节点, 然后对所有叶节点进行状态估值. 第二阶段自低向上倒推估计值, 一层取极小, 一层去极大. 直至求出初始节点的估值.,MIN,MAX,6-5=1, 5-5=0, 6-5=1, 5-5=0,4-5=-1,5-6=-1, 5-5=0, 5-6=-1, 6-6=0,4-6=-2,5-4=1 6-4=2,Alpha-beta 过程 在固定深度的极大极小过程中, 对于一个给定的节点, 需要先扩展到给定的深度, 然后对叶节点进行估值,在一层一层地向上返回值, 决定最佳移动。 为提高效率, 我们可以按深度优先方式, 从左边开始, 先对最左分支扩展到给定深度, 定出极大和极小的取值界限,即alpha值和beta值, 然后一边扩展一边估值, 并把估值同alpha值和beta值相比较,这样就可以省掉许多节点的估值, 当然这些节点也不必产生了, 因此提高了算法的效率, 这就是Alpha-beta 过程。,Alpha-beta剪枝的原则 1。 在任一个MIN节点, 如果发现了其beta值小于或者等于它的一个MAX祖先节点的alpha值,则可以剪枝 2。 在任一个MAX 节点下, 如果发现了其alpha值大于或者等于它的一个MIN祖先节点的bata值,则可以剪枝,2,5,3,1,2,0,3,3,3,MAX,MIN,MAX,0,2,MIN,图3.8 alpha-beta剪枝过程,0 5 -3 3 3 -3 0 2 2 -3 0 -2 3 5 4 1 -3 0 6 8 9 -3,MAX,最佳移动,=0,=0,=0,=0,=0,=1,=-3,=1,=6,=1,演讲完毕,谢谢观看!,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号