人工智能导论-第2章分析优秀PPT.ppt

《人工智能导论-第2章分析优秀PPT.ppt》由会员分享，可在线阅读，更多相关《人工智能导论-第2章分析优秀PPT.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、其次章其次章 与或图搜寻问题与或图搜寻问题目标目标初始节点sabc1其次章其次章 与或图搜寻问题与或图搜寻问题与或树是用于表示问题及其求解过程的又一种形式化方法。对于一个困难问题，干脆求解往往比较困难，因此通过下述方法进行简化：分解：把一个困难问题简化为若干简洁的子问题，重复此过程，直到不须要再分解或者不能再分解为止。若每个子问题都可求解，则原问题可求解。因此下图称为“与”树。PP3P2P12其次章其次章 与或图搜寻问题与或图搜寻问题等价变换：对于一个困难问题，除了可用等价变换：对于一个困难问题，除了可用“分解分解”方方法进行求解外，还可利用同构或同态的等价变换，把法进行求解外，还可利用同构或

2、同态的等价变换，把它变换为若干个较为简洁求解的新问题。若新问题中它变换为若干个较为简洁求解的新问题。若新问题中有一个可求解，则就得到了原问题的解。因此下图称有一个可求解，则就得到了原问题的解。因此下图称为为“或或”树树PP3P2P13其次章其次章 与或图搜寻问题与或图搜寻问题与或树PP3P2P1P12P11P32P33P3142.1 基本概念基本概念本原问题：不能再分解或变换，而且可以干脆求解的本原问题：不能再分解或变换，而且可以干脆求解的子问题。子问题。端节点与终止节点：没有子节点的节点称为端节点；端节点与终止节点：没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。明显，终止节本

3、原问题所对应的节点称为终止节点。明显，终止节点确定是端节点，但端节点不确定是终止节点。点确定是端节点，但端节点不确定是终止节点。可解节点：满足下列条件之一者，称为可解节点：可解节点：满足下列条件之一者，称为可解节点：1.它是一个终止节点；它是一个终止节点；2.它是一个它是一个“或或”节点，且其子节点中至少有一个是节点，且其子节点中至少有一个是可解节点；可解节点；3.它是一个它是一个“与与”节点，且其子节点中全部都是可解节节点，且其子节点中全部都是可解节点。点。52.1 基本概念基本概念不行解节点：关于可解节点的三个条件不行解节点：关于可解节点的三个条件全部不满足的节点称为不行解节点。全部不满足

4、的节点称为不行解节点。解树：由可解节点构成，并且由这些节解树：由可解节点构成，并且由这些节点可推出初始节点（它对应于原始问题）点可推出初始节点（它对应于原始问题）为可解节点的子树称为解树。为可解节点的子树称为解树。6解树解树PtttPttt7与或树的广度优先搜寻与或树的广度优先搜寻1.把初始节点S0放入OPEN表。2.把OPEN表中的第一个节点（记为节点n)取出放入CLOSED表。3.假如节点n可扩展，则作下列工作：3.1 扩展节点n，将其子节点放入OPEN 表的尾部，并为每个子节点配置指向父节点的指针，以备标识过程运用。3.2 考察这些子节点中有否终止节点。若有，则标识这些终止节点为可解节点

5、，并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。假如初始节点S0也被标识为可解节点，就得到了解树，搜寻成果，退出搜寻过程；假如不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。3.3 转第2步。8与或树的广度优先搜寻（续）与或树的广度优先搜寻（续）4.假如节点n不行扩展，则作下列工作。4.1.标识节点n为不行解节点。4.2.应用不行解标识过程对节点n的先辈节点中不行解的节点进行标识，假如初始节点S0也被标识为不行解节点，则搜寻失败，表明原问题无解，退出搜寻过程；假如不能确定S0为不行解节点，则从OPEN表中删去具有不行解先辈的节点。4.3 转第2步。9与或

6、树的广度优先搜寻：示例与或树的广度优先搜寻：示例2134t1 ABt2 t4 t3 510与或树的广度优先搜寻：示例与或树的广度优先搜寻：示例(1).首先扩展1号节点，得到2号节点和3号节点，由于这两个子节点均不是终止节点，所以接着扩展2号节点。此时OPEN表中只剩下3号节点。(2).扩展2号节点后，得到4号节点和t1节点。此时OPEN表中的节点有：3，4,t1。由于t1是终止节点，则标识它为可解节点，并应用可解标识过程，对其先辈节点中的可解节点进行标识。在此例中，因为t1的父节点是一个“与”节点，因此仅有t1可解尚不能确定2号节点是否为可解节点。所以接着搜寻。下一步扩展的节点是3号节点。11

7、示例示例(续续)扩展3号节点得到5号节点与B节点，两者都不是终止节点，所以接着扩展4号节点。扩展4号节点后得到节点A和t2。由于t2是终止节点，所以标识它为可解节点，并用可解标识过程标识出4、2均为可解节点，但1号节点目前还不能确定它是否是可解节点。此时5号节点是OPEN标中的第一个待考察的节点，所以下一步扩展5号节点。扩展5号节点，得到t3、t4，由于t3、t4均为终止节点，所以被标识为可解节点，通过应用可解标识过程可得到5、3、1号节点均为可解节点。12与或树的有界深度优先搜寻与或树的有界深度优先搜寻1.把初始节点S0放入OPEN表。2.把OPEN表中的第一个节点（记为节点n)取出放入CL

8、OSED表。3.假如节点n的深度大于等于深度界限，则转第5步的5.1步。4.假如节点n可扩展，则作下列工作：4.1 扩展节点n，将其子节点放入OPEN 表的首部，并为每个子节点配置指向父节点的指针，以备标识过程运用。4.2 考察这些子节点中有否终止节点。若有，则标识这些终止节点为可解节点，并应用可解标识过程对其父节点、祖父节点等先辈节点中的可解节点进行标识。假如初始节点S0也被标识为可解节点，就得到了解树，搜寻成果，退出搜寻过程；假如不能确定S0为可解节点，则从OPEN表中删去具有可解先辈的节点。4.3 转第2步。13与或树的有界深度优先搜寻（续）与或树的有界深度优先搜寻（续）5.假如节点n不

9、行扩展，则作下列工作。5.1.标识节点n为不行解节点。5.2.应用不行解标识过程对节点n的先辈节点中不行解的节点进行标识，假如初始节点S0也被标识为不行解节点，则搜寻失败，表明原问题无解，退出搜寻过程；假如不能确定S0为不行解节点，则从OPEN表中删去具有不行解先辈的节点。5.3 转第2步。14与或树的有序搜寻与或树的有序搜寻与或树的有序搜寻是用来求取代价最小的解树的一种搜寻方法，为了求得代价最小的解树，就要在每次确定欲扩展的节点时，先往前多看几步，计算以下扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩展。像这样依据代价确定搜寻路途的方法称为与或树的有序搜寻，它是一种启发式搜寻策略。

10、15与或树的有序搜寻：耗散值的计算与或树的有序搜寻：耗散值的计算 设用c(x,y)表示节点x到其子节点y的代价，则计算节点x的方法如下：假如x是终止节点，则定义节点x的代价h(x)=0;假如x是“或”节点，y1,y2,yn是它的子节点，则节点x的代价由下式计算得到h(x)=minc(x,yi)+h(yi)假如x是“与”节点，则节点x的代价有两种计算方法：和代价法与最大代价法。和代价法：最大代价法：假如x不行扩展，且又不是终止节点，则定义h(x)=。16耗散值（代价值）的计算：示例耗散值（代价值）的计算：示例解树：S0,A,t1和t2。S0,B,D,G,t4和t5。由左边的解树可得：和代价：h(

11、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。S0At1t2EBCDFGt4t5t326512212311217与或树的有序搜寻与或树的有序搜寻计算任一节点x的代价h(x)时，都要求已知其子节点yi的代价h(yi)。但搜寻是自上而下进行的，即先有父节点，后有子节点，除非节点x的全部子节点都是不行扩展节点，否则子节点的

12、代价是不知道的。那么如何计算x的代价值h(x)呢？解决的方法是依据问题本身供应的启发式信息定义一个启发函数，由此函数估算出子节点yi的代价h(yi)，然后再按和代价或者最大代价计算出节点x的代价值h(x)。有了h(x)，节点x的父节点、祖父节点以及直到初始节点S0的各先辈节点的代价h都可自下而上的逐层推算出来。18与或树的有序搜寻与或树的有序搜寻当节点yi被扩展后，也是先用启发函数估算出其子节点的代价，然后再算出h(yi)。此时算出的h(yi)可能与原先估算出的h(yi)不相同，这时应当用后算出的h(yi)取代原先估算出的h(yi)，并且按此h(yi)自下而上地重新计算各先辈节点的h值。当节点

13、yi的子节点又被扩展时，上述过程又要重新进行一遍。总之，每当有一代新的节点生成时，都要自下而上地重新计算其先辈节点的代价，这是一个自上而下地生成节点，又自下而上地计算代价h的反复进行的过程。19与或树的有序搜寻：希望树与或树的有序搜寻：希望树有序搜寻的目的是求出最优解树，即代价最小的树。这就是要求搜寻过程中任一时刻求出的部分解树其代价是最小的。为此，每次选择欲扩展的节点时都应选择有希望成为最优解树一部分的节点进行扩展。由于这些节点及其先辈节点（包括初始节点S0）所构成的与/或树有可能成为最优解树的一部分，因此称它为希望树。希望树：1.初始节点在希望树T中;2.假如节点x在希望树中，则确定有：2

14、.1 假如x是具有节点y1，y2，yn的“或”节点，则具有 h(x)=minc(x,yi)+h(yi)值的那个子节点也应在T中。2.2 假如x 是“与”节点，则它的全部子节点都应在T中。20与或树的有序搜寻：算法与或树的有序搜寻：算法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就是最优

15、解树，成功退出。4.4 否则，从OPEN表中删去具有可解先辈的全部节点。21与或树的有序搜寻：算法（续）与或树的有序搜寻：算法（续）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

16、计算这些子节点的h值及其先辈节点的h值。7.转第2步。22与或树的有序搜寻：示例与或树的有序搜寻：示例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，因此左子树为希望树一次扩展两层，B C E F下面的值均为按某种启发式方法估算出来的23与或树的有序搜寻：示例与或树的有序搜寻：示例S0ACGDEH22232Fh(L)=2,h(M)=6,h(B)=3,h(A)=8,L、B均为可解节点。但节点C目前不能肯定是可解节点，故

17、A和S0也还不能确定为可解节点。左子树仍然是希望树，下面对节点C进行扩展。MLB0022324与或树的有序搜寻：示例与或树的有序搜寻：示例S0ACGDEH22232Fh(N)=2,h(P)=7,h(C)=3,h(A)=8,由此可推算出h(S0)9。BPN0032ML0022252.3 博弈树搜寻博弈树搜寻博弈问题：诸如下棋、打牌、斗争等一类竞争性智能活动称为博弈。其中最为简洁的一种称为“二人零和、全信息、非偶然”博弈。对垒的A、B双方轮番实行行动，博弈的结果只有三种状况：A方胜，B方败；B方胜、A方败；双方战成平局。在对垒过程中，任何一方都了解当前的格局及过去的历史。任何一方在实行行动前都要依

18、据当前的实际状况，进行得失分析，选取对自己最为有利而对对方最为不利的对策，不存在“碰运气”的偶然因素。即双方都是很理智地确定自己的行动。26分钱币问题分钱币问题（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）我方先走对方必胜我方必胜27中国象棋中国象棋一盘棋平均走50步，总状态数约为10的161次方。假设1毫微秒走一步，约需10的145次方年。结论：不行能穷举。28博弈树博弈树在博弈过程中，任何一方都希望自己取得成功。因此，在某

19、一方当前有多个行动方案可供选择时，他总是选择对自己最为有利而对对方最为不利的那个行动方案。此时，假如我们站在A方的立场上，则可供A方选择的若干行动方案之间是“或”关系，因为主动权操在A方手里。但是若B方也有若干个可供选择的方案，则对方来说这些行动方案之间是“与”关系，因为这时主动权操在B方，这些可供选择方案的任何一个被B选中，A方必需考虑到对自己最不利的状况的发生。若把上述博弈过程用图表示出来，得到的是一棵“与/或树”。这里要特殊指出，该“与/或”树是始终站在某一方（例如A方）的立场上得出，决不行一会儿站在这一方的立场上，一会儿又站在另一方的立场上。描述博弈过程的与或树称为博弈树，它有如下特点

20、：1.博弈的初始格局是初始节点；2.在博弈树中，“或”节点和“与”节点逐层交替出现的。自己一方扩展的节点之间是“或”关系，对方扩展的节点之间是“与”关系。双方轮番地扩展节点。3.全部能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；全部使对方获胜的终局都是不行解节点。29极大微小方法极大微小方法基本思想：1.设博弈的一方为A、一方为B。极大微小分析法是为其中的一方（如A）找寻一个最优行动方案的方法。2.为了找到当前的最优行动方案，须要对各个方案可能产生的后果进行比较。具体地说，就是要考虑每一方案实施后对方可能实行的全部行动，并计算可能的得分。3.为计算得分，须要依据问题的特性信息定义一

21、个估价函数，用来估算当前博弈树端节点的得分。此时估算出来的得分称为静态估值。4.当端节点的估值计算出来后，再推算出父节点的得分。其方法是：对“或”节点，选其子节点中一个最大的得分作为父节点的得分，这是为了使自己在可供选择的方案中选一个对自己最有利的方案；对“与”节点，选其子节点中一个最小的得分作为父节点的得分，这是为了立足于最坏的状况。这样计算出的父节点的得分称为倒推值。5.假如一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。301，微小极大过程，微小极大过程05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小ab31极大微

22、小分析法：一子棋极大微小分析法：一子棋一子棋游戏：估价函数定义如下设棋局为P，估价函数为e(P)：1.若P是A必胜的棋局，则e(P)；2.若P是B必胜的棋局，则e(P)；3.若P是输赢未定的棋局，则e(P)=e(+P)-e(-P)。其中，e(+P)表示在棋局P上添上全部的a后直线的数目，e(+P)表示在棋局P上添上全部的b后直线的数目。32极大微小分析法：一子棋极大微小分析法：一子棋aababababaababbaaabababbabaS0S3S2S4S5S11010-1-10-10-221-11-21A的第一着棋生成的博弈树。每一着棋都要导致博弈树深度加2：一层是自己，一层是对方。33-剪枝

23、剪枝对于一个“或”节点来说，它取当前子节点中的最大最大倒推值作为它倒推值的下界下界，称此值为值；对于一个“与”节点来说，它取当前子节点中的最小最小倒推值作为它倒推值的上界上界，称此值为值；34-剪枝剪枝S0ABEDCHGFNMLPQXXISRXJTXKUXXX2841-2591-521-225251-5112“与”节点G的值不能上升其父节点C的值，则对节点G以下的分枝可停止搜寻，并使G的倒推值为。这种剪枝称为剪枝“或”节点D的值不能降低其父节点A的值，则对节点D以下的分枝可停止搜寻，并使D的倒推值为。这种剪枝称为剪枝。35-剪枝剪枝由上面的例子可以归纳出：1.任何“或”节点x的值假如不能降低其父节点的值，则对节点x以下的分枝可停止搜寻，并使x的倒推值为。这种剪枝称为剪枝。2.任何“与”节点x的值假如不能上升其父节点的值，则对节点x以下的分枝可停止搜寻，并使x的倒推值为。这种剪枝称为剪枝。在-剪枝技术中，一个节点的第一个子节点的倒推值（或估值）是很重要的。对于一个“或”节点，假如估值最高的子节点最先生成，或者对于一个“与”节点，估值最低的子节点最先生成，则被剪除的节点数最多，搜寻的效率最高。这称为最优-剪枝法。36The End作业：P56习题1.10作业：P74习题2.637