人工智能导论_第2章课题

1第二章与或图搜索问题目标目标初始节点sabc2第二章与或图搜索问题•与或树是用于表示问题及其求解过程的又一种形式化方法。•对于一个复杂问题，直接求解往往比较困难，因此通过下述方法进行简化：•分解：把一个复杂问题简化为若干简单的子问题，重复此过程，直到不需要再分解或者不能再分解为止。若每个子问题都可求解，则原问题可求解。因此下图称为“与”树。PP3P2P13第二章与或图搜索问题•等价变换：对于一个复杂问题，除了可用“分解”方法进行求解外，还可利用同构或同态的等价变换，把它变换为若干个较为容易求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。因此下图称为“或”树PP3P2P14第二章与或图搜索问题•与或树PP3P2P1P12P11P32P33P3152.1基本概念•本原问题：不能再分解或变换，而且可以直接求解的子问题。•端节点与终止节点：没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。显然，终止节点一定是端节点，但端节点不一定是终止节点。•可解节点：满足下列条件之一者，称为可解节点：•1.它是一个终止节点；•2.它是一个“或”节点，且其子节点中至少有一个是可解节点；•3.它是一个“与”节点，且其子节点中全部都是可解节点。62.1基本概念•不可解节点：关于可解节点的三个条件全部不满足的节点称为不可解节点。•解树：由可解节点构成，并且由这些节点可推出初始节点（它对应于原始问题）为可解节点的子树称为解树。7解树PtttPttt8与或树的广度优先搜索•1.把初始节点S0放入OPEN表。•2.把OPEN表中的第一个节点（记为节点n)取出放入CLOSED表。•3.如果节点n可扩展，则作下列工作：•3.1扩展节点n，将其子节点放入OPEN表的尾部，并为每个子节点配置指向父节点的指针，以备标识过程使用。•3.2考察这些子节点中有否终止节点。若有，则标识这些终止节点为可解节点，并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。如果初始节点S0也被标识为可解节点，就得到了解树，搜索成果，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。•3.3转第2步。9与或树的广度优先搜索（续）•4.如果节点n不可扩展，则作下列工作。•4.1.标识节点n为不可解节点。•4.2.应用不可解标识过程对节点n的先辈节点中不可解的节点进行标识，如果初始节点S0也被标识为不可解节点，则搜索失败，表明原问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从OPEN表中删去具有不可解先辈的节点。•4.3转第2步。10与或树的广度优先搜索：示例2134t1ABt2t4t3511与或树的广度优先搜索：示例•(1).首先扩展1号节点，得到2号节点和3号节点，由于这两个子节点均不是终止节点，所以接着扩展2号节点。此时OPEN表中只剩下3号节点。•(2).扩展2号节点后，得到4号节点和t1节点。此时OPEN表中的节点有：3，4,t1。由于t1是终止节点，则标识它为可解节点，并应用可解标识过程，对其先辈节点中的可解节点进行标识。在此例中，因为t1的父节点是一个“与”节点，因此仅有t1可解尚不能确定2号节点是否为可解节点。所以继续搜索。下一步扩展的节点是3号节点。12示例(续)•扩展3号节点得到5号节点与B节点，两者都不是终止节点，所以接着扩展4号节点。•扩展4号节点后得到节点A和t2。由于t2是终止节点，所以标识它为可解节点，并用可解标识过程标识出4、2均为可解节点，但1号节点目前还不能确定它是否是可解节点。此时5号节点是OPEN标中的第一个待考察的节点，所以下一步扩展5号节点。•扩展5号节点，得到t3、t4，由于t3、t4均为终止节点，所以被标识为可解节点，通过应用可解标识过程可得到5、3、1号节点均为可解节点。13与或树的有界深度优先搜索•1.把初始节点S0放入OPEN表。•2.把OPEN表中的第一个节点（记为节点n)取出放入CLOSED表。•3.如果节点n的深度大于等于深度界限，则转第5步的5.1步。•4.如果节点n可扩展，则作下列工作：•4.1扩展节点n，将其子节点放入OPEN表的首部，并为每个子节点配置指向父节点的指针，以备标识过程使用。•4.2考察这些子节点中有否终止节点。若有，则标识这些终止节点为可解节点，并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。如果初始节点S0也被标识为可解节点，就得到了解树，搜索成果，退出搜索过程；如果不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。•4.3转第2步。14与或树的有界深度优先搜索（续）•5.如果节点n不可扩展，则作下列工作。•5.1.标识节点n为不可解节点。•5.2.应用不可解标识过程对节点n的先辈节点中不可解的节点进行标识，如果初始节点S0也被标识为不可解节点，则搜索失败，表明原问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从OPEN表中删去具有不可解先辈的节点。•5.3转第2步。15与或树的有序搜索•与或树的有序搜索是用来求取代价最小的解树的一种搜索方法，为了求得代价最小的解树，就要在每次确定欲扩展的节点时，先往前多看几步，计算以下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。像这样根据代价决定搜索路线的方法称为与或树的有序搜索，它是一种启发式搜索策略。16与或树的有序搜索：耗散值的计算设用c(x,y)表示节点x到其子节点y的代价，则计算节点x的方法如下：1.如果x是终止节点，则定义节点x的代价h(x)=0;2.如果x是“或”节点，y1,y2,…,yn是它的子节点，则节点x的代价由下式计算得到h(x)=min{c(x,yi)+h(yi)}3.如果x是“与”节点，则节点x的代价有两种计算方法：和代价法与最大代价法。4.和代价法：5.最大代价法：6.如果x不可扩展，且又不是终止节点，则定义h(x)=。n1iii))y(h)y,x(c()x(h)}y(h)y,x(c{)x(hiini1max17耗散值（代价值）的计算：示例•解树：S0,A,t1和t2。S0,B,D,G,t4和t5。•由左边的解树可得：•和代价：h(A)=11,h(S0)=13•最大代价：h(A)=6,h(S0)=8•由右边的解树可得：•和代价：h(G)=3,h(D)=4,h(B)=6,h(S0)=8•最大代价：h(G)=2,h(D)=3,h(B)=5,h(S0)=7•显然，若按和代价计算，右边的解树是最优解树，其代价为8；若按最大代价计算，右边解树解树仍然是最优解树，其代价为7。S0At1t2EBCDFGt4t5t326512212311218与或树的有序搜索•计算任一节点x的代价h(x)时，都要求已知其子节点yi的代价h(yi)。但搜索是自上而下进行的，即先有父节点，后有子节点，除非节点x的全部子节点都是不可扩展节点，否则子节点的代价是不知道的。那么如何计算x的代价值h(x)呢？•解决的办法是根据问题本身提供的启发式信息定义一个启发函数，由此函数估算出子节点yi的代价h(yi)，然后再按和代价或者最大代价计算出节点x的代价值h(x)。有了h(x)，节点x的父节点、祖父节点以及直到初始节点S0的各先辈节点的代价h都可自下而上的逐层推算出来。19与或树的有序搜索•当节点yi被扩展后，也是先用启发函数估算出其子节点的代价，然后再算出h(yi)。此时算出的h(yi)可能与原先估算出的h(yi)不相同，这时应该用后算出的h(yi)取代原先估算出的h(yi)，并且按此h(yi)自下而上地重新计算各先辈节点的h值。当节点yi的子节点又被扩展时，上述过程又要重新进行一遍。总之，每当有一代新的节点生成时，都要自下而上地重新计算其先辈节点的代价，这是一个自上而下地生成节点，又自下而上地计算代价h的反复进行的过程。20与或树的有序搜索：希望树•有序搜索的目的是求出最优解树，即代价最小的树。这就是要求搜索过程中任一时刻求出的部分解树其代价是最小的。为此，每次选择欲扩展的节点时都应挑选有希望成为最优解树一部分的节点进行扩展。由于这些节点及其先辈节点（包括初始节点S0）所构成的与/或树有可能成为最优解树的一部分，因此称它为希望树。•希望树：•1.初始节点在希望树T中;•2.如果节点x在希望树中，则一定有：•2.1如果x是具有节点y1，y2，…，yn的“或”节点，则具有h(x)=min{c(x,yi)+h(yi)}值的那个子节点也应在T中。•2.2如果x是“与”节点，则它的全部子节点都应在T中。21与或树的有序搜索：算法•1.把初始节点S0放入OPEN表中。•2.求出希望树T，即根据当前搜索树中节点的代价h求出以S0为根的希望树T。•3.依次把OPEN表中T的端节点N选出放入CLOSED表中。•4.如果节点N是终止节点，则作如下工作：•4.1标识N为可解节点。•4.2对T应用可解标识过程，把N的先辈节点中的可解节点都标识为可解节点。•4.3若初始节点S0能被标识为可解节点，则T就是最优解树，成功退出。•4.4否则，从OPEN表中删去具有可解先辈的所有节点。22与或树的有序搜索：算法（续）•5.如果节点N不是终止节点，且它不可扩展，则作下列工作：•5.1标识N为不可解节点。•5.2对T应用不可解标识过程，把N的先辈节点中的不可解节点都标识为不可解节点。•5.3若初始节点S0也被标识为不可解节点，则失败退出。•5.4否则，从OPEN表中删去具有不可解先辈的所有节点。•6.如果节点N不是终止节点，但它可扩展，则作下列工作：•6.1扩展节点N，产生N的所有子节点。•6.2把这些子节点都放入OPEN表中，并为每个子节点配置指向父节点（节点N）的指针。•6.3计算这些子节点的h值及其先辈节点的h值。•7.转第2步。23与或树的有序搜索：示例S0ABCDEF3332h(A)=8,h(D)=7,h(S0)=8,右子树为希望树S0ABCGDEH22232FH(G)=7,h(H)=6,h(E)=7,h(D)=11,S0的右子树算出的h(S0)＝12，而左子树的h(S0)＝9，因此左子树为希望树一次扩展两层，BCEF下面的值均为按某种启发式方法估算出来的24与或树的有序搜索：示例S0ACGDEH22232Fh(L)=2,h(M)=6,h(B)=3,h(A)=8,L、B均为可解节点。但节点C目前不能肯定是可解节点，故A和S0也还不能确定为可解节点。左子树仍然是希望树，下面对节点C进行扩展。MLB0022325与或树的有序搜索：示例S0ACGDEH22232Fh(N)=2,h(P)=7,h(C)=3,h(A)=8,由此可推算出h(S0)＝9。BPN0032ML0022262.3博弈树搜索•博弈问题：诸如下棋、打牌、战争等一类竞争性智能活动称为博弈。其中最为简单的一种称为“二人零和、全信息、非偶然”博弈。•对垒的A、B双方轮流采取行动，博弈的结果只有三种情况：A方胜，B方败；B方胜、A方败；双方战成平局。•在对垒过程中，任何一方都了解当前的格局及过去的历史。•任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自己最为有利而对对方最为不利的对策，不存在“碰运气”的偶然因素。即双方都是很理智地决定自己的行动。27分钱币问题（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）我方先走对方必胜我方必胜28中国象棋•一盘棋平均走50步，总状态数约为10的161次方。•假设1毫微秒走一步，约需10的145次方年。•结论：不可能穷举。29博弈树•在博弈过程中，任何一方都希望自己取得胜利。因此，在某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利而对对方最为不利的那个行动方案。此时，如果我们站在A方的立场上，则可供A方选择的若干行动方案之间是“或”关系，因为主动权操在A方手里。