搜索与或图搜索.ppt

,第 四章,与或图搜索,与或图搜索,第四章-2,内容,4.0 与或树表示 4.1 与/或树的一般搜索 4.2 与/或树的广度优先搜索 4.3 与/或树的深度优先搜索 4.4 与或树的启发式搜索 4.5 博弈树的启发式搜索,与或图搜索,第四章-3,4.0 与或树表示,不同于状态空间方法的另外一种形式化方法。基本思想：当一个问题比较复杂时，直接进行求解往往比较困难。可通过归约（分解或变换），将它转化为一系列较简单的问题。通过对这些较简单问题的求解来实现对原问题的求解。,与或图搜索,第四章-4,4.0 与或树表示,【例4.0】设有四边形ABCD和ABCD，证明它们全等。,与或图搜索,第四章-5,4.0 与或树表示,分析：原问题分解为两个子问题：,与或图搜索,第四章-6,4.0 与或树表示,与或图搜索,第四章-7,4.0 与或树表示,4.0.1 分解问题P可以归约为一组子问题P1,P2,Pn。只有当所有子问题Pi(i1，2，n)都有解时,原问题P才有解。即分解所得到的子问题的“与”和原问题P等价。与树K-连接符,与或图搜索,第四章-8,4.0 与或树表示,4.0.2 等价变换问题P可以归约为一组子问题P1,P2,Pn。这些子问题Pi中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解。即变换所得到的子问题的“或”与原问题P等价。或树把一个原问题变换为若干个子问题可用一个“或树”来表示。,与或图搜索,第四章-9,4.0 与或树表示,4.0.3 与或树如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其归约过程可用一个“与/或树”来表示。,原始问题,本原问题（终止节点）,端节点没有子节点的节点，即叶子节点；终止节点可解节点，即本原问题。,t,与或图搜索,第四章-10,4.0 与或树表示,P,t,t,t,4.0.4 解树由可解节点构成，并且由这些可解节点可以推出初始节点(它对应着原始问题)为可解节点的子树。在解树中一定包含初始节点。,与或图搜索,第四章-11,4.0 与或树表示,【例4.1】三阶梵塔问题。解：用三元组表示问题在任一时刻的状态：(i,j,k)i：代表金片C所在的钢针号；j:代表金片B所在的钢针号；k;代表金片A所在的钢针号；,1 2 3,A,B,C,(1,1,1)-(3,3,3),(1,1,1)-(1,2,2),(1,2,2)-(3,2,2),(3,2,2)-(3,3,3),(1,1,1)-(1,1,3),(1,1,3)-(1,2,3),(1,2,3)(1,2,2),(3,2,2)-(3,2,1),(3,2,1)(3,3,1),(3,3,1)(3,3,3),三阶梵塔问题的与或树,在该与/或树中，有7个终止节点，它们分别对应着7个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：,与或图搜索,第四章-14,4.0 与或树表示,与或图搜索,第四章-15,内容,4.0 与或树表示 4.1 与/或树的一般搜索 4.2 与/或树的广度优先搜索 4.3 与/或树的深度优先搜索 4.4 与或树的启发式搜索 4.5 博弈树的启发式搜索,与或图搜索,第四章-16,4.1 与/或树的一般搜索,与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：（1）把原始问题作为初始节点S0，并把它作为当前节 点；（2）应用分解或等价变换操作对当前节点进行扩展；（3）为每个子节点设置指向父节点的指针；（4）选择合适的子节点作为当前节点，反复执行第（2）步和第（3）步，在此期间需要多次调用可解 标记过程或不可解标记过程，直到初始节点被标 记为可解节点或不可解节点为止。,与或图搜索,第四章-17,4.1 与/或树的一般搜索,在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。可解标记过程由可解子节点来确定其父节点、祖父节点为可解节点的过程。不可解标记过程由不可解子节点来确定其父节点、祖父节点为不可解节点的过程。,与或图搜索,第四章-18,4.1 与/或树的一般搜索,搜索解树的过程中，节点删除策略：如果搜索过程确定某个节点为可解节点，则其不 可解的后裔节点就可从搜索树中删去；如果搜索过程能确定某个节点为不可解节点，则 其后裔节点也可从搜索树中删去。,与或图搜索,第四章-19,内容,4.0 与或树表示 4.1 与/或树的一般搜索 4.2 与/或树的广度优先搜索 4.3 与/或树的深度优先搜索 4.4 与或树的启发式搜索 4.5 博弈树的启发式搜索,与或图搜索,第四章-20,4.2 与/或树的广度优先搜索,与/或树的广度优先搜索算法：（1）把初始节点S0 放人Open表中；（2）把Open表的第一个节点取出放入Closed表，并记该节点 为n；（3）如果节点n可扩展，则做下列工作：扩展节点n，将其子节点放入Open表的尾部，并为每一个子 节点设置指向父节点的指针；考察这些子节点中是否有终止节点。若有，则标记这些终 止节点为可解节点，并用可解标记过程对其父节点及先辈 节点中的可解节点进行标记。如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点；转第（2）步。,与或图搜索,第四章-21,4.2 与/或树的广度优先搜索,搜索算法（续）：（4）如果节点n不可扩展，则做下列工作：标记节点n为不可解节点；应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点；转第（2）步。,【例4.2】t1、t2、t3的节点是终止节点，A、B、C为不可解的端节点,(1)1 2 3 1,(2)2 3 A 4 1 2,(3)3 A 4 5 1 2 3 t1,(4)A 4 5,(5)4 5 B 1 2 3 t1 4 t2,(6)5 B 1 2 3 t1 4 t2 5 t3,(7)搜索成功,解树:1,2,3,4,5,t1,t2,t3,扩展节点,Open 列表,Closed列表,与或图搜索,第四章-23,内容,4.0 与或树表示 4.1 与/或树的一般搜索 4.2 与/或树的广度优先搜索 4.3 与/或树的深度优先搜索 4.4 与或树的启发式搜索 4.5 博弈树的启发式搜索,与或图搜索,第四章-24,4.3 与/或树的深度优先搜索,与/或树的深度优先搜索算法：（1）把初始节点S0放入 Open表中；（2）把Open表的第一个节点取出放入Closed表，并记该节点为 n；（3）如果节点n的深度等于dm，则转第（5）步的第 点；（4）如果节点n可扩展，则做下列工作：扩展节点 n，将其子节点放入 Open表的首部，并为每一 个子节点设置指向父节点的指针；考察这些子节点中是否有终止节点。若有，则标记这些 终止节点为可解节点，并用可解标记过程对其父节点及 先辈节点中的可解节点进行标记。如果初始节点S0能够 被标记为可解节点，就得到了解树，搜索成功，退出搜 索过程；如果不能确定S0为可解节点，则从Open表中删 去具有可解先辈的节点；转第（2）步。,与或图搜索,第四章-25,4.3 与/或树的深度优先搜索,（5）如果节点n不可扩展，则做下列工作：标记节点n为不可解节点；应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定为不可解节点，则从Open表中删去具有不可解先辈的节点；转第（2）步。,与或图搜索,第四章-26,4.3 与/或树的深度优先搜索,【例4.3】对上例所给出的与或树，若按有解深度优先搜索，且给定dm=4。则其扩展节点的顺序为：1，3，5，2，4其解树与上例相同。,1,2,3,A,4,t1,t3,C,B,t2,5,与或图搜索,第四章-27,内容,4.0 与或树表示 4.1 与/或树的一般搜索 4.2 与/或树的广度优先搜索 4.3 与/或树的深度优先搜索 4.4 与或树的启发式搜索 4.5 博弈树的启发式搜索,与或图搜索,第四章-28,4.4 与或树的启发式搜索,与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树（希望树）。,4.4.1 解树的代价与希望树最优解树 指代价最小的那棵解树。,与或图搜索,第四章-29,4.4 与或树的启发式搜索,如何计算解树的代价？,目标,目标,初始节点,a,b,c,与或图搜索,第四章-30,4.4 与或树的启发式搜索,解树的代价可按如下规则计算：（1）若n为终止节点：（2）若n为或节点，且子节点为n1，n2，nk，（3）若n为与节点，且子节点为n1，n2，nk，和代价法：最大代价法：（4）若n是端节点，但又不是终止节点：（5）根节点的代价即为解树的代价。,【例4.4】计算解树的代价。左边的解树和代价：最大代价：右边的解树和代价：最大代价：,终止节点：t1,t2,t3 和 t4 端节点：E 和 F,与或图搜索,第四章-32,4.4 与或树的启发式搜索,希望树为了找到最优解树，搜索过程的任何时刻都应该选择那些最有希望成为最优解树一部分的节点进行扩展。由这些节点及其父节点所构成的子树，称为希望树。【定义】希望解树T（1）初始节点S0在希望树T中；（2）如果n是具有子节点n1，n2，nk的或节点，则n的 某个子节点ni在希望树T中的充分必要条件是:h（ni）=min c（n，ni）h（ni）1ik（3）如果n是与节点，则n的全部子节点都在希望树T中。,与或图搜索,第四章-33,4.4 与或树的启发式搜索,4.4.2 与或树的启发式搜索过程与或树的启发式搜索过程是不断地选择、修正希望树的过程，其搜索过程如下：（1）把初始节点S0放入Open表中，计算h（S0）；（2）计算希望树T；（3）依次在Open表中取出T的端节点放入Closed表，并 记该节点为n；（4）如果节点n为终止节点，则做下列工作：标记节点n为可解节点；在T上应用可解标记过程，对n的先辈节点中的所有可解节点进行标记；如果初始节点S0能够被标记为可解节点，则T就是最优解树，成功退出；否则，从Open表中删去具有可解先辈的所有节点；转第（2）步。,与或图搜索,第四章-34,4.4 与或树的启发式搜索,（5）如果节点n不是终止节点，但可扩展，则做下列工作：扩展节点n，生成n的所有子节点；把这些子节点都放入 Open表中，并为每一个子节点设置指向父节点 n的指针；计算这些子节点及其先辈节点的h值；转第（2）步。（6）如果节点n不是终止节点，且不可扩展，则做下列工作：标记节点n为不可解节点；在T上应用不可解标记过程，对n的先辈节点中的所有不可解节点进行标记；如果初始节点S。能够被标记为不可解节点，则问题无解，失败退出；否则，从Open表中删去具有不可解先辈的所有节点；转第（2）步。,与或图搜索,第四章-36,4.4 与或树的启发式搜索,【例4.5】假设搜索过程每次扩展节点时都同扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。,8,8,7,希望树T:扩展节点 S0 后,与或图搜索,第四章-37,4.4 与或树的启发式搜索,S0,A,D,B,C,E,F,8,3,3,2,3,2,2,2,7,7,6,11,9,S0,A,D,B,C,E,F,8,3,3,2,3,2,2,2,7,7,6,11,9,G,K,H,I,L,J,0,0,2,2,2,6,与或图搜索,第四章-38,4.4 与或树的启发式搜索,9,与或图搜索,第四章-39,内容,4.0 与或树表示 4.1 与/或树的一般搜索 4.2 与/或树的广度优先搜索 4.3 与/或树的深度优先搜索 4.4 与或树的启发式搜索 4.5 博弈树的启发式搜索,与或图搜索,第四章-40,4.5 博弈树的启发式搜索,4.5.1 概述机遇性博弈存在不可预测性的博弈。双人完备信息博弈两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。任何一方走步时，都是选择对自己最为有利，而对另一方最为不利的行动方案。假设博弈的一方为MAX，另一方为MIN。在博弃过程的每一步，可供MAX和MIN选择的行动方案都可能有多种。,与或图搜索,第四章-41,4.5 博弈树的启发式搜索,MIN,MAX,MIN,MAX,MIN,MAX,分钱币问题,对方先走,我方必胜,与或图搜索,第四章-42,4.5 博弈树的启发式搜索,博弈树把双人完备信息博弈过程用图表示出来，就可得到一棵与/或树。下一步该MAX走步的节点称为MAX节点。下一步该MIN走步的节点称为MIN节点。博弈树具有如下特点：博弈的初始状态是初始节点；博弈树中的“或”节点和“与”节点是逐层交替出现 的；整个博弈过程始终站在某一方的立场上，所有能使自 己一方获胜的终局都是本原问题，相应的节点是可解 节点；所有使对方获胜的终局都是不可解节点。,与或图搜索,第四章-43,4.5 博弈树的启发式搜索,假定站在MAX方的立场：可供自己选择的行动方案之间是“或”的关系。原因是主动权掌握在MAX手里，选择哪个方案完全是由自己决定的。可供MIN选择的行动方案之间则是“与”的关系。原因是主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中。MAX必须防止那种对自己最为不利的情况的发生。,与或图搜索,第四章-44,4.5 博弈树的启发式搜索,4.5.2 针对可穷举搜索情况极大极小过程,与或图搜索,第四章-45,4.5 博弈树的启发式搜索,4.5.3 固定深度的极大极小过程对于某些情况，要生成整个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树n-层预判（n-ply look-ahead）。（1）利用估价函数f(n)对叶节点进行静态评估：如果该节点对MAX有利，其估价函数取正值；如果该节点对MIN有利，其估价函数取负值；如果该节点对双方有利，其估价函数取接近于0的值。（2）计算非叶节点的值，必须从叶节点向上倒退MAX节点：其倒退值应该取其后继节点估值的最大值。MIN节点：其倒推值应该取其后继节点估值的最小值。（3）重复步骤（2），直至求出初始节点的倒推值。,与或图搜索,第四章-46,4.5 博弈树的启发式搜索,对假想状态空间的4层预判极小极大过程，叶子节点显示了启发值，内部状态显示了向上传播的值,与或图搜索,第四章-47,4.5 博弈树的启发式搜索,【例4.6】九宫游戏。设MAX方的棋子用标记，MIN方的棋子用标记，并规定MAX方先走步。解：为了对叶节点进行静态估值，规定估价函数e（P）如下：若 P是 MAX的必胜局，则 e（P）=+若 P是 MIN的必胜局，则 e（P）=-若P对MAX、MIN都是胜负未定局，则e(P)=e(+P)e(-P)e（+P）：棋局 P上有可能使成三子一线的数目。e（-P）：棋局 P上有可能使成三子一线的数目。,一字棋棋盘,与或图搜索,第四章-48,4.5 博弈树的启发式搜索,X有6条可能的胜利路线,O有5条可能的胜利路线,P,P,P,X有4条可能的胜利路线,O有6条可能的胜利路线,X有5条可能的胜利路线,O有4条可能的胜利路线,应用到九宫游戏开局移动的2层预判极小极大过程,两种可能的MAX第二步移动,对X在接近终局的移动应用极小极大过程,与或图搜索,第四章-52,4.5 博弈树的启发式搜索,【例4.7】,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,极大,极小,a,b,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,0,4,1,-3,-3,6,8,9,与或图搜索,第四章-53,4.5 博弈树的启发式搜索,4.5.4-剪枝极小极大过程性能分析：极小极大过程需要对搜索空间进行两遍分析，第一遍是向下降到预判层并在那里应用启发评估，第二遍是沿树向上传播评估值。极小极大过程是先生成与/或树，然后再计算各节点的估值，这种生成节点和计算估值相分离的搜索方式，需要生成规定深度内的所有节点（包括许多可以被更智能的算法所忽略或修剪掉的分支），因此搜索效率较低。,3,2,3,与或图搜索,第四章-54,4.5 博弈树的启发式搜索,-搜索的基本思想：-搜索并不搜索预判深度的整个空间，而是以深度优先的方式前进。在搜索中产生两个值，分别称为和。值与MAX节点相关联，且为当前子节点的最大倒推值作为下界（从不减少）。值与MIN节点相关联，且为当前子节点的最小倒推值作为上界（从不增大）。,F,K,L,M,8,4,6,8,MAX的值,F,K,L,M,4,8,6,4,MIN 的值,与或图搜索,第四章-55,4.5 博弈树的启发式搜索,-剪枝的规则如下：任何MAX节点n的值大于或等于它先辈节点的值，则n以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。任何MIN节点n的值小于或等于它先辈节点的值，则n以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。,C,F,G,K,L,M,N,4,8,6,1,4,4,l,C,F,G,K,L,M,N,4,2,1,6,4,4,6,剪枝,剪枝,S0,A,B,C,D,F,G,H,E,I,J,K,L,M,N,P,Q,R,S,4,8,6,1,5,8,0,-6,4,4,l,4,5,5,0,0,4,-6,0,-剪枝的例子,与或图搜索,第四章-57,4.5 博弈树的启发式搜索,对假想状态空间的4层预判极小极大过程，叶子节点显示了启发值，内部状态显示了向上传播的值,与或图搜索,第四章-58,4.5 博弈树的启发式搜索,A有=3（A将不会大于3）B是剪枝，因为53C有=3（C将不会小于3）D是剪枝，因为03E是剪枝，因为23C是3,与或图搜索,第四章-59,思考题,-剪枝,0,-3,3,-3,-3,-2,1,-3,6,-3,0,3,1,6,0,1,1,极大,极小,a,b,0,5,-3,3,3,-3,0,2,2,-3,0,-2,3,0,4,1,-3,-3,6,8,9,