资源描述：
《人工智能4与或图搜索ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章与或图的搜索目标目标初始节点与或图（树）表示问题三解梵塔问题ABC123三解梵塔问题(1,1,1)→(3,3,3)(1,1,1)→(1,2,2)(1,2,2)→(3,2,2)(3,2,2)→(3,3,3)(1,1,1)→(1,1,3)(1,1,3)→(1,2,3)(1,2,3)→(1,2,2)(3,2,2)→(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)(1,1,1)A,B,C3.1与或图初始节点与或图目标目标初始节点基本概念与或图是一个超图，节点间通过连接符连接。K-连接符：…...K个与或耗散值的计算k(
2、n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集Cn为连接符的耗散值…...i个nn1n2ni目标目标初始节点解图：能解节点终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。不能解节点没有后裔的非终节点是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才能解。3.2与或图启发式搜索算法AO*目标目标初始节
3、点与或图的启发式搜索算法AO*算法105-106两个过程：图生成过程，即扩展节点计算耗散值的过程AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n8目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)红色：4=1+1+1+1黑色：3=2+1目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黑色
4、：6n1n2(4)n3(4)5目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黑色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黑色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)213.3博弈树(Gametree)搜索3.3博弈树(Gametree)搜索20世纪60年代，研制出的西洋跳棋和国际象棋的博弈程序达到了大师级的水平。1958约翰•麦卡锡提出博弈树搜索算法1997年，IB
5、M公司研制的“深蓝”国际象棋程序，采用博弈树搜索算法，该程序战胜了国际象棋世界冠军卡斯帕罗夫。1.概述博弈问题特点：双人对弈，轮流走步。信息完备，双方所得到的信息是一样的。零和，即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利或无利的棋。1.概述博弈的特性两个棋手交替地走棋；比赛的最终结果，是赢、输和平局中的一种；可用图搜索技术进行，但效率很低；博弈的过程，是寻找置对手于必败态的过程；双方都无法干预对方的选择。1.概述2.Grundy博弈下棋的双方是对立的，命名博弈的双方，一方为“正方”，这类节点称为“MAX”节点；另一方为“反方”
6、，这类节点称为“MIN”节点。正方和反方是交替走步的，因此MAX节点和MIN节点会交替出现。2.Grundy博弈Grundy博弈是一个分钱币的游戏。有一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如，选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去，直到有一位选手无法把钱币再分成不相等的两堆时就得认输。2.Grundy博弈设初始状态为(7，MIN)，建立问题的状态空间图，图中所有终结点均表示该选手必输的情况，取胜方的目标是设法使棋局发展为结束在对方走步时的终结点上。（7）（
7、6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）对方-min先走我方-max胜ABC2.Grundy博弈有向图中有四个出度为零的结点:A,B,C结点A是MAX(我方)的搜索目标，而结点B，C则为MIN(对方)的搜索目标。2.Grundy博弈搜索策略要考虑的问题是：对MIN走步后的每一个MAX结点，必须证明MAX对MIN可能走的每一个棋局对弈后能获胜，即MAX必须考虑应付MIN的所有招法
8、，这是一个与的含意，因此含有MAX符号的结点可看成与结点。2.Grundy博弈对MAX走步后的每一个MIN结点，只须证明MAX有一步能走赢就可以，即MAX只要考虑能
