人工智能与或图搜索课件

,#,人工智能,吉林大学珠海学院计算机科学与技术系,2.1 与或图(AND/OR Graph)的搜索,为严格描述AND/OR图，我们先推广弧的概念。在有向图中的弧是从一个父亲节点指向它的儿子节点的。在AND/OR图中使用的弧叫做超弧，一个超弧可以把一个父亲节点和k个儿子节点同时连接起来，这样的弧也叫做k连弧，在AND/OR图中，k连弧用弧线连接起来。当k=1时，k连弧退化成通常的有向图中的弧。,2.1 与或图(AND/OR Graph)的搜索为严格描述,1,k连弧,一般的弧,k连弧一般的弧,2,n7,n6,n3,n0,n1,n4,n2,n5,n8,与或图,n7n6n3n0n1n4n2n5n8与或图,3,n,5,n,1,n,3,n,6,n,7,n,8,n,5,n,0,n,7,n,8,n,4,n,0,三个解图,n,5,n,7,n,8,n,4,n,0,n5n1n3n6n7n8n5n0n7n8n4n0三个解图n5,4,在定义中假定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的解图。,在定义中假定AND/OR图不含回路，即是说，图中不存在一个,5,与或图,设从节点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。,与或图设从节点n到目标节点集合N的费用用c(n,N)表示，,6,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.,2.2 与或图的启发式搜索AND/OR图的启发搜索过程AO*,7,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,7.建立一个由n构成的单元素集合S.,8,算法分为两个阶段,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,算法分为两个阶段,9,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,n1n5n41215,n0n1n5n451n2,4n7,0,10,5,n0,n5,n4,1,n7,0,n8,0,2,搜索得到的解图,5,n0n5n41n7,0n8,02搜索得到的解图,11,2.3 博弈树的搜索,穷尽的极大极小过程。,两个,游戏者,分别为,MAX 和MIN,MAX想取得高的分数，而MIN想取得低的分数，把整个棋的状态以及所有可能的移动都用一个有与或图表示出来，对于某一游戏者求出他的解图，就是为游戏者制定的赢的策略。,Nim,游戏，桌子上有 7 枚硬币，由,MAX 和MIN两个人分别把一堆硬币分成不相等的两堆，谁不能继续做下去，谁就算输，为MAX制定一个赢的策略。知识表示，二元组s,p,其中s为一集合，表示桌面上各堆的硬币数，p表示对当前状态应该移动的游戏者。例如 （2，3，2，MAX）表示现在桌面上有 3 堆硬币，分别为2，3，2个，此时应抡到MAX移动。,2.3 博弈树的搜索 穷尽的极大极小过程。两个游,12,1,1,13,固定深度的极大极小过程。,实际的游戏的状态空间是非常大的，例如国际象棋有 10,120,个状态，要想把所有状态都列出来，实际上是做不到的，改进的处理方法是在当前状态下把游戏扩展到某一固定的深度，对这个深度的树的叶节点进行状态估值，然后分别逐层地以取极大和取极小的方式上传，最终给出对游戏者移动的最佳建议 例；九宫游戏 估值函数：,MAX,所能占据的行，列和对角线数-MAX所能占据的行，列和对角线数,如果MAX赢，为无穷大,如果MIN赢，为0,5-4=1,固定深度的极大极小过程。实际的游戏的状态空间是非常大,14,两步棋的例子,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的移动,两步棋的例子SJIHGFEDABCMAX取极大值MIM取极小,15,过程MINMAX:,算法分为两个阶段,第一阶段用宽度优先产生给定深度内的所有节点,然后对所有叶节点进行状态估值.第二阶段自低向上倒推估计值,一层取极小,一层去极大.直至求出初始节点的估值.,过程MINMAX:,16,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,MINMAX6-5=1,5-5=0,6-5=1,5-,17,18,Alpha-beta,过程,在固定深度的极大极小过程中，对于一个给定的节点，需要先扩展到给定的深度，然后对叶节点进行估值，在一层一层地向上返回值，决定最佳移动。为提高效率，我们可以按深度优先方式，从左边开始，先对最左分支扩展到给定深度，定出极大和极小的取值界限，即alpha值和beta值，然后一边扩展一边估值，并把估值同alpha值和beta值相比较，这样就可以省掉许多节点的估值，当然这些节点也不必产生了，因此提高了算法的效率，这就是Alpha-beta 过程。,Alpha-beta 过程 在固定深度的极大极小过程中，,19,20,Alpha-beta剪枝的原则 1。在任一个MIN节点，如果发现了其beta值小于或者等于它的一个MAX祖先节点的alpha值，则可以剪枝 2。在任一个MAX 节点下，如果发现了其alpha值大于或者等于它的一个MIN祖先节点的bata值，则可以剪枝,Alpha-beta剪枝的原则 1。在任一个MIN节点，,21,2,5,3,1,2,0,3,3,3,MAX,MIN,MAX,0,2,253120333MAXMINMAX02,22,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,MIN图3.8 alpha-beta剪枝过程,23,等待是失败的源头，行动是成功的开始。,11月-24,11月-24,Wednesday,November 13,2024,安全用电，节约用水，消防设施，定期维护。,20:48:33,20:48:33,20:48,11/13/2024 8:48:33 PM,事故教训是镜子，安全经验是明灯。,11月-24,20:48:33,20:48,Nov-24,13-Nov-24,跨越今日的视野，扩展,21,世纪的眼光。,20:48:33,20:48:33,20:48,Wednesday,November 13,2024,多一份防范意识，少一份生命危险。,11月-24,11月-24,20:48:33,20:48:33,November 13,2024,灾害常生于疏忽，祸患多起于细末。,2024年11月13日,8:48 下午,11月-24,11月-24,减少浪费，降低成本，气氛融洽，工作规范，提升品质，安全保证。,13 十一月 2024,8:48:33 下午,20:48:33,11月-24,神是责任，安全的方针是第一。,十一月 24,8:48 下午,11月-24,20:48,November 13,2024,关爱生命，关注安全。,2024/11/13 20:48:33,20:48:33,13 November 2024,仪器设备勤保养，生产自然更顺畅。,8:48:33 下午,8:48 下午,20:48:33,11月-24,该说说到，说到做到，做到有效。,11月-24,11月-24,20:48,20:48:33,20:48:33,Nov-24,品质是生产出来的，不是靠检验出来的。,2024/11/13 20:48:33,Wednesday,November 13,2024,质量就是效益。,11月-24,2024/11/13 20:48:33,11月-24,谢谢大家！,等待是失败的源头，行动是成功的开始。9月-239月-23Fr,24,