《人工智能之与或图搜索问题课件》由会员分享，可在线阅读，更多相关《人工智能之与或图搜索问题课件（69页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 与或图搜索问题与或图搜索问题目标目标目标目标初始节点初始节点sabc12.1 基本概念基本概念n n与与或或图图是是一一个个超超图图，节节点点间间通通过过连连接接符符连连接。接。n nK-连接符：连接符：.K个个2耗散值的计算耗散值的计算k(n,N)=Cn+k(n1,N)+k(ni,N)其中：其中：N为终节点集为终节点集 Cn为连接符的耗散值为连接符的耗散值.i个个nn1n2ni3目标目标目标目标初始节点初始节点 解图：解图：4能解节点能解节点n n终节点是能解节点终节点是能解节点n n若若非非终终节节点点有有“或或”子子节节点点时时，当当且且仅仅当当其其子子节点至少有一能解时，
2、该非终节点才能解。节点至少有一能解时，该非终节点才能解。n n若若非非终终节节点点有有“与与”子子节节点点时时，当当且且仅仅当当其其子子节点均能解时，该非终节点才能解。节点均能解时，该非终节点才能解。5不能解节点不能解节点n n没有后裔的非终节点是不能解节点。没有后裔的非终节点是不能解节点。n n若若非非终终节节点点有有“或或”子子节节点点，当当且且仅仅当当所所有有子子节点均不能解时，该非终节点才不能解。节点均不能解时，该非终节点才不能解。n n若若非非终终节节点点有有“与与”子子节节点点时时，当当至至少少有有一一个个子节点不能解时，该非终节点才不能解。子节点不能解时，该非终节点才不能解。6普
3、通图搜索的情况普通图搜索的情况f(n)=g(n)+h(n)f(n)=g(n)+h(n)对对对对n n的的的的评评评评价价价价实实实实际际际际是是是是对对对对从从从从s s到到到到n n这这这这条条条条路路路路径径径径的评价的评价的评价的评价ns7与或图与或图:对局部图的评价对局部图的评价目标目标目标目标初始节点初始节点abc8两个过程两个过程n n图生成过程，即扩展节点图生成过程，即扩展节点n n从最优的局部途中选择一个节点扩展从最优的局部途中选择一个节点扩展从最优的局部途中选择一个节点扩展从最优的局部途中选择一个节点扩展n n计算耗散值的过程计算耗散值的过程n n对当前的局部图从新计算耗散值
4、对当前的局部图从新计算耗散值对当前的局部图从新计算耗散值对当前的局部图从新计算耗散值9AO*算法举例算法举例其中：其中：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设：设：K连接符连接符的耗散值为的耗散值为K目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n810目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n8初始节点初始节点n0n1(2)n4(1)n5(1)红色：红色：4黄色：黄色：311初始节点初始节点n0n4(1)n5(1)红色：红色：4黄色：黄色：6n1
5、n2(4)n3(4)5目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n812红色：红色：5黄色：黄色：6初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n813红色：红色：5黄色：黄色：621初始节点初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)目标目标目标目标初始节点初始节点n0n1n2n3n4n5n6n7n814博弈博弈 是一类具有竞争性的智能活动是一类具有竞争性的智能活动双双人人博博弈弈：即即两两位位选选手手对对垒垒
6、，轮轮流流依依次次走走步步，其其中中任任何何一一方方都都完完全全知知道道对对方方过过去去已已经经走走过过的的棋棋步步和和今今后后可可能能的的走走步步，其其结结果果是是一一方方赢赢(而而另另一方则输一方则输)，或双方和局，或双方和局2.3 博弈树搜索博弈树搜索15博弈的例子博弈的例子：一字棋一字棋跳棋跳棋中国象棋中国象棋围棋围棋五子棋五子棋162.3 博弈树搜索博弈树搜索n n博弈问题博弈问题n n双人对弈，对垒的双方轮流走步；双人对弈，对垒的双方轮流走步；双人对弈，对垒的双方轮流走步；双人对弈，对垒的双方轮流走步；n n信信信信息息息息完完完完备备备备，对对对对垒垒垒垒双双双双方方方方所所所所
7、得得得得到到到到的的的的信信信信息息息息是是是是一一一一样样样样的的的的，不存在一方能看到，而另外一方看不到的情况；不存在一方能看到，而另外一方看不到的情况；不存在一方能看到，而另外一方看不到的情况；不存在一方能看到，而另外一方看不到的情况；n n零零零零和和和和，即即即即对对对对一一一一方方方方有有有有利利利利的的的的棋棋棋棋，对对对对另另另另一一一一方方方方肯肯肯肯定定定定是是是是不不不不利利利利的的的的，不不不不存存存存在在在在对对对对双双双双方方方方均均均均有有有有利利利利或或或或均均均均无无无无利利利利的的的的棋棋棋棋，对对对对弈弈弈弈的的的的结结结结果果果果是是是是一一一一方方方方
8、赢赢赢赢，而而而而另另另另一一一一方方方方输输输输，或或或或者者者者双双双双方方方方和和和和棋。棋。棋。棋。17双双方方的的智智能能活活动动，任任何何一一方方都都不不能能单单独独控控制制博博弈弈过过程程，而而是是由由双双方方轮轮流流实实施施其其控控制制对对策策的过程。的过程。博弈的特点：博弈的特点：18如何根据当前的棋局，选择对自己最有利的一如何根据当前的棋局，选择对自己最有利的一步棋步棋？人工智能中研究的博弈问题人工智能中研究的博弈问题：中国象棋中国象棋19用博弈树来表示，它是一种特殊的用博弈树来表示，它是一种特殊的与或树与或树。节点。节点代表博弈的格局（即棋局），相当于状态空间中代表博弈的
9、格局（即棋局），相当于状态空间中的状态，反映了博弈的信息，的状态，反映了博弈的信息，并且与节点、或节并且与节点、或节点隔层交替出现。点隔层交替出现。博弈问题（求解过程）的表示博弈问题（求解过程）的表示：20假设博弈双方为：假设博弈双方为：MAX和和MIN在在博博弈弈过过程程中中，规规则则是是双双方方轮轮流流走走步步。在在博博弈弈树中，相当于博弈双方轮流扩展其所属节点。树中，相当于博弈双方轮流扩展其所属节点。为什么与节点、或节点隔层交替出现为什么与节点、或节点隔层交替出现？21从从MAX方的角度来看方的角度来看：所有所有MIN方节点都是方节点都是与节点与节点理由理由：因因为为MIN方方必必定定选
10、选择择最最不不利利于于MAX方方的的方方式式来来扩扩展展节节点点，只只要要MIN方方节节点点的的子子节节点点（下下出出棋棋局局）中中有有一一个个对对MAX方方不不利利，则则该该节节点点就就对对MAX方不利，故为方不利，故为“与节点与节点”。MIN好招好招22从从MAX方的角度来看方的角度来看：所有属于所有属于MAX方的节点都是方的节点都是或节点或节点理由理由：因为扩展因为扩展MAX方节点时，方节点时，MAX方可选择扩展最方可选择扩展最有利于自己的节点，只要可扩展的子节点中有有利于自己的节点，只要可扩展的子节点中有一个对已有利，一个对已有利，则该节点就对已有利。则该节点就对已有利。MAX好招好招
11、23总之：总之：从从MAX方来说，与节点、或节点交替出现；反之，方来说，与节点、或节点交替出现；反之，从从MIN方的角度来看，情况正好相反。方的角度来看，情况正好相反。24在在博博弈弈树树中中，先先行行一一方方的的初初始始状状态态对对应应着着树树的的根根节节点点，而而任任何何一一方方获获胜胜的的最最终终格格局局为为目目标标状状态态，对应于树的对应于树的终叶节点终叶节点（可解节点或本原问题）。（可解节点或本原问题）。但但是是，从从MAX的的角角度度出出发发，所所有有使使MAX获获胜胜的的状状态态格格局局都都是是本本原原问问题题，是是可可解解节节点点，而而使使MIN获获胜的状态格局是胜的状态格局是
12、不可解节点不可解节点。25博弈树特点博弈树特点(1)(1)(1)(1)博弈的初始状态是初始节点；博弈的初始状态是初始节点；博弈的初始状态是初始节点；博弈的初始状态是初始节点；(2)(2)(2)(2)博博博博弈弈弈弈树树树树的的的的“与与与与”节节节节点点点点和和和和“或或或或”节节节节点点点点是是是是逐逐逐逐层层层层交交交交替替替替出出出出现的；现的；现的；现的；(3)(3)(3)(3)整整整整个个个个博博博博弈弈弈弈过过过过程程程程始始始始终终终终站站站站在在在在某某某某一一一一方方方方的的的的立立立立场场场场上上上上，所所所所以以以以能能能能使使使使自自自自己己己己一一一一方方方方获获获获
13、胜胜胜胜的的的的终终终终局局局局都都都都是是是是本本本本原原原原问问问问题题题题，相相相相应应应应的的的的节节节节点点点点也也也也是是是是可可可可解解解解节节节节点点点点，所所所所有有有有使使使使对对对对方方方方获获获获胜胜胜胜的的的的节节节节点点点点都都都都是是是是不不不不可解节点。可解节点。可解节点。可解节点。26例例 Grundy博弈：分配物品的问题博弈：分配物品的问题如如果果有有一一堆堆数数目目为为N的的钱钱币币，由由两两位位选选手手轮轮流流进进行行分分配配，要要求求每每个个选选手手每每次次把把其其中中某某一一堆堆分分成成数数目目不不等等的的两两小小堆堆，直直至至有有一一选选手手不不能
14、能将将钱钱币币分分成成不等的两堆为止，则判定这位选手为输家。不等的两堆为止，则判定这位选手为输家。27用数字序列加上一个说明来表示一个状态：用数字序列加上一个说明来表示一个状态：(3,2,1,1,MAX)数字序列数字序列：表示不同堆中钱币的个数：表示不同堆中钱币的个数说明说明：表示下一步由谁来分，即取：表示下一步由谁来分，即取MAX或或MIN28现在取现在取 N7 的简单情况的简单情况，并由，并由MIN先分先分 注注：如果如果MAX走红箭头的分法，必定获胜。走红箭头的分法，必定获胜。所有可能的分法所有可能的分法(7,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(5,1,1,M
15、IN)(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,1,1,1,MIN)(3,1,1,1,1,MIN)(2,1,1,1,1,1,MAX)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对对于于比比较较复复杂杂的的博博弈弈问问题题，只只能能模模拟拟人人的的思思维维“
16、向向前前看看几几步步”，然然后后作作出出决决策策，选选择择最最有有利利自自己己的的一一步步。即即只只能能给给出出几几层层走走法法，然然后后按按照照一一定定的的估算办法，估算办法，决定走一好招。决定走一好招。31中国象棋中国象棋n n一一盘盘棋棋平平均均走走50步步，总总状状态态数数约约为为10的的161次方。次方。n n假设假设1毫微秒走一步，约需毫微秒走一步，约需10的的145次方年。次方年。n n结论：不可能穷举。结论：不可能穷举。32在人工智能中可以采用搜索方法在人工智能中可以采用搜索方法来求解博弈问题，下面就来讨论来求解博弈问题，下面就来讨论博弈中两中最基本的搜索方法。博弈中两中最基本的搜索方法。33对于复杂的博弈问题，要规定搜索深度与时间，对于复杂的博弈问题，要规定搜索深度与时间，以便于博弈搜索能顺利进行。以便于博弈搜索能顺利进行。假设由假设由MAX来选择走一步棋，问题是：来选择走一步棋，问题是：MAX如何来选择一步好棋如何来选择一步好棋？极大极小过程极大极小过程34极大极小过程极大极小过程 n n极极大大极极小小过过程程是是考考虑虑双双方方对对弈弈若若干干步步之之后后，从从
