人工智能与或图搜索23

1、2.1 与或图(AND/OR Graph)的搜索为严格描述AND/OR图，我们先推广弧的概念。在有向图中的弧是从一个父亲节点指向它的儿子节点的。 在AND/OR图中使用的弧叫做超弧，一个超弧可以把一个父亲节点和k个儿子节点同时连接起来，这样的弧也叫做k连弧，在AND/OR图中，k连弧用弧线连接起来。当k=1时，k连弧退化成通常的有向图中的弧。 k连弧一般的弧弧n7n6n3n0n1n4n2n5n8与或图n5n1n3n6n7n8n5n0n7n8n4n0三个解图图n5n7n8n4n0在定义中中假定AND/OR图不含回回路，即即是说， 图中中不存在在一个节节点的后后裔也是是这个节节点的祖祖先的情情形。

2、不不含回回路保证证了节点点间具有有部分序序关系， 从而而保证了了下面定定义的合合理性。设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中的的一个

3、节节点，则则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

4、图图的启发发搜索过过程AO*1.建建立一个个只由根根节点s构成的的搜索图图G,设设从s 出发发的解图图的费用用为q(s)=h(s),如如果s是目标标节点， 用SOLVED标标记s.2.untils 被标标上SOLVED,do:3.begin4.通通过跟跟踪从s出发的的有标记记的超弧弧计算候候选解图图G(这些标标记在后后 面的的步骤11中给给出)5.在在G中选一一个不是是目标节节点的叶叶节点n,6.扩扩展节节点n, 产生生节点n的所有有儿子n1, n2,., nk,并并把这这些儿子子连到图图G上,对于每每一个不不曾在G中出现现的儿子子nj, 设q(nj)=h(nj),如如果这这些儿子子节点中中的

5、某些些节点是是目标节节点,则则把这些些节点标标记为SOLVED.7.建立一个个由n构成的单单元素集集合S.8.直到S变空, do:9.begin10.从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)的最小者者，标标记实现现这个最最小值的的超弧，如果本本次标记记与以前前的标记记不同， 擦去去以

6、前的的标记， 如果果这些超超弧指向向的所有有儿子节节点都标标记了SOLVED,则把m也标上SOLVED.12.如果m标记了SOLVED或者m修改后的的费用与与以前的的费用不不同，则则把m通过标记记的超弧弧连接的的父亲节节点加入入到S中，13end14.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,n1n5n41215,n0n1n

7、5n451n2,4n7,03,n04n8,0n6,25,n0n1n5n451n2,4n7,0n8,0n6,2n3,422一次循环环后二次循环环后三次循环环后四次循环环后图3.5AO*搜索算法法的例子子n1n5n41213,n0n34n245,n0n5n41n7,0n8,02搜索得到到的解图图2.3博博弈树树的搜索索穷尽的极极大极小小过程。两个游戏者分别为MAX和MIN, MAX想取得高高的分数数，而而MIN想取得低低的分数数，把整整个棋的的状态以以及所有有可能的的移动都都用一个个有与或或图表示示出来， 对于于某一游游戏者求求出他的的解图，就是为为游戏者者制定的的赢的策策略。Nim游戏，桌桌子上

8、有有 7枚枚硬币币，由由MAX和MIN两个人分分别把一一堆硬币币分成不不相等的的两堆，谁不能能继续做做下去，谁就算算输，为为MAX制定一个个赢的策策略。知识表示示，二二元组s,p,其中s为一集合合，表表示桌面面上各堆堆的硬币币数，p表示对当当前状态态应该移移动的游游戏者。例如（2，3，2，MAX）表示现在在桌面上上有3 堆硬硬币，分分别为为2，3，2个， 此时时应抡到到MAX移动。1固定深度度的极大大极小过过程。实际的游游戏的状状态空间间是非常常大的， 例如如国际象象棋有10120个状态， 要想想把所有有状态都都列出来来，实实际上是是做不到到的，改改进的的处理方方法是在在当前状状态下把把游戏扩

9、扩展到某某一固定定的深度度，对对这个深深度的树树的叶节节点进行行状态估估值，然然后分别别逐层地地以取极极大和取取极小的的方式上上传，最最终给给出对游游戏者移移动的最最佳建议议例例；九九宫游戏戏估估值值函数：MAX所能占据据的行， 列和和对角线线数-MAX所能占据据的行， 列和和对角线线数如果MAX赢，为为无穷大大如果MIN赢，为为05-4=1两步棋的的例子SJIHGFEDABCMAX取极大值值MIM取极小值值MAX(-2)(-2)(0)(0)(-6)(9)(-4)(-3)(-4)(-2)(-6)MAX的移动过程MINMAX:算法分为为两个阶阶段,第一阶段段用宽度度优先产产生给定定深度内内的所有

10、有节点,然后对所所有叶节节点进行行状态估估值.第二阶段段自低向向上倒推推估计值值,一层取极极小,一层去极极大.直至求出出初始节节点的估估值.MINMAX6-5=1,5-5=0,6-5=1,5-5=0,4-5=-15-6=-1,5-5=0,5-6=-1,6-6=0,4-6=-25-4=16-4=2Alpha-beta过程在固定深深度的极极大极小小过程中中，对对于一个个给定的的节点， 需要要先扩展展到给定定的深度度，然然后对叶叶节点进进行估值值，在一一层一层层地向上上返回值值，决决定最佳佳移动。 为提提高效率率，我我们可以以按深度度优先方方式，从从左边边开始， 先对对最左分支扩展展到给定定深度， 定出出极大和和极小的的取值界界限，即即alpha值和beta值，然然后一边边扩展一一边估值值，并并把估值值同alpha值和beta值相比较较，这样样就可以以省掉许许多节点点的估值值，当当然这些些节点也也不必产产生了， 因此此提高了了算法的的效率， 这就就是Alpha-beta过程。Alpha-beta剪枝的原原则1。 在任任一个MIN节点，如如果发发现了其其beta值小于或或者等于于它的一一个MAX祖先节点点的alpha值，则