人工智能第二章讲义

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