搜索
与或图搜索第四章-2内容4.0与或树表示4.1与/或树的一般搜索4.2与/或树的广度优先搜索4.3与/或树的深度优先搜索4.4与／或树的启发式搜索4.5博弈树的启发式搜索与或图搜索第四章-34.0与或树表示不同于状态空间方法的另外一种形式化方法。基本思想：当一个问题比较复杂时，直接进行求解往往比较困难。可通过归约（分解或变换），将它转化为一系列较简单的问题。通过对这些较简单问题的求解来实现对原问题的求解。与或图搜索第四章-44.0与或树表示【例4.0】设有四边形ABCD和A′B′C′D′，证明它们全等。与或图搜索第四章-54.0与或树表示分析：原问题分解为两个子问题：与或图搜索第四章-64.0与或树表示与或图搜索第四章-74.0与或树表示4.0.1分解问题P可以归约为一组子问题{P1,P2,……,Pn}。只有当所有子问题Pi(i＝1，2，……，n)都有解时,原问题P才有解。即分解所得到的子问题的“与”和原问题P等价。与树K-连接符P1P2P3P…...K个与或图搜索第四章-84.0与或树表示4.0.2等价变换问题P可以归约为一组子问题{P1,P2,……,Pn}。这些子问题Pi中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解。即变换所得到的子问题的“或”与原问题P等价。或树把一个原问题变换为若干个子问题可用一个“或树”来表示。P1P2P3P与或图搜索第四章-94.0与或树表示4.0.3与或树如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其归约过程可用一个“与/或树”来表示。PP1P2P3P31P32P33P11P12原始问题本原问题（终止节点）端节点———没有子节点的节点，即叶子节点；终止节点——可解节点，即本原问题。t与或图搜索第四章-104.0与或树表示Pttt4.0.4解树由可解节点构成，并且由这些可解节点可以推出初始节点(它对应着原始问题)为可解节点的子树。在解树中一定包含初始节点。与或图搜索第四章-114.0与或树表示【例4.1】三阶梵塔问题。解：用三元组表示问题在任一时刻的状态：(i,j,k)i：代表金片C所在的钢针号；j:代表金片B所在的钢针号；k;代表金片A所在的钢针号；123123ABC123(1,1,1)123(1,2,2)123(3,2,2)123(3,3,3)ABC(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个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：与或图搜索第四章-144.0与或树表示目标目标初始节点sabc与或图搜索第四章-15内容4.0与或树表示4.1与/或树的一般搜索4.2与/或树的广度优先搜索4.3与/或树的深度优先搜索4.4与／或树的启发式搜索4.5博弈树的启发式搜索与或图搜索第四章-164.1与/或树的一般搜索与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：（1）把原始问题作为初始节点S0，并把它作为当前节点；（2）应用分解或等价变换操作对当前节点进行扩展；（3）为每个子节点设置指向父节点的指针；（4）选择合适的子节点作为当前节点，反复执行第（2）步和第（3）步，在此期间需要多次调用可解标记过程或不可解标记过程，直到初始节点被标记为可解节点或不可解节点为止。与或图搜索第四章-174.1与/或树的一般搜索在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。可解标记过程由可解子节点来确定其父节点、祖父节点为可解节点的过程。不可解标记过程由不可解子节点来确定其父节点、祖父节点为不可解节点的过程。与或图搜索第四章-184.1与/或树的一般搜索搜索解树的过程中，节点删除策略：①如果搜索过程确定某个节点为可解节点，则其不可解的后裔节点就可从搜索树中删去；②如果搜索过程能确定某个节点为不可解节点，则其后裔节点也可从搜索树中删去。与或图搜索第四章-19内容4.0与或树表示4.1与/或树的一般搜索4.2与/或树的广度优先搜索4.3与/或树的深度优先搜索4.4与／或树的启发式搜索4.5博弈树的启发式搜索与或图搜索第四章-204.2与/或树的广度优先搜索与/或树的广度优先搜索算法：（1）把初始节点S0放人Open表中；（2）把Open表的第一个节点取出放入Closed表，并记该节点为n；（3）如果节点n可扩展，则做下列工作：①扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针；②考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点；③转第（2）步。与或图搜索第四章-214.2与/或树的广度优先搜索搜索算法（续）：（4）如果节点n不可扩展，则做下列工作：①标记节点n为不可解节点；②应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点；③转第（2）步。【例4.2】t1、t2、t3的节点是终止节点，A、B、C为不可解的端节点123A4t1t3CBt25(1)1231(2)23A412(3)3A45123t1(4)A45(5)45B123t14t2(6)5B123t14t25t3(7)搜索成功,解树:1,2,3,4,5,t1,t2,t3扩展节点Open列表Closed列表与或图搜索第四章-23内容4.0与或树表示4.1与/或树的一般搜索4.2与/或树的广度优先搜索4.3与/或树的深度优先搜索4.4与／或树的启发式搜索4.5博弈树的启发式搜索与或图搜索第四章-244.3与/或树的深度优先搜索与/或树的深度优先搜索算法：（1）把初始节点S0放入Open表中；（2）把Open表的第一个节点取出放入Closed表，并记该节点为n；（3）如果节点n的深度等于dm，则转第（5）步的第①点；（4）如果节点n可扩展，则做下列工作：①扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针；②考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解节点进行标记。如果初始节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点；③转第（2）步。与或图搜索第四章-254.3与/或树的深度优先搜索（5）如果节点n不可扩展，则做下列工作：①标记节点n为不可解节点；②应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定为不可解节点，则从Open表中删去具有不可解先辈的节点；③转第（2）步。与或图搜索第四章-264.3与/或树的深度优先搜索【例4.3】对上例所给出的与／或树，若按有解深度优先搜索，且给定dm=4。则其扩展节点的顺序为：1，3，5，2，4其解树与上例相同。123A4t1t3CBt25与或图搜索第四章-27内容4.0与或树表示4.1与/或树的一般搜索4.2与/或树的广度优先搜索4.3与/或树的深度优先搜索4.4与／或树的启发式搜索4.5博弈树的启发式搜索与或图搜索第四章-284.4与／或树的启发式搜索与／或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树（希望树）。4.4.1解树的代价与希望树最优解树指代价最小的那棵解树。与或图搜索第四章-294.4与／或树的启发式搜索如何计算解树的代价？目标目标初始节点abc与或图搜索第四章-304.4与／或树的启发式搜索解树的代价可按如下规则计算：（1）若n为终止节点：（2）若n为或节点，且子节点为n1，n2，…，nk，（3）若n为与节点，且子节点为n1，n2，…，nk，和代价法：最大代价法：（4）若n是端节点，但又不是终止节点：（5）根节点的代价即为解树的代价。【例4.4】计算解树的代价。①左边的解树和代价：最大代价：②右边的解树和代价：最大代价：S0ABt1Ct3Et2Dt4F22463521终止节点：t1,t2,t3和t4端节点：E和F与或图搜索第四章-324.4与／或树的启发式搜索希望树为了找到最优解树，搜索过程的任何时刻都应该选择那些最有希望成为最优解树一部分的节点进行扩展。由这些节点及其父节点所构成的子树，称为希望树。【定义】希望解树T（1）初始节点S0在希望树T中；（2）如果n是具有子节点n1，n2，…，nk的或节点，则n的某个子节点ni在希望树T中的充分必要条件是:h（ni）=min{c（n，ni）＋h（ni）}1≤i≤k（3）如果n是与节点，则n的全部子节点都在希望树T中。…...nn1nk与或图搜索第四章-334.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）步。与或图搜索第四章-344.4与／或树的启发式搜索（5）如果节点n不是终止节点，但可扩展，则做下列工作：①扩展节点n，生成n的所有子节点；②把这些子节点都放入Open表中，并为每一个子节点设置指向父节点n的指针；③计算这些子节点及其先辈节点的h值；④转第（2）步。（6）如果节点n不是终止节点，且不可扩展，则做下列工作：①标记节点n为不可解节点；②在T上应用不可解标记过程，对n的先辈节点中的所有不可解节点进行标记；③如果初始节点S。能够被标记为不可解节点，则问题无解，失败退出；④否则，从Open表中删去具有不可解先辈的所有节点；⑤转第（2）步。与或图搜索第四章-364.4与／或树的启发式搜索【例4.5】假设搜索过程每次扩展节点时都同扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。887S0ADBCEF3332希望树T:扩展节点S0后与或图搜索第四章-374.4与／或树的启发式搜索S0ADBCEF83323222776119S0ADBCEF83323222776119GKHILJ002226与或图搜索第四章-384.4与／或树的启发式搜索S0DEF83323222776119IGKHLJ002226MNP003229ABC9与或图搜索第四章-39内容4.0与或