人工智能与或图搜索.ppt

《人工智能与或图搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、2.1与或图(AND/ORGraph)的搜索为严格描述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到目标节点集

3、合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图的两个解图中

4、，左图的费用是8，右图的费用是7。2.2与或图的启发式搜索AND/OR图的启发搜索过程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中出现的

5、儿子nj,设q(nj)=h(nj),如果这些儿子节点中的某些节点是目标节点,则把这些节点标记为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)=

7、1,H(n6)=2,H(n7)=0,H(n8)=0,n1n5n41215,n0n1n5n451n2,4n7,03,n04n8,0n6,25,n0n1n5n451n2,4n7,0n8,0n6,2n3,422一次循环后二次循环后三次循环后四次循环后图3.5AO*搜索算法的例子n1n5n41213,n0n34n245,n0n5n41n7,0n8,02搜索得到的解图2.3博弈树的搜索穷尽的极大极小过程。两个游戏者分别为MAX和MIN,MAX想取得高的分数，而MIN想取得低的分数，把整个棋的状态以及所有可能的移动都用一

8、个有与或图表示出来，对于某一游戏者求出他的解图，就是为游戏者制定的赢的策略。Nim游戏，桌子上有7枚硬币，由MAX和MIN两个人分别把一堆硬币分成不相等的两堆，谁不能继续做下去，谁就算输，为MAX制定一个赢的策略。知识表示，二元组《s,p》,其中s为一集合，表示桌面上各堆的硬币数，p表示对当前状态应该移动的游戏者。例如（2，3，2，MAX）表示现在桌面上有3堆硬币，分别为2，3，2个，此时应抡