《人工智能第二章讲义ppt课件.ppt》由会员分享，可在线阅读，更多相关《人工智能第二章讲义ppt课件.ppt（45页珍藏版）》请在三一办公上搜索。
1、人工智能第二章讲义,2,回顾：图搜索算法,s,g,一个结点的后继节点之间是“或”的关系,3,“与”关系,如果一个结点的部分或全部后继节点都被求解，该结点才被求解。,一个结点的后继节点之间是“与”的关系,4,“与”关系的表示方法,超弧线：具有“与”关系的子节点间用超弧线来表示。,5,第二章 与或图搜索问题,目标,目标,初始节点s,a,b,c,6,2.1 基本概念,与或图是一个超图，节点间通过连接符连接。K-连接符：表示父结点指向一组具有k个后继结点的结点集。,K=1 子结点为或结点,K1 子结点为与结点,7,连接符示例,2-连接符,1-连接符,8,耗散值的计算 k(n, N),k(n, N) =
2、 Cn+k(n1, N)+k(ni, N)其中：N为终节点集 Cn为连接符的耗散值,k(n1, N),k(n2, N),Cn,k(ni, N),9,目标,目标,初始节点,解图：,10,能解节点,终节点是能解节点若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。,11,不能解节点,没有后裔的非终节点是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。,12,与或图中的局部图,局部图：,
3、(1)单一结点是一个局部图。,(2)对一个局部图中的任意叶结点n，选择一个外向连接符K，则该局部图、外向连接符K以及K所连接的n的后继结点一起组成的仍是一个局部图。,13,局部图,目标,目标,初始节点,a,b,c,14,普通图搜索：对单个结点的评价,f(n) = g(n) + h(n)对n的评价实际是对从s到n这条路径的评价,n,s,15,与或图: 对局部图的评价,由于“与”节点的存在，单纯对一个节点的评价已经不能反映解图的全面情况。需通过对局部解图进行评价。,16,两个过程,图生成过程，即扩展节点从最优的局部图中选择一个节点扩展计算耗散值的过程对当前的局部图重新计算耗散值,17,博弈树搜索,
4、博弈问题（1）双人对弈，对垒的双方轮流走步。（2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。（3）零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。,18,博弈问题为什么可以用与或图表示,我方走棋: 只需从若干个可以走的棋中，选择一个棋走即可。若干个可以走的棋是“或”的关系。对方走棋：对我方来说，必须能够应付对手的每一种走棋。相当于这些棋是“与”的关系。博弈问题是一种特殊的与或图。,19,Grundy博弈：分钱币的游戏,有一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次
5、只把其中某一堆分成数目不等的两小堆。例如选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。,20,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）B,（3,1,1,1,1,MIN）,（2,2,1,1,1,MIN）A,（2,1,1,1,1,1,MAX）C,MAX输,MAX输,MIN输,Grun
6、dy博弈：分钱币的游戏,21,分钱币问题的产生式系统描述,综合数据库：用无序数字序列x1，x2， 表示n堆钱币不同的个数，再用两个说明符号代表选手，无序数列和符号M组合（x1，x2， ，M）就代表由某个选手走步的状态。规则：if （x1， ，M）（xjy+z，yz）then （x1， ，y，z， ，xn， ）设初始状态为（7，MIN），则该问题的状态空间图如图3.4所示，图中所有终节点均表示该选手必输的情况，取胜方的目标是设法使棋局发展为结束在对方走步时的终节点上，因此节点A是MAX的搜索目标，而节点B，C则为MIN的搜索目标。,22,含有MAX符号的节点可看成与节点。含有MIN符号的节点可看
7、成或节点。MAX要取胜，必须对所有与节点取胜，但只需 对一个或节点取胜，这就是与或图的一个解图。寻找MAX的取胜策略等同于求解图。解图代表一种完整的博弈策略。,Grundy博弈：搜索策略,23,中国象棋,一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不可能穷举。,24,极小极大搜索过程,极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的-剪枝搜索方法，就是从这一方法发展而来的。,25,通过评价函数对所有棋局势态进行评估。评价函数值0时，棋局对我方有利，对对方不利。评价函数值0时，棋局对我方不利，对对方有利。评价函数值=+时，我
8、方必胜。评价函数值=- 时，对方必胜。只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。为了走出好棋，必须多看几步，从多种可能状态中选择一步好棋。,极小极大搜索过程,26,极大极小方法：基本思想,1. 设博弈的一方为MAX、一方为MIN。极大极小分析法 是为其中的一方（如MAX）寻找一个最优走步方案。2. 根据棋局势态优劣特征定义一个静态估价函数f(p)，用 来对当前博弈树端节点(棋局的势态)做出优劣估值。3. f(p)取值规定如下：有利于MAX 的棋局势态， f(p)0。有利于MIN 的棋局势态， f(p)0。势均力敌的棋局势态，f(p)=0。 f(p
9、)=+时， MAX必胜。 f(p)=- 时， MIN 必胜。,27,4. 当端节点的估值计算出来后，再倒推估算出父 节点的估值。 倒推估算方法：对MAX走步的节点，为了使自己在可供选择的走步中 选一个对自己最有利的走步，因此选择其子节点(“或” 节点)中最大的一个估值作为父节点(MAX节点)的估值；对MIN走步的节点， MAX应考虑最坏的情况，因此选择其子节点(“与”节点)中一个最小的估值作为父节点(MIN节点)的估值。 5. 如果一个走步方案能获得较大的倒推值，则它就是当前最好的走步方案。,极大极小方法：基本思想,28,1. 极小极大过程,0,-3,3,-3,-3,-2,1,-3,6,-3,
10、0,3,1,6,0,1,1,极大 max,极小 min,a,b,min,max,29,设有九个空格，由A，B二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。,极大极小分析法：一子棋,30,极大极小分析法：一子棋,一子棋游戏的估价函数定义如下：设棋局为P，估价函数为f(P)： 1. 若P是A必胜的棋局，则f(P)； 2. 若P是B必胜的棋局，则f(P)； 3. 若P是胜负未定的棋局，则f(P)=f(+P)-f(-P)。 其中： f(+P)表示在棋局P的所有空格上都放上A的棋子后 三子成线的数目 f(-P)表
11、示在棋局P的所有空格上都放上B的棋子 后三子成线的数目。,31,极大极小分析法：一子棋,当前棋局p:,f(p)=6-4=2,所有空格上都放上A的棋子：,f(+p)=6,所有空格上都放上B的棋子：,f(-p)=4,32,极大极小分析法：一子棋,A的第一着棋生成的博弈树。每一着棋都要导致博弈树深度加2：一层是自己，一层是对方。,极大 A,极小B,A,33,生成所有端节点后，才计算静态估值和倒推值,极大极小分析法：存在问题,改进： 生成一个端节点后，马上计算静态估值和倒推值。,-剪枝法,34,-剪枝,max必定 min max (下界值) ， min (上界值),35,-剪枝：,问题：、如何取值，才
12、能使 max必定 min？,假设： ,由于： max ，min , = max min = max min,因此：当 时，必有max min。,36,若生成某些端节点后，能估计出父节点的或值，并且，则就不必再扩展父节点的其余子节点了(因为这些节点的估值对父节点的倒推值已无任何影响)。,-剪枝：,37,-剪枝：举例(深度优先搜索),1,-1,-1, =-1,极大 max,极小 min,2,1,max,若结点4的值是父结点s的所有子结点中的最大值，则s=-1，此时不影响父结点的取值。,3,初始结点s, = -1,-1,此时， ,若结点4的值不是父结点s的所有子结点中的最大值，则父结点s取其他子结点
13、中的最大值，此时也不影响父结点的取值。,38,-剪枝：举例(深度优先搜索),1,-1,-1, =-1,极大 max,极小 min,2,1,max,由于 ，不影响父结点的取值，所以不必再扩展节点4的其他子结点了,3,初始节点s, = -1,-1,-剪枝,39,-剪枝,具体的剪枝方法如下：(1) 对于一个极小值层节点MIN，若能估计出其倒推值 的上界，并且这个值不大于 MIN的父节点(极 大值层节点)的估计倒推值的下界，即， 则就不必再扩展该 MIN节点的其余子节点了(因为 这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为剪枝。,40,-剪枝,(2) 对于一个极大值层节点MAX
14、，若能估计出其倒推值的下确界，并且这个值不小于 MAX的父节点(一定是极小值层节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为剪枝。,41,-剪枝,从算法中看到：(1) MAX节点(包括起始节点)的值永不减少；(2) MIN节点(包括起始节点)的值永不增加。在搜索期间，和值的计算如下：(1) 一个MAX节点的值等于其后继节点当前最大的最终倒推值。 (2) 一个MIN节点的值等于其后继节点当前最小的最终倒推值。,42,剪枝的条件：后辈节点的值祖先节点的值时， 剪枝后辈节点的 值祖先节点的值时， 剪枝简记为：极小极大， 剪枝极大极小， 剪枝,43,-剪枝（续）,0,0,0,0,a,b,d,f,极大 max,极小 min, =0, = 0,0,极大 max,极小 min, =-3,-3,44,-剪枝（续）,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,5,4,1,-3,0,6,8,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,极大 max,极小 min,max,min,45,-剪枝的其他应用,故障诊断 A B C D风险投资,
