《《搜索与或图搜索》PPT课件》由会员分享，可在线阅读，更多相关《《搜索与或图搜索》PPT课件（59页珍藏版）》请在金锄头文库上搜索。
1、 与或图搜索与或图搜索1内容内容n 4.0 4.0 与或树表示与或树表示n 4.1 4.1 与与/ /或树的一般搜索或树的一般搜索n 4.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n 4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n 4.4 4.4 与或树的启发式搜索与或树的启发式搜索n 4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索与或图搜索与或图搜索24.0 4.0 与或树表示与或树表示n不同于状态空间方法的另外一种形式化方法。n基本思想：n当一个问题比较复杂时，直接进行求解往往比较困难。n可通过归约（分解或变换），将它转化为一系列较简单的问题。n通过
2、对这些较简单问题的求解来实现对原问题的求解。与或图搜索与或图搜索34.0 4.0 与或树表示与或树表示n【例】n设有四边形ABCD和ABCD，证明它们全等。与或图搜索与或图搜索44.0 4.0 与或树表示与或树表示n分析：原问题分解为两个子问题：与或图搜索与或图搜索54.0 4.0 与或树表示与或树表示与或图搜索与或图搜索64.0 4.0 与或树表示与或树表示n4.0.1 分解n问题P可以归约为一组子问题P1,P2,Pn。n只有当所有子问题Pi(i1，2，n)都有解时,原问题P才有解。n即分解所得到的子问题的“与”和原问题P等价。n与树nK-连接符P1P2P3P.K个与或图搜索与或图搜索74.
3、0 4.0 与或树表示与或树表示n4.0.2 等价变换n问题P可以归约为一组子问题P1,P2,Pn。n这些子问题Pi中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解。n即变换所得到的子问题的“或”与原问题P等价。n或树n把一个原问题变换为若干个子问题可用一个“或树”来表示。P1P2P3P与或图搜索与或图搜索84.0 4.0 与或树表示与或树表示n4.0.3 与或树n如果一个问题既需要通过分解，又需要通过变换才能得到其本原问题，则其归约过程可用一个“与/或树”来表示。PP1P2P3P31P32P33P11P12原始问题本原问题（终止节点）端节点没有子节点的节点，即叶子
4、节点；终止节点可解节点，即本原问题。t与或图搜索与或图搜索94.0 4.0 与或树表示与或树表示Ptttn4.0.4 解树n由可解节点构成，并且由这些可解节点可以推出初始节点(它对应着原始问题)为可解节点的子树。n在解树中一定包含初始节点。与或图搜索与或图搜索104.0 4.0 与或树表示与或树表示n【例】三阶梵塔问题。n解：n用三元组表示问题在任一时刻的状态：(i,j,k)ni：代表金片C所在的钢针号；nj: 代表金片B所在的钢针号；nk; 代表金片A所在的钢针号；1 2 31 2 31 2 31 2 3ABC与或图搜索与或图搜索11 1 2 3(1, 1, 1)1 2 3(1, 2, 2)
5、1 2 3(3, 2, 2)1 2 3(3, 3, 3)ABC与或图搜索与或图搜索12(1,1,1)-(3,3,3) (1,1,1)-(3,3,3) (1,1,1)-(1,2,2)(1,1,1)-(1,2,2)(1,2,2)-(3,2,2)(1,2,2)-(3,2,2)(3,2,2)-(3,3,3)(3,2,2)-(3,3,3)(1,1,1)-(1,1,3)(1,1,1)-(1,1,3)(1,1,3)-(1,2,3)(1,1,3)-(1,2,3)(1,2,3) (1,2,2)(1,2,3) (1,2,2)(3,2,2)-(3,2,1)(3,2,2)-(3,2,1) (3,2,1) (3,3,1
6、)(3,2,1) (3,3,1)(3,3,1) (3,3,3)(3,3,1) (3,3,3)三阶梵塔问题的与或树三阶梵塔问题的与或树n在该与/或树中，有7个终止节点，它们分别对应着7个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：与或图搜索与或图搜索134.0 4.0 与或树表示与或树表示目标目标目标目标初始节点初始节点sabc与或图搜索与或图搜索14内容内容n 4.0 4.0 与或树表示与或树表示n 4.1 4.1 与与/ /或树的一般搜索或树的一般搜索n 4.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n 4.3 4.3 与与/ /或树的深度优先搜索或树
7、的深度优先搜索n 4.4 4.4 与或树的启发式搜索与或树的启发式搜索n 4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索与或图搜索与或图搜索154.1 4.1 与与/ /或树的一般搜索或树的一般搜索n与/或树的搜索过程实际上是一个不断寻找解树的过程。其一般搜索过程如下：n（1）把原始问题作为初始节点S0，并把它作为当前节 点； n（2）应用分解或等价变换操作对当前节点进行扩展； n（3）为每个子节点设置指向父节点的指针； n（4）选择合适的子节点作为当前节点，反复执行第 （2）步和第（3）步，在此期间需要多次调用可解 标记过程或不可解标记过程，直到初始节点被标 记为可解节点或不可解节点为
8、止。与或图搜索与或图搜索164.1 4.1 与与/ /或树的一般搜索或树的一般搜索n在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决定的。n对与节点，只有其所有子节点都为可解时它才为可解，只要有一个子节点不可解它就是不可解的；n对或节点，只要有一个子节点可解它就是可解的，仅当所有子节点都是不可解时它才为不可解。n可解标记过程n由可解子节点来确定其父节点、祖父节点为可解节点的过程。n不可解标记过程n由不可解子节点来确定其父节点、祖父节点为不可解节点的过程。与或图搜索与或图搜索174.1 4.1 与与/ /或树的一般搜索或树的一般搜索n搜索解树的过程中，节点删除策略：n 如
9、果搜索过程确定某个节点为可解节点，则其不 可解的后裔节点就可从搜索树中删去；n 如果搜索过程能确定某个节点为不可解节点，则 其后裔节点也可从搜索树中删去。与或图搜索与或图搜索18内容内容n 4.0 4.0 与或树表示与或树表示n 4.1 4.1 与与/ /或树的一般搜索或树的一般搜索n 4.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n 4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n 4.4 4.4 与或树的启发式搜索与或树的启发式搜索n 4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索与或图搜索与或图搜索194.2 4.2 与与/ /或树的广度优先搜索或树
10、的广度优先搜索n与/或树的广度优先搜索算法：n（1）把初始节点S0 放人Open表中； n（2）把Open表的第一个节点取出放入Closed表，并记该节点 为n； n（3）如果节点n可扩展，则做下列工作： n扩展节点n，将其子节点放入Open表的尾部，并为每一个子 节点设置指向父节点的指针； n考察这些子节点中是否有终止节点。若有，则标记这些终 止节点为可解节点，并用可解标记过程对其父节点及先辈 节点中的可解节点进行标记。n如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；n如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点； n转第（2）步。与或图
11、搜索与或图搜索204.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n搜索算法（续）：n（4）如果节点n不可扩展，则做下列工作： n 标记节点n为不可解节点； n 应用不可解标记过程对节点n的先辈中不可解的节点进行标记。n如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；n如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点； n转第（2）步。与或图搜索与或图搜索21【例例】 t1、t2、t3的节点是终止节点，的节点是终止节点，A 、 B 、 C为不可解的端节点为不可解的端节点123A4t1t3CBt25(1) 1 2 3 1(2
12、) 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列表列表与或图搜索与或图搜索22内容内容n 4.0 4.0 与或树表示与或树表示n 4.1 4.1 与与/ /或树的一般搜索或树的一般搜索n 4.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n 4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n 4.4
13、 4.4 与或树的启发式搜索与或树的启发式搜索n 4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索与或图搜索与或图搜索234.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n与/或树的深度优先搜索算法：n（1）把初始节点S0放入 Open表中； n（2）把Open表的第一个节点取出放入Closed表，并记该节点为 n； n（3）如果节点n的深度等于dm，则转第（5）步的第 点； n（4）如果节点n可扩展，则做下列工作：n扩展节点 n，将其子节点放入 Open表的首部，并为每一 个子节点设置指向父节点的指针； n考察这些子节点中是否有终止节点。若有，则标记这些 终止节点为可解节点
14、，并用可解标记过程对其父节点及 先辈节点中的可解节点进行标记。如果初始节点S0能够 被标记为可解节点，就得到了解树，搜索成功，退出搜 索过程；如果不能确定S0为可解节点，则从Open表中删 去具有可解先辈的节点； n转第（2）步。与或图搜索与或图搜索244.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n（5）如果节点n不可扩展，则做下列工作：n标记节点n为不可解节点； n应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定为不可解节点，则从Open表中删去具有不可解先辈的节点； n转
15、第（2）步。与或图搜索与或图搜索254.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n【例】n对上例所给出的与或树，若按有解深度优先搜索，且给定dm=4。n则其扩展节点的顺序为：1，3，5，2，4n其解树与上例相同。123A4t1t3CBt25与或图搜索与或图搜索26内容内容n 4.0 4.0 与或树表示与或树表示n 4.1 4.1 与与/ /或树的一般搜索或树的一般搜索n 4.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n 4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n 4.4 4.4 与或树的启发式搜索与或树的启发式搜索n 4.5 4.5 博弈
16、树的启发式搜索博弈树的启发式搜索与或图搜索与或图搜索274.4 4.4 与或树的启发式搜索与或树的启发式搜索 与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树（希望树）。n4.4.1 解树的代价与希望树n最优解树 n指代价最小的那棵解树。与或图搜索与或图搜索284.4 4.4 与或树的启发式搜索与或树的启发式搜索n如何计算解树的代价？目标目标目标目标初始节点初始节点abc与或图搜索与或图搜索294.4 4.4 与或树的启发式搜索与或树的启发式搜索n解树的代价可按如下规则计算：n（1）若n为终止节点： n（2）若n为或节点，且子节点为n1，n2，nk， n（3）若n为与节点，且子节点为n1，n2，nk， n和代价法：n最大代价法：n（4）若n是端节点，但又不是终止节点：n（5）根节点的代价即为解树的代价。与或图搜索与或图搜索30n【例】计算解树的代价。n左边的解树n和代价：n最大代价：n右边的解树n和代价：n最大代价：S0ABt1Ct3Et2Dt4F22463521终止节点：终止节点：t1, t2,
