2014第4章搜索原理

1、搜索原理Solving Problems by Searching现实世界中问题求解的过程实际上可以看成是一个搜索的过程。人工智能的许多领域都可以抽象为“问题求解”。推理过程实际上也是一个搜索过程，即在知识库中搜索和前提条件相匹配的规则，然后运用这些规则进行推理。为了进行有效搜索，对所求解的问题要以适当的形式表现出来，其表现方法直接影响到搜索效率。2014-11-26Introduction to Artificial Intelligence4.1状态空间4.1.1 状态图状态描述问题求解过程中任意时刻状况的数据结构。可用一组变量的有序集合来表示：S=(Sk1,Sk2,Skn)算符引起状态中

2、某些分量发生变化，从而使问题有一个状态变为另一个状态的操作称为算符。2014-11-26Introduction to Artificial Intelligence状态空间用算符所空间。由问题的全部状态及一切可的集合称为问题的状态(S,F,G)。可用三元组表示S为初始状态集， F为算符集G为目标状态集4.1.2 状态空间举例2014-11-26Introduction to Artificial Intelligence例：Hano塔问题AABB1231231,2,3三根柱子，1柱上面有A,B两个， A<B。需移到3柱上。注意每次只能移动一个盘子，而要将且大盘不能压在小盘上。我们用二元

3、组表示状态 S=(Sa,Sb), Sa表示A所在柱号,Sb表示B所在柱号。因此有：S0=(1,1)S3=(2,1)S6=(3,1)2014-11-26S1=(1,2)S4=(2,2)S7=(3,2)S2=(1,3)S5=(2,3)S8=(3,3)S=S0=(1,1) G=S8=(3,3)Introduction to Artificial Intelligence定义算符：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2)B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)状态空间：1,1A(1,3)A(1,2)2,13,1B(1,

4、3)2,3A(2,3)B(1,2)3,2A(3,2)3,31,31,22,22014-11-26Introduction to Artificial Intelligence三阶Hano塔123123n阶Hano塔 ?2014-11-26Introduction to Artificial Intelligence修士-野人问题missionary - cannibal河有道士，三个野人，都要渡到右岸去，仅有一条船。渡河的规则有：1、所有的修道士和野人都可以划船。2、每次一条船上最多可载两人。3、不论在还是右岸，修道士的人数不可以低于野人的人数，否则修道士将被野人4、渡船的方案由修道士来设计。

5、2014-11-26Introduction to Artificial Intelligence用三元组 <m c b>表示状态:m 代表在修道士人数，c 代表在野人人数，b 代表船的状态：=1 船在=0 船不在， 初始状态为(3 3 1) 目标状态为(0 0 0)4×4×2=32种定义操作：P10, P01, P11 , P20, P02Q10, Q01, Q11 , Q20, Q02P表示从到右岸，Q表示从右岸到，i, j表示船上修士和野人的个数。2014-11-26Introduction to Artificial IntelligenceQ11Q0Q

6、10P11P02P01P2P102014-11-26Introduction to Artificial IntelligenceQ10P11P02Q01P20Q01P02Q11P20P02Q01P02Q01P11Q102014-11-26Introduction to Artificial Intelligence问题的扩展有一条河分割，开始时有m个野人，n个修道士（mn）要过河。但是只有一条船，船上可坐c个人。在船上或在某边的岸上如果野人的数目大于修道士的数目野人就会对修道士安全的过河方案。例 (5,5,3)修道士。要求给出一种2014-11-26Introduction to Artif

7、icial Intelligence例：钱币问题3次翻转123123三枚硬币，初始反正反。每次可翻转一枚，连续三次，是否可以变成反反反或者正正正。我们用三元组表示状态 Q=(q1,q2,q3),0-正，1-反S=(1,0,1)G=(0,0,0)或(1,1,1)定义操作 f1，f2，f3，表示反转第几块。2014-11-26Introduction to Artificial Intelligencef1f3f2f3f2f1f1f2f3f1 f1 f2 f1 f2 f1 f2 f1 f1 f2 f2 f2 f2 f3 f3 f3 f2 f3f3 f3 f2f2f3f12014-11-26Intr

8、oduction to Artificial Intelligence例：火柴问题？123123三根火柴，均。每次可翻转相邻两根，是否可以变成均我们用三元组表示状态 Q=(q1,q2,q3),0-上，1-下S=(0,0,0)G=(1,1,1)定义操作 f1反转1，2根，f2翻转2，3根2014-11-26Introduction to Artificial Intelligencef1f1f2f2f2f1f1f2问题的扩展n根火柴，每次可翻转t根2014-11-26Introduction to Artificial Intelligence4.1.3 问题的变换知识的表示方法各不相同，各有各

9、的特点。选择良 好的表示方法，可以使问题易于求解。在2n×2n的方格棋盘上，去掉对角两个方格，问怎样可划分成1×2 的小块。首先n没有限制，且分割的方法非常多。如何考虑？2014-11-26Introduction to Artificial Intelligence问题变换用黑白相间着色，可以发现对角线的颜色都是一致的。而任意一个1×2的块，都是一黑一白。<数，黑格数>表示S=<2n2-2，2n2>G=<0,0> f=(a-1,b-1)2014-11-26Introduction to Artificial Intellige

10、nce表达式问题(a+b)×(c-d)÷(e-f)求÷后序遍历ab+cd-×ef-÷-×+-efabcd建立堆栈，遇到数字如栈，遇到符号则出栈运算2014-11-26Introduction to Artificial Intelligence4.1.4搜索方法分类爬山法瞎子爬山，每次从当前状态找出周围最可能的路，向目标走一步， 再重复前面过程。如果问题是线性的，就可以找到目标。当前状态。方法简单，只如果问题有局部最大值，就可能无法找到最终解。2014-11-26Introduction to Artificial Intellige

11、nce回溯法如果不起点到当前的路径，可以回退到，再试探另一条路径。例：皇后问题 - 在n×n的棋盘上， 放置n个皇后，要求每一横行，每一列，每一对角线上均只能放置一个皇后，求可能的方案。2014-11-26Introduction to Artificial IntelligenceQQQQ例：迷宫问题 - 在n*n的网格上，0表示可以通过，1表示不能通过。寻找从开始到目标的最佳路径。0 0 0 0 01 0 1 0 10 0 1 1 10 1 000 0 002014-11-26Introduction to Artificial Intelligence图搜索在状态空间图中寻找目

12、标或路径的基本方法。盲目搜索 -启发式搜索与问题本身信息无关-利用问题的特点图搜索可看作一种在图中寻找路径的方法。初始节点和目标节点。求得把一个状态变换为另一状态的规则序列问题就等价 于求得图中的一条路径问题。2014-11-26Introduction to Artificial Intelligence4.2盲目搜索策略4.2.1 图搜索的一般策略复杂问题的状态空间一般都十分庞大，如果全部，需占用巨大的空间，需要很长的时间，难以实现。而且与问题有关的往往只是整个状态空间的一部分，因此只需要生成所需要的状态空间。思想把问题的初始状态作为当前节点，选择适当的算符对其操作，生成一组子状态。然后选

13、则某个子状态作为当前节点， 直到找到解。2014-11-26Introduction to Artificial Intelligence数据结构：OPEN表：存放刚生成而未扩展的的节点CLOSED表：存放已经扩展的的节点扩展：用合适的算符对该节点进行操作， 生成一组子节点2014-11-26Introduction to Artificial Intelligence编号状态节点点状态节点点(1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。(2) 建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3) 若OPEN表是空表，则失败。(4) 选择OPEN

14、表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5) 若n为一目标节点，则有解并，此追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。(6) 扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。 *(8) 按某一任意方式或按某种策略，重排OPEN表。(9) GO LOOP 3。2014-11-26Introduction to Artificial Intel

15、ligence（7）补充:对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED 表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。2014-11-26Introduction to Artificial Intelligence开始是失败否是中南大学 智能2014-11-26Introduction to Artificial IntelligenceOPEN表为空表？n为目标节点吗？否系统与智能软件重排OPEN表例：八数码问题（8-puzzle）在3*3的方格上，放置1，2，3，4，5，6，7， 8棋子，还有一个空格，每

16、次可将相邻棋子移入空 格。要求通过一定步骤达到目标状态。定义操作：空格左移，空格上移，空格右移，空格下移2014-11-26Introduction to Artificial Intelligence1238476528314765空格右移空格上移空格左移空格下移2014-11-26Introduction to Artificial Intelligence2831647576523652834.2.2 宽度优先搜索(breadth-first search)搜索是以接近起始节点的程度依次扩展节点，逐 层进行的；在对下一层的任一节点进行搜索之前，必须搜索的所有节点。(6) 扩展节点n，将子

17、节点放入OPEN表尾部，并配置其点的指针。将OPEN表作为“先进先出” 的队列进行操作。2014-11-26Introduction to Artificial Intelligence2014-11-26Introduction to Artificial Intelligence1237846523847658326528375283652345283765283765752832352837652836523765283特点：完备的搜索策略，只要存在解，就一定能找到最 佳解（路径最短）。盲目性较大，当目标距离较远时，会产生大量无 用的节点，效率较低。2014-11-26Introduct

18、ion to Artificial Intelligence4.2.3 深度优先搜索(depth-first search)我们定义节点的深度如下：(1) 起始节点(即根节点)的深度为0。(2) 任何其它节点的深度等于其父辈节点深度加上1。深度优先搜索首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。(6) 扩展节点n，将子节点放入OPEN表前端，并配置其点的指针。将OPEN表作为“后进先出”的堆栈进行操作。2014-11-26Introduction to Artificial Intelligence扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去

19、；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能小。2014-11-26Introduction to Artificial Intelligence2014-11-26Introduction to Artificial Intelligence4765852837652836523765283有界深度优先搜索 为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度深度界限。任何节点如果达到了深度界限，那么作为没有后继节点处理。把它们2014-11-26Introd

20、uction to Artificial Intelligence开始CLOSED有待扩展节点？NYR为空？Y失败2014-11-26Introduction to Artificial IntelligenceOPEN为空？YNYd(n)>dm？Yn为目标吗？NNn可扩展？Y扩展节点n，将后继节点加入OPEN 表，设置指针特点：深度优先是完备的算法。备的搜索策略。而有界深度则是可以较快向深度方向进行。但是如果所处分支错 误，也会导致无法求解或效率低下。2014-11-26Introduction to Artificial Intelligence4.2.3 代价优先搜索在上面的讨论中

21、，没有考虑搜索的代价，搜索树 中每条边都是等价的。只用路径长度来表示。事实上，边上的代价可以不同，表示时间、距离等花费。S边上标有代价（费用）的树称为代价树g(x)表示从初始节点到x的代价。c(x1,x2)表示点x1和子节点x2的代价有：g(x2)=g(x1)+c(x1,x2)g(x1) x1c(x1,x2)g(x2) x2Introduction to Artificial Intelligence2014-11-26对于节点i的每个后继节点j，计算g(j)=g(i)+c(i,j)2014-11-26duction to Artificial Intelligence(A-E)售货员问题AA

22、434BC1B1354524D2DED1E152C3432E1BC2E35E42014-11-26Introduction to Artificial Intelligence4.2.4 总结在搜索的(8)步，按某一任意方式或按某种策略， 重排OPEN表。设f(x)表示某种策略若f(x)=mind(x)，则为宽度优先搜索若f(x)=maxd(x)，则为深度优先搜索若f(x)=ming(x)，则为代价优先搜索。2014-11-26Introduction to Artificial Intelligence关于重置指针A45CB52D2014-11-26Introduction to Artif

23、icial Intelligence4.3启发式搜索盲目搜索：效率低，耗费过多的计算空间与时间。分析前面介绍的宽度优先、深度优先搜索，代价优先搜索算法, 其主要的差别是OPEN表中待扩展节点的顺序问题。人们就试图找到法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。启发信息：进行需要的某些有关具体问题领域的 特性的信息，把此种信息叫做启发信息。利用启发信息的搜索方法叫做启发式搜索方法。2014-11-26Introduction to Artificial Intelligence4.3.1 估价函数用来估算节点希望程度的量度，叫做估价函数(evaluati

24、on function)。f(n)表示节点n的估价函数值例如：在8数码问题中，我们考虑不在位2014-11-26Introduction to Artificial Intelligencew=4f=4f(n)=w(n)+d(n)w=5 f=6w=3 f=4w=5 f=6w=3f=5w=4f=6w=3 f=5w=2 f=5w=4 f=7w=3 f=6w=4 f=7w=1 f=5w=0 f=5w=2 f=82014-11-26Introduction to Artificial Intelligence全局择优搜索best-first search2014-11-26Introduction t

25、o Artificial Intelligence正确地选择估价函数对确定搜索结果具有决定性的作用。使用不能识别某些节点真实希望的估价 函数会形成非最小代价路径；而使用一个过多地 估计了全部节点希望的估价函数(就像宽度优先搜索方法得到的估价函数一样)又会扩展过多的节点。估价函数的定义十分重要。如何既提高效率，又保证求得最佳解？A*算法对估价函数进行了限制。2014-11-26Introduction to Artificial Intelligence4.3.2 A*算法我们描述一个特别的估价函数，这个估价函数f使得在任意节点上其函数值f(n)能估算出从节点S到节点n的最小代价路径的代价与从节

26、点n到某一目标节点的最小代价路径的代价之总和，也就是说f(n)是约束通过节点n的一条最小代价路径的代价的一个估计。因此，OPEN表上具有最小f值的那个节点就是所估计的加有最少严格约束条件的节点，而且适的。要扩展这个节点是合2014-11-26Introduction to Artificial Intelligence估价函数的定义：对节点n定义f*(n)=g*(n)+h*(n) ,表示从S开始约束通过节点n的一条最佳路径的代价。g*是从S到n的最小代价， h*是从n到目标t的最小代价设有最佳路径s,n1,n2,n,t, 有：f*(s)=f*(n1)=f*(n2) =f*(n)=f*(t)令f

27、(n)=g(n)+h(n)g是g*的估计 ，h是h*的估计2014-11-26Introduction to Artificial Intelligenceg(n)是g*(n)的估计。对于任意节点，有g(n) g*(n)我们称h(n)为启发函数，如果对于任意节点， 满足：h(n) h*(n)即 h是h*的下界，则图搜索算法称为A*算法。例如：在8数码中，w(n) h*(n)可以证明： A*算法是可采纳的，即如果问题有界，保证能找到最佳解。2014-11-26Introduction to Artificial IntelligenceA*的可采纳性1. 对于有限图，A*会在有限步内终止。2.

28、对于无限图，若有解存在，A*也必然会终止3. A*必然会终止在最优路径上。A*扩展的每一个节点n，都有f(n) f*(s)2014-11-26Introduction to Artificial Intelligence1对于有限图，A*会在有限步内终止所谓有限图，节点个数是有限的。Graph search算法中，终止条件有两个：，当OPEN表为空时；失败由于每次从OPEN表中取出一个节点，因此总有用完OPEN表的时候，算法总可以结束。2014-11-26Introduction to Artificial Intelligence2对于无限图，若有解存在，A*也必然会终止因为问题有解，因此存

29、在一条最优路径；S0,S1,S2,S3,.Sm,S*g设为在算法结束前，OPEN表中必然含有这条路径上的某些节点Sx，设 其中最前的为f(Sx) f*(S0)有若算法不终止，令 e为最小的边的代价，g*(xn) d *(xn) ×e且 g (xn) d *(xn) ×e所以 f (xn) d *(xn) ×e由于算法不结束，d不断增长，总会出现某个时候，f(Sx) > f*(S0)出现！2014-11-26Introduction to Artificial Intelligence3A*必然会终止在最优路径上。假定A*没有终止在最优路径上，而是终止在某个节

30、点t上。则f(t)=g(t)> f*(s)根据前面所证明，在A*结束前，必有最佳路径上的节点n在OPEN表里，因此，A*必然会选择n先扩展，而不是t. 因此A*只能结束于最佳路径。可以证明，最优路径上的节点满足 f*(s)2014-11-26Introduction to Artificial IntelligenceA*的最优性设有两个估价函数h1(x),h2(x),如每个节点h1(x) h2(x)则 h2具有更强的启发能力，A2*扩展的节点是A1*扩展节点的子集2014-11-26Introduction to Artificial Intelligencef1(n)=w(n)+d(

31、n)f2(n)=p(n)+d(n)w=4p=5w=5 p=6w=3 p=4w=5 p=6w=3p=5w=3 p=3w=3 p=3w=2 p=2w=4 p=4w=1 p=1w=0 p=0w=2 p=22014-11-26Introduction to Artificial Intelligence4.44.4.1与或树的搜索与或树与或用于表示问题及求解过程的又一种形式化方法，也称为问题归约方法。把初始问题通过一系列分解变换最终变成一个子问题的集合，而这些子问题的得到的。可以直接最后，把各子问题的解复合起来，从而得到初始问题的解。2014-11-26Introduction to Artifici

32、al Intelligence变换分解PPP1P2P3P1P2P3与树把问题P分解成或树把问题P变换成 P1问题，当P1P1P2P2P3P3P2P2P3P3问题，当P1都可解时，P可解。有一个可解时，P可解。与或树 分解变换结合2014-11-26Introduction to Artificial Intelligence本原问题不能再分解或变换，且直接可解的子问题端节点在与或，没有子节点的节点终止节点在与或，本原问题对应的节点可解节点1)终止节点P2)点都可解的与节点P1P2P33)至少一个子节点可解的或节点不可解节点不满足可解条件P11P12P31P32由能导致初始节点（根节点）与或树为

33、可解的所有可解节点所的树2014-11-26Introduction to Artificial Intelligence4.4.2与或树的搜索(求解)与或树的求解不是寻找一条路径，而是寻找。与或树上节点的可由其子节点决定的，与或树的求程。由子节点向上不断推断点可解性的过可解标示由可解节点向上确定其点的过程。不可解标示由不可解节点向上确定其解节点的过程。点、祖点为可解节点、祖点为不可2014-11-26Introduction to Artificial Intelligence开始YNn可扩展N子节点有终止节点YYNS0不可解？YS0可解？N失败2014-11-26Introduction

34、to Artificial Intelligencet1BAt2t3t42014-11-26Introduction to Artificial Intelligence与或树的广度优先搜索ABCADEGCBDEGF不可解标识可解标识JKHI可解标识可解标识2014-11-26Introduction to Artificial Intelligence与或树的深度优先搜索ACAGBCBEDEFG可解标识JKHI可解标识可解标识2014-11-26Introduction to Artificial Intelligence4.4.3与或树的代价搜索与或树代价搜索可以求取代价最小的的代价。设c

35、(x,y)表示可用以下方法计算：点x到子节点y的代价，节点x的代价1) 如果x是终止节点，则 h(x)=02) 如果x是或节点，y1,y2,是x的子节点，则h(x)=minc(x,yi)+h(yi), i=1n 3)如果x是与节点，y1,y2,是x的子节点，则和法：h(x)=(c(x,yi)+h(yi), i=1n：h(x)=maxc(x,yi)+h(yi), i=1n最h(x)=4)如果x是不可解节点，则2014-11-26Introduction to Artificial IntelligenceS813226116AB5214ttCD12313tEFG12和法最h(S）= 21h(S)

36、 =8tt2014-11-26Introduction to Artificial Intelligence希望树当我们要计算一个节点的代价时，必须知道其子节点的代价。但是，搜索是自上而下进行的，即先有点，后有子节点，因此如何计算代价？我们可以根据问题的启发信息定义启发函数，由此估算子节点的代价h(yi)，然后计算出x的代价h(x)。并根据x的代价自下而上推算其点的代价，直到根节点。我们的目的是求得代价最小的。因此我们的搜索可以沿代价最小的的子树称为希望树进行。我们把某一时刻最小代价2014-11-26Introduction to Artificial Intelligence希望树T的定义

37、 初始节点S0在希望树T中； 如果与节点x在希望树T中，则它的一定在T中；点 如果或节点x在希望，则具有最小c(x,yi)+h(yi)的子节点也在T中。2014-11-26Introduction to Artificial Intelligence开始YNn是终止节点Nn可扩展YYNNS0可解？S0不可解？Y失败2014-11-26Introduction to Artificial Intelligence扩展n,将其子节点配上父指针放入OPEN表计算点和先辈的h(x)设初始节点S，每次扩展两层，与或交替。边的代价均为1，和法计算913DE3F27343MPGH00220022322220

38、14-11-26Introduction to Artificial Intelligence4.5博弈树的搜索博弈富有智能行为的竞争活动，诸如下棋、打牌、等双人完备信息博弈机遇性博弈双人完备信息博弈 A，B双方轮流采取行动零和：A胜B败; B胜A败;平局全信息：任何一方都了解当前和历史格局。任何一方都根据当前情况，选择对最有利的步骤。2014-11-26Introduction to Artificial Intelligence博弈论（game theory）对人的基本假定是： 人是理性的（rational）或者说人自私的理性的人是指他在具体策略选择时的目的是使的利益最大化，博弈论研究的是

39、理性的人之间如何进行策略选择的。2014-11-26Introduction to Artificial Intelligence经典例子： "徒的困境”两个嫌疑犯（和）作案后被抓住，审讯；的政策是"坦白从宽，抗拒从严"，如果两人都坦白则各判年；如果一人坦白另一人不坦白，坦白的放出去，不坦白的判 年；如果都不坦白则因证据不足各判年。可能出现的四种情况*均衡*整体最佳2014-11-26Introduction to Artificial Intelligence坦白坦白88不坦白坦白100坦白不坦白010不坦白不坦白11.(John F. Nash)1994年学奖

40、获得者1950年和1951年的两篇关于非合作博弈论的重要，彻底改变了人们对竞争和市场的看法。他证明了非合作博弈及其均衡解，并证明了均衡解的存在性，即著名的均衡。从而揭示了博弈均衡与均衡的内在。的研究奠定了现代非合作博弈论的基石，后来的博弈论研究基本上都沿着这条主线展开的。美丽心灵的主角2014-11-26Introduction to Artificial Intelligence博弈树博弈过程中，双方都希望胜利。 当轮到走时，可以从多种方案中选择一个对最有利的方案，只需选择一个分枝即可，因此就是“或”的关系。 而当对方走时，操作权在对方手里，由于无法对方选择的方案，因此对所有可能性对来说就是

41、“与”的关系。博弈过程中，与对方交替进行，可以用“与或树”表示博弈过程，称为博弈树注意，博弈树始终是站在某一立场得出的2014-11-26Introduction to Artificial Intelligence2014-11-26Introduction to Artificial Intelligence完全的搜索对于大多数博弈来说是不可行的。据测算，完全的国际象棋博弈图大约有1040个节点。因此我们只能采用局部搜索的方式。可以命名两个博弈者，一个是Max,另一个是Min。我们的任务是为Max寻找最佳的走法。静态评估函数：根据问题的特性给出某种状态的估价值。> 0,= 0,对Ma

42、x有利。双方同等(表示Max赢)h(x)< 0， 对Min方有利(-表示Max输)Introduction to Artificial Intelligence2014-11-26极大极小分析（Max-Min）对于Max节点，他肯定选择对的步子，即也就是h(x)最大。最有利在考虑Min节点时，对方应该会走对最不利的步子，即h(x)最小。节点的估价值就是这样从交替倒推的过程最大、最小节点的后继的倒推值比直接从节点计算静态估价值更可靠。2014-11-26Introduction to Artificial Intelligence Max3 Min 23433Max22-11-234-51

43、3Min321-114-264346-56-218362014-11-26Introduction to Artificial Intelligence例：（一字棋，Tic-Tac-Toe）在3 × 3的九个空格上，由MAX(画×)， MIN (画) 二人对弈。轮到谁走棋谁就往空格上放一只的棋子，谁先使的成一线”(同一行、列或对棋子“角线全是同样的棋子)，谁就取得了胜利。××××2014-11-26Introduction to Artificial Intelligence×如何定义估价函数？设棋面为x，定义：p：在棋面上

44、，如果将所有空格全部填充为×， 此时出现三个×成一线的次数；q：在棋面上，如果将所有空格全部填充为， 此时出现三个成一线的次数； ×× ×××× ×××将空格填充为q = 4将空格填充为×P = 5某个状态2014-11-26Introduction to Artificial Intelligence×定义估价函数 e(x)若x是MAX必胜的棋局，则e(x)+若x是MIN必胜的棋局，则e(P)-否则，e(x)=p-q若e(x)>0,说明对MAX方有利e(x)<0,说明对MIN方有利2014-11-26Introduction to Artificial Intelligence扩展两层后估算15-4=16-4=2-24-6=-2-16-6=06-6=05-6=-15-6=-16-5=15-5=04-5=-15-5=06-5=12014-11-26Introduction to Artificial Intelligence×××××××