人工智能第二章讲义ppt课件

人工智能第二章讲义人工智能第二章讲义12回顾：图搜索算法回顾：图搜索算法sg一个结点的后继节点之间是“或”的关系2回顾：图搜索算法sg一个结点的后继节点之间是“或”的关系23“与与”关系关系如果一个结点的部分或全部后继节点都被求解，该结点才被求解。一个结点的后继节点之间是“与”的关系3“与”关系如果一个结点的部分或全部后继节点都被求解，该结点34“与与”关系的表示方法关系的表示方法超弧线：具有超弧线：具有“与与”关系的子节点间用超弧线来表示。关系的子节点间用超弧线来表示。sbc4“与”关系的表示方法超弧线：具有“与”关系的子节点间用超弧45第二章第二章 与或图搜索问题与或图搜索问题目标目标初始节点sabc5第二章 与或图搜索问题目标目标初始节点sabc562.1 基本概念基本概念l与或图是一个超图，节点间通过连接符连接。lK-连接符：表示父结点指向一组具有表示父结点指向一组具有k个后继个后继结点的结点集。结点的结点集。.K个K=1 子结点为或结点子结点为或结点K1 子结点为与结点子结点为与结点62.1 基本概念与或图是一个超图，节点间通过连接符连接。67连接符示例连接符示例asbc2-连接符连接符1-连接符连接符7连接符示例asbc2-连接符1-连接符78耗散值的计算耗散值的计算 k(n,N)k(n,N)=Cn+k(n1,N)+k(ni,N)其中：N为终节点集 Cn为连接符的耗散值.nn1n2niNk(n1,N)k(n2,N)Cnk(ni,N)8耗散值的计算 k(n,N)k(n,N)=Cn+k89目标目标初始节点 解图：9目标目标初始节点 解图：910能解节点能解节点l终节点是能解节点l若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。l若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。10能解节点终节点是能解节点1011不能解节点不能解节点l没有后裔的非终节点是不能解节点。l若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。l若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。11不能解节点没有后裔的非终节点是不能解节点。1112与或图中的局部图与或图中的局部图局部图：(1)单一结点是一个局部图。(2)对一个局部图中的任意叶结点n，选择一个外向连接符K，则该局部图、外向连接符K以及K所连接的n的后继结点一起组成的仍是一个局部图。12与或图中的局部图局部图：(1)单一结点是一个局部图。(21213局部图局部图目标目标初始节点abc13局部图目标目标初始节点abc1314普通图搜索：对单个结点的评价普通图搜索：对单个结点的评价f(n)=g(n)+h(n)对n的评价实际是对从s到n这条路径的评价ns14普通图搜索：对单个结点的评价 f(n)=g(n)+1415与或图与或图:对局部图的评价对局部图的评价目标目标初始节点abc由于“与”节点的存在，单纯对一个节点的评价已经不能反映解图的全面情况。需通过对局部解图进行评价。15与或图:对局部图的评价目标目标初始节点abc由于“与”1516两个过程两个过程l图生成过程，即扩展节点l从最优的局部图中选择一个节点扩展l计算耗散值的过程l对当前的局部图重新计算耗散值16两个过程图生成过程，即扩展节点1617 博弈树搜索博弈树搜索l博弈问题l（1）双人对弈，对垒的双方轮流走步。（2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。（3）零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。17 博弈树搜索博弈问题1718博弈问题为什么可以用与或图表示博弈问题为什么可以用与或图表示l我方走棋:只需从若干个可以走的棋中，选择一个棋走即可。若干个可以走的棋是“或”的关系。l对方走棋：对我方来说，必须能够应付对手的每一种走棋。相当于这些棋是“与”的关系。l博弈问题是一种特殊的与或图。18博弈问题为什么可以用与或图表示我方走棋:1819Grundy博弈：分钱币的游戏博弈：分钱币的游戏 l有一堆数目为N的钱币，由两位选手轮流进行分堆，要求每个选手每次只把其中某一堆分成数目不等的两小堆。例如选手甲把N分成两堆后，轮到选手乙就可以挑其中一堆来分，如此进行下去直到有一位选手先无法把钱币再分成不相等的两堆时就得认输。19Grundy博弈：分钱币的游戏 有一堆数目为N的钱币，由1920MIN:对方对方 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博弈：分钱币的游戏博弈：分钱币的游戏 20MIN:对方 MAX:我方（7,MIN）（6,1,2021分钱币问题的产生式系统描述分钱币问题的产生式系统描述l综合数据库：用无序数字序列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的搜索目标。21分钱币问题的产生式系统描述综合数据库：用无序数字序列x2122l含有MAX符号的节点可看成与节点。l含有MIN符号的节点可看成或节点。lMAX要取胜，必须对所有与节点取胜，但只需 对一个或节点取胜，这就是与或图的一个解图。l寻找MAX的取胜策略等同于求解图。解图代表一种完整的博弈策略。Grundy博弈：搜索策略博弈：搜索策略22含有MAX符号的节点可看成与节点。Grundy博弈：搜索2223中国象棋中国象棋l一盘棋平均走50步，总状态数约为10的161次方。l假设1毫微秒走一步，约需10的145次方年。l结论：不可能穷举。23中国象棋一盘棋平均走50步，总状态数约为10的161次方2324极小极大搜索过程极小极大搜索过程l极小极大搜索方法是博弈树搜索的基本方法，现在博弈树搜索中最常用的-剪枝搜索方法，就是从这一方法发展而来的。24极小极大搜索过程极小极大搜索方法是博弈树搜索的基本方法，2425l通过评价函数对所有棋局势态进行评估。l评价函数值0时，棋局对我方有利，对对方不利。l评价函数值0。l有利于MIN 的棋局势态，f(p)max min =max min因此：当 时，必有max min。35-剪枝：问题：、如何取值，才能使 max必定 3536l若生成某些端节点后，能估计出父节点的或值，并且，则就不必再扩展父节点的其余子节点了(因为这些节点的估值对父节点的倒推值已无任何影响)。-剪枝：剪枝：36若生成某些端节点后，能估计出父节点的或值，并且3637-剪枝：举例剪枝：举例(深度优先搜索深度优先搜索)1-1-1 =-1极大 max极小 min21max若结点4的值是父结点s的所有子结点中的最大值，则s=-1，此时不影响父结点的取值。3-145初始结点s =-1-1此时，若结点4的值不是父结点s的所有子结点中的最大值，则父结点s取其他子结点中的最大值，此时也不影响父结点的取值。37-剪枝：举例(深度优先搜索)1-1-1=-1极大3738-剪枝：举例剪枝：举例(深度优先搜索深度优先搜索)1-1-1 =-1极大 max极小 min21max由于 ，不影响父结点的取值，所以不必再扩展节点4的其他子结点了3-145初始节点s =-1-1-剪枝38-剪枝：举例(深度优先搜索)1-1-1=-1极大3839-剪枝剪枝l具体的剪枝方法如下：(1)对于一个极小值层节点MIN，若能估计出其倒推值 的上界，并且这个值不大于 MIN的父节点(极 大值层节点)的估计倒推值的下界，即，则就不必再扩展该 MIN节点的其余子节点了(因为 这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为剪枝。39-剪枝具体的剪枝方法如下：3940-剪枝剪枝l(2)对于一个极大值层节点MAX，若能估计出其倒推值的下确界，并且这个值不小于 MAX的父节点(一定是极小值层节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为剪枝。40-剪枝(2)对于一个极大值层节点MAX，若能估计出4041-剪枝剪枝l从算法中看到：(1)MAX节点(包括起始节点)的值永不减少；(2)MIN节点(包括起始节点)的值永不增加。在搜索期间，和值的计算如下：(1)一个MAX节点的值等于其后继节点当前最大的最终倒推值。(2)一个MIN节点的值等于其后继节点当前最小的最终倒推值。41-剪枝从算法中看到：(1)MAX节点(包括起始节4142l剪枝的条件：l后辈节点的值祖先节点的值时，剪枝l后辈节点的 值祖先节点的值时，剪枝l简记为：l极小极大，剪枝l极大极小，剪枝42剪枝的条件：4243-剪枝（续）剪枝（续）500300ab-3cdf极大 max极小 min =0 =00极大 max极小 min =-3-343-剪枝（续）500300ab-3cdf极大 max极4344-剪枝（续）剪枝（续）05-333-3022-30-23541-30689-300-303305411-31661abcdefghijkmn极大 max极小 minmaxmin44-剪枝（续）05-333-3022-30-235414445-剪枝的其他应用剪枝的其他应用l故障诊断 A B C Dl风险投资45-剪枝的其他应用故障诊断45