人工智能之与或图搜索问题.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第二章 与或图搜索问题,目标,目标,初始节点s,a,b,c,1,人工智能之与或图搜索问题,第1页,2.1 基本概念,与或图是一个超图，节点间经过连接符连接。,K-连接符：,.,K,个,2,人工智能之与或图搜索问题,第2页,耗散值计算,k(n,N)=,C,n+k(,n,1,N)+k(,n,i,N),其中：N为终节点集,C,n为连接符耗散值,.,i,个,n,n,1,n,2,n,i,3,人工智能之与或图搜索问题,第3页,目标,目标,初始节点,解图：,4,人工智能之与或图搜索问题,第4页,能解节点,终节点是能解节点,若非终节点有“或”子节点时，当且仅当其子节点最少有一能解时，该非终节点才能解。,若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。,5,人工智能之与或图搜索问题,第5页,不能解节点,没有后代非终节点是不能解节点。,若非终节点有“或”子节点，当且仅当全部子节点均不能解时，该非终节点才不能解。,若非终节点有“与”子节点时，当最少有一个子节点不能解时，该非终节点才不能解。,6,人工智能之与或图搜索问题,第6页,普通图搜索情况,f(n)=g(n)+h(n),对n评价实际是对从s到n这条路径评价,n,s,7,人工智能之与或图搜索问题,第7页,与或图:对局部图评价,目标,目标,初始节点,a,b,c,8,人工智能之与或图搜索问题,第8页,两个过程,图生成过程，即扩展节点,从最优局部途中选择一个节点扩展,计算耗散值过程,对当前局部图从新计算耗散值,9,人工智能之与或图搜索问题,第9页,AO*算法举例,其中：,h(n,0,)=3,h(n,1,)=2,h(n,2,)=4,h(n,3,)=4,h(n,4,)=1,h(n,5,)=1,h(n,6,)=2,h(n,7,)=0,h(n,8,)=0,设：K连接符,耗散值为K,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,10,人工智能之与或图搜索问题,第10页,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,初始节点,n,0,n,1,(2),n,4,(1),n,5,(1),红色：4,黄色：3,11,人工智能之与或图搜索问题,第11页,初始节点,n,0,n,4,(1),n,5,(1),红色：4,黄色：6,n1,n,2,(4),n,3,(4),5,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,12,人工智能之与或图搜索问题,第12页,红色：5,黄色：6,初始节点,n,0,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5,n,6,(2),n,7,(0),n,8,(0),2,目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,13,人工智能之与或图搜索问题,第13页,红色：5,黄色：6,2,1,初始节点,n,0,n,4,(1),n,5,(1),n,1,n,2,(4),n,3,(4),5n,6,(2),n,7,(0),n,8,(0),目标,目标,初始节点,n,0,n,1,n,2,n,3,n,4,n,5,n,6,n,7,n,8,14,人工智能之与或图搜索问题,第14页,博弈,是一类含有竞争性智能活动,双人博弈,：即两位选手对垒，轮番依次走步，其中任何一方都完全知道对方过去已经走过棋步和今后可能走步，其结果是一方赢,(,而另一方则输,),，或双方和局,2.3 博弈树搜索,15,人工智能之与或图搜索问题,第15页,博弈例子,：,一字棋,跳棋,中国象棋,围棋,五子棋,16,人工智能之与或图搜索问题,第16页,2.3 博弈树搜索,博弈问题,双人对弈，对垒双方轮番走步；,信息完备，对垒双方所得到信息是一样，不存在一方能看到，而另外一方看不到情况；,零和，即对一方有利棋，对另一方必定是不利，不存在对双方都有利或均无利棋，对弈结果是一方赢，而另一方输，或者双方和棋。,17,人工智能之与或图搜索问题,第17页,双方智能活动，任何一方都不能单独控制博弈过程，而是由双方轮番实施其控制对策过程。,博弈特点：,18,人工智能之与或图搜索问题,第18页,怎样依据当前棋局，选择对自己最有利一步棋？,人工智能中研究博弈问题,：,中国象棋,19,人工智能之与或图搜索问题,第19页,用博弈树来表示，它是一个特殊,与或树,。节点代表博弈格局（即棋局），相当于状态空间中状态，反应了博弈信息，,而且与节点、或节点隔层交替出现。,博弈问题（求解过程）表示,：,20,人工智能之与或图搜索问题,第20页,假设博弈双方为：MAX和MIN,在博弈过程中，规则是双方轮番走步。在博弈树中，相当于博弈双方轮番扩展其所属节点。,为何与节点、或节点隔层交替出现,？,21,人工智能之与或图搜索问题,第21页,从,MAX,方角度来看,：,全部,MIN,方节点都是,与节点,理由,：,因为,MIN,方必定选择最不利于,MAX,方方式来扩展节点，只要,MIN,方节点子节点（下出棋局）中有一个对,MAX,方不利，则该节点就对,MAX,方不利，故为“,与节点,”。,MIN,好招,22,人工智能之与或图搜索问题,第22页,从,MAX,方角度来看,：,全部属于,MAX,方节点都是,或节点,理由,：,因为扩展,MAX,方节点时，,MAX,方可选择扩展最有利于自己节点，只要可扩展子节点中有一个对已经有利，,则该节点就对已经有利。,MAX,好招,23,人工智能之与或图搜索问题,第23页,总之：,从,MAX,方来说，与节点、或节点交替出现；反之，从,MIN,方角度来看，情况恰好相反。,24,人工智能之与或图搜索问题,第24页,在博弈树中，先行一方初始状态对应着树,根节点,，而任何一方获胜最终格局为目标状态，对应于树,终叶节点,（可解节点或本原问题）。,不过，从,MAX,角度出发，全部使,MAX,获胜状态格局都是本原问题，是,可解节点,，而使,MIN,获胜状态格局是,不可解节点,。,25,人工智能之与或图搜索问题,第25页,博弈树特点,(1)博弈初始状态是初始节点；,(2)博弈树“与”节点和“或”节点是逐层交替出现；,(3)整个博弈过程一直站在某一方立场上，所以能使自己一方获胜终局都是本原问题，对应节点也是可解节点，全部使对方获胜节点都是不可解节点。,26,人工智能之与或图搜索问题,第26页,例,Grundy,博弈：分配物品问题,假如有一堆数目为,N,钱币，由两位选手轮番进行分配，要求每个选手每次把其中某一堆分成数目,不等,两小堆，直至有一选手不能将钱币分成不等两堆为止，则判定这位选手为输家。,27,人工智能之与或图搜索问题,第27页,用数字序列加上一个说明来表示一个状态：,(,3,2,1,1,MAX,),数字序列,：表示不一样堆中钱币个数,说明,：表示下一步由谁来分，即取,MAX,或,MIN,28,人工智能之与或图搜索问题,第28页,现在取,N,7 简单情况,，并由,MIN,先分,注,：,假如MAX走红箭头分法，必定获胜。,全部可能分法,(7,MIN),(6,1,MAX),(5,2,MAX),(4,3,MAX),(5,1,1,MIN),(4,2,1,MIN),(3,2,2,MIN),(3,3,1,MIN),(4,1,1,1,MAX),(3,2,1,1,MAX),(2,2,2,1,MAX),(2,2,11,1,MIN),(3,1,1,1,1,MIN),(2,1,1,1,1,1,MAX),29,人工智能之与或图搜索问题,第29页,分钱币问题,（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）,对方先走,我方必胜,30,人工智能之与或图搜索问题,第30页,对于比较复杂博弈问题，只能模拟人思维,“,向前看几步,”,，然后作出决议，选择最有利自己一步。即,只能给出几层走法，然后按照一定估算方法，,决定走一好招31,人工智能之与或图搜索问题,第31页,中国象棋,一盘棋平均走50步，总状态数约为10161次方。,假设1毫微秒走一步，约需10145次方年。,结论：不可能穷举。,32,人工智能之与或图搜索问题,第32页,在人工智能中能够采取搜索方法来求解博弈问题，下面就来讨论博弈中两中最基本搜索方法。,33,人工智能之与或图搜索问题,第33页,对于复杂博弈问题，要要求搜索深度与时间，方便于博弈搜索能顺利进行。,假设由,MAX,来选择走一步棋，问题是：,MAX,怎样来选择一步好棋,？,极大极小过程,34,人工智能之与或图搜索问题,第34页,极大极小过程,极大极小过程是考虑双方对弈若干步之后，从可能走法中选一步相对好走法来走，即在有限搜索深度范围内进行求解。,需要定义一个静态估价函数e,方便对棋局态势做出评定。,35,人工智能之与或图搜索问题,第35页,对于每一格局（棋局）给出（定义或者倒推）一个静态估价函数值。值越大对MAX越有利，反之越不利；,极大极小过程基本思绪,：,36,人工智能之与或图搜索问题,第36页,对于给定格局，,MAX,给出可能走法，然后,MIN,对应地给出对应走法，这么重复若干次，得到一组端节点（必须由,MIN,走后得到，等候,MAX,下棋局）。这一过程相当于节点扩展；,注,：博弈树深度或层数一定是偶数。,37,人工智能之与或图搜索问题,第37页,对于每一个端节点，计算出它们静态估价函数，然后自下而上地逐层计算倒推值，直到MAX开始格局。在MIN下格局中取估值最小值，在MAX下格局中取估值最大值；,取估值最大格局作为,MAX,要走一招棋。,38,人工智能之与或图搜索问题,第38页,例,：,向前看一步两层博弈树,39,人工智能之与或图搜索问题,第39页,定义静态函数e(P)普通标准,：,40,人工智能之与或图搜索问题,第40页,OPEN,：存放待扩展节点，此时为队列，即以宽度优先策略扩展节点。,CLOSED,：存放已扩展节点，此时为堆栈，即后扩展节点先计算。,符号,：,41,人工智能之与或图搜索问题,第41页,极大极小过程基本思想：,(1)当轮到MIN走步节点时，MAX应考虑最坏情况（即f(p)取极小值）；,(2)当轮到MAX走步节点时，MAX应考虑最好情况（即f(p)取极大值）；,(3)评价往回倒推时，对应于两位棋手反抗策略，交替使用（1）和（2）两种方法传递倒推值。,42,人工智能之与或图搜索问题,第42页,1,、将初始节点,S,放入,OPEN,表中，开始时搜索树,T,由初始节点,S,组成；,2,、若,OPEN,表为空（,节点扩展结束,），则转5；,3,、将,OPEN,表中第一个节点,n,移出放,入,CLOSED,表前端；,极大极小搜索过程,为,：,43,人工智能之与或图搜索问题,第43页,4,、若,n,可直接判定为赢、输、或平局，则令对应,e,(n,)=，-或 0，并转2；不然扩展,n,，产生,n,后继节点集,n,i,，将,n,i,放入搜索树 T 中。此时，若搜索深度,d,n,i,小于预先设定深度,k,，则将,n,i,放入OPEN表末端，转2；不然，,n,i,到达深度,k,，计算,e,(,n,i,)，并转2；,44,人工智能之与或图搜索问题,第44页,5,、若,CLOSED,表为空，则转8；不然取出,CLOSED,表中第一个节点，记为,n,p,；,Open为空，即已经扩展完节点,步2,45,人工智能之与或图搜索问题,第45页,6,、若,n,p,属于,MAX,层，且对于它属于,MIN,层子节点,n,ci,e,(,n,ci,)有值，则：e,(,n,p,)=max,n,ci,46,人工智能之与或图搜索问题,第46页,（续）,若,n,p,属于,MIN,层，且对于它属于,MAX,层子节点,n,ci,e,(,n,ci,)有值，则：,e,(,n,p,)=min,n,ci,47,人工智能之与或图搜索问题,第47页,7,、转5；,8,、依据,e,(S),值，标识走步或者结束（-，或 0）。,48,人工智能之与或图搜索问题,第48页,第一阶段,为1、2、3、4步，用宽度优先算法生成要求深度,k,全部博弈树，然后对其全部端节点计算 e(P)；,第二阶段,为5、6、7、8步，是自下而上逐层求节点倒推估价值，直至求出初始节点 e(S)为止，再由 e(S)选得相对很好走法，过程结束。,算法分成两个阶段,：,49,人工智能之与或图搜索问题,第49页,等对手走出对应棋，再以当前格局作为初始节点，重复此过程，选择对自己有利走法。,50,人工智能之与或图搜索问题,第50页,极大极小过程,51,人工智能之与或图搜索问题,第51页,例,：,一字棋极大极小搜索过程,约定,：,每一方只向前看一步,（扩展出二层）,记,MAX,棋子为“,”，,MIN,棋子为“,O,”,要求,MAX,先手,52,人工智能之与或图搜索问题,第52页,若格局 P 对任何一方都不能获胜，则,e(P)=（,全部空格上都放上MAX棋子后，MAX三个棋子所组成行、列及对角线总数,）-全部空格上都放上MIN棋子后，MIN三个棋子所组成行、列及对角线总数,）,静态预计函数e(P)定义为,：,53,人工智能之与或图搜索问题,第53页,若 P 是MAX获胜，则,e(P)=+,若 P 是MIN获胜，则,e(P)=,54,人工智能之与或图搜索问题,第54页,例：,计算以下棋局静态估价函数值,e(P)=6-4=2,棋局,O,O,O,O,O,O,O,O,O,O,行=2,列=2,对角=2,行=2,列=2,对角=0,55,人工智能之与或图搜索问题,第55页,利用棋盘对称性，有些棋局是等价,O,O,O,O,56,人工智能之与或图搜索问题,第56页,O,O,O,O,O,O,O,O,O,O,OO,1,0,1,0,-1,-1,0,-1,0,-2,1,2,1,-2,-1,1,MAX,MIN,MAX,MAX走步,57,人工智能之与或图搜索问题,第57页,第二步,O,X,X,O,X,O,X,X,O,X,X,O,X,X,X,O,O,X,X,O,O,X,X,O,X,O,X,O,X,O,X,O,X,O,2,1,3,2,1,1,O,O,X,X,O,X,X,O,O,X,X,O,O,X,X,O,O,X,X,O,1,0,2,0,1,O,O,X,X,1,0,O,O,X,X,O,O,X,X,O,O,X,X,O,X,O,X,O,X,X,O,O,X,X,O,2,2,3,1,2,2,1,O,O,X,X,O,X,O,X,O,O,X,X,1,1,0,0,1,58,人工智能之与或图搜索问题,第58页,第三步,O,O,X,X,X,O,O,X,X,O,O,X,X,X,O,O,X,X,X,O,O,X,X,X,O,O,X,X,X,X,O,O,O,X,X,X,O,O,X,X,O,X,O,O,X,X,O,X,O,O,X,O,X,O,O,O,X,X,X,O,O,O,X,X,X,O,O,X,X,X,O,O,O,X,X,X,O,O,O,O,X,X,X,O,O,X,X,X,O,O,O,X,X,X,O,O,O,X,X,O,X,O,O,O,X,X,X,O,O,O,X,X,X,O,O,X,X,O,X,O,O,X,O,X,X,O,OO,X,X,X,O,O,O,X,X,X,O,O,X,X,X,O,O,O,X,O,X,X,-,0,2,1,-,-,-,1,2,2,1,0,1,-,-,-,1,1,1,1,1,1,2,-,1,1,59,人工智能之与或图搜索问题,第59页,O,O,MAX,MIN,60,人工智能之与或图搜索问题,第60页,MAX,MIN,O,O,61,人工智能之与或图搜索问题,第61页,极大极小搜索过程由两个完全分离两个步骤组成：,第一,、用宽度优先算法生成一棵博弈搜索树,第二,、预计值倒推计算,缺点,：这种分离使得搜索效率比较低,62,人工智能之与或图搜索问题,第62页,极小极大过程,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,9,-3,0,-3,3,-3,-3,-2,1,-3,6,0,3,1,6,0,1,1,极大,极小,a,b,注：用表示MAX，用表示MIN，端节点上数字表示它对应估价函数值。,极大,极小,63,人工智能之与或图搜索问题,第63页,极大极小过程是先生成与/或树，然后再计算各节点估值，这种生成节点和计算估值相分离搜索方式，需要生成要求深度内全部节点，所以搜索效率较低。,改进,：,在博弈树生成过程中同时计算端节点预计值及倒推值，以降低搜索次数，这就是-过程思想，也称为-剪枝法。,剪枝概念,:,假如能边生成节点边对节点估值，并剪去一些没用分枝，这种技术被称为-剪枝。,64,人工智能之与或图搜索问题,第64页,-剪枝,极大节点下界为,。,极小节点上界为。,剪枝条件：,后辈节点值祖先节点值时，剪枝,后辈节点 值祖先节点值时，剪枝,简记为：,极小极大，剪枝,极大极小，剪枝,65,人工智能之与或图搜索问题,第65页,一个-剪枝详细例子，以下列图所表示。其中最下面一层端节点旁边数字是假设估值。,在该图中，L、M、N估值推出节点F倒推值为4，即F值为4，由此可推出节点C倒推值4。,记C倒推值下界为4，不可能再比4小，故C值为4。,由节点N估值推知节点G倒推值小于1,不论G其它子节点估只是多少，G倒推值都不可能比1大。所以，1是G倒推值上界，所以G值1。另已知C倒推值4，G其它子节点又不可能使C倒推值增大。所以对G其它分支无须再搜索，相当于把这些分枝剪去。,由F、G倒推值可推出节点C倒推值4，再由C可推出节点A倒推值4，即A值为4。,另外，由节点P、Q推出节点H倒推值为5，所以D倒推值5，即D值为5。此时，D其它子节点倒推值不论是多少都不能使D及A倒推值降低或增大，所以D其它分枝被减去，并可确定A倒推值为4。以这类推，最终推出S,0,倒推值为4。,4,S,0,4,A,0,11,4,5,0,C,D,E,0,-6,I,J,4,1,K,L,N,4,6,1,F,G,5,P,5,8,H,M,8,值,值,值,值,Q,R,0,-6,S,66,人工智能之与或图搜索问题,第66页,8,6,-3,1,4,5,3,-3,5,0,-剪枝（续）,3,-3,0,2,2,-3,0,-2,3,9,-3,0,0,-3,0,3,3,0,5,4,1,1,-3,1,6,6,1,a,b,c,d,e,f,g,h,i,j,k,m,n,0,剪枝,剪枝,剪枝,剪枝,67,人工智能之与或图搜索问题,第67页,-剪枝其它应用,故障诊疗,A B C D,风险投资,68,人工智能之与或图搜索问题,第68页,