《搜索与或图搜索》ppt课件

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 博弈树的启发式搜索博弈树的启发式搜索4.0 4.0 与或树表示与或树表示n不同于形状空间方法的另外一种方式化方法。n根本思想：n当一个问题比较复杂时，直接进展求解往往比较困难。n可经过归约分解或变换，将它转化为一系列较简单的问题。n经过对这些较简单问题的求解来实现对原问题的求解。4.

2、0 4.0 与或树表示与或树表示n【例4.0】n设有四边形ABCD和ABCD，证明它们全等。4.0 4.0 与或树表示与或树表示n分析：原问题分解为两个子问题：4.0 4.0 与或树表示与或树表示4.0 4.0 与或树表示与或树表示n4.0.1 分解n问题P可以归约为一组子问题P1,P2,Pn。n只需当一切子问题Pi(i1，2，n)都有解时,原问题P才有解。n即分解所得到的子问题的“与和原问题P等价。n与树nK-衔接符P1P2P3P.K个4.0 4.0 与或树表示与或树表示n4.0.2 等价变换n问题P可以归约为一组子问题P1,P2,Pn。n这些子问题Pi中只需有一个有解那么原问题P就有解，只

3、需当一切子问题Pi都无解时原问题P才无解。n即变换所得到的子问题的“或与原问题P等价。n或树n把一个原问题变换为假设干个子问题可用一个“或树来表示。P1P2P3P4.0 4.0 与或树表示与或树表示n4.0.3 与或树n假设一个问题既需求经过分解，又需求经过变换才干得到其本原问题，那么其归约过程可用一个“与/或树来表示。PP1P2P3P31P32P33P11P12原始问题本原问题终止节点端节点没有子节点的节点，即叶子节点；终止节点可解节点，即本原问题。t4.0 4.0 与或树表示与或树表示Ptttn4.0.4 解树n由可解节点构成，并且由这些可解节点可以推出初始节点(它对应着原始问题)为可解节

4、点的子树。n在解树中一定包含初始节点。4.0 4.0 与或树表示与或树表示n【例4.1】三阶梵塔问题。n解：n用三元组表示问题在任一时辰的形状：(i,j,k)ni：代表金片C所在的钢针号；nj: 代表金片B所在的钢针号；nk; 代表金片A所在的钢针号；1 2 31 2 31 2 31 2 3ABC 1 2 3(1, 1, 1)1 2 3(1, 2, 2)1 2 3(3, 2, 2)1 2 3(3, 3, 3)ABC(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

5、)(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)(3,2,1) (3,3,1)(3,3,1) (3,3,3)(3,3,1) (3,3,3)三阶梵塔问题的与或树三阶梵塔问题的与或树n在该与/或树中，有7个终止节点，它们分别对应着7个本原问题。假设把这些本原问题从左至右陈列起来，即得到了原始问题的解：4.0 4.0

6、 与或树表示与或树表示目的目的目的目的初始节点初始节点sabc内容内容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 博弈树的启发式搜索博弈树的启发式搜索4.1 4.1 与与/ /或树的普通搜索或树的普通搜索n与/或树的搜索过程实践上是一个不断寻觅解树的过程。其普通搜索过程如下：n1把原始问题作为初始节点S0，并把它作为当前节n 点； n2

7、运用分解或等价变换操作对当前节点进展扩展； n3为每个子节点设置指向父节点的指针； n4选择适宜的子节点作为当前节点，反复执行第n 2步和第3步，在此期间需求多次调用可解n 标志过程或不可解标志过程，直到初始节点被标n 记为可解节点或不可解节点为止。4.1 4.1 与与/ /或树的普通搜索或树的普通搜索n在与/或树中，除端节点和终止节点外，一个节点的可解性完全是由其子节点来决议的。n对与节点，只需其一切子节点都为可解时它才为可解，只需有一个子节点不可解它就是不可解的；n对或节点，只需有一个子节点可解它就是可解的，仅当一切子节点都是不可解时它才为不可解。n可解标志过程n由可解子节点来确定其父节点

8、、祖父节点为可解节点的过程。n不可解标志过程n由不可解子节点来确定其父节点、祖父节点为不可解节点的过程。4.1 4.1 与与/ /或树的普通搜索或树的普通搜索n搜索解树的过程中，节点删除战略：n 假设搜索过程确定某个节点为可解节点，那么其不n 可解的后裔节点就可从搜索树中删去；n 假设搜索过程能确定某个节点为不可解节点，那么n 其后裔节点也可从搜索树中删去。内容内容n 4.0 4.0 与或树表示与或树表示n 4.1 4.1 与与/ /或树的普通搜索或树的普通搜索n 4.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n 4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n

9、 4.4 4.4 与或树的启发式搜索与或树的启发式搜索n 4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索4.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n与/或树的广度优先搜索算法：n1把初始节点S0 放人Open表中； n2把Open表的第一个节点取出放入Closed表，并记该节点n 为n； n3假设节点n可扩展，那么做以下任务： n扩展节点n，将其子节点放入Open表的尾部，并为每一个子 n 节点设置指向父节点的指针； n调查这些子节点中能否有终止节点。假设有，那么标志这些终n 止节点为可解节点，并用可解标志过程对其父节点及先辈 n 节点中的可解节点进展标志。n假设初始

10、解节点S0可以被标志为可解节点，就得到了解树，搜索胜利，退出搜索过程；n假设不能确定S0为可解节点，那么从Open表中删去具有可解先辈的节点； n转第2步。4.2 4.2 与与/ /或树的广度优先搜索或树的广度优先搜索n搜索算法续：n4假设节点n不可扩展，那么做以下任务： n 标志节点n为不可解节点； n 运用不可解标志过程对节点n的先辈中不可解的节点进展标志。n假设初始解节点S0也被标志为不可解节点，那么搜索失败，阐明原始问题无解，退出搜索过程；n假设不能确定S0为不可解节点，那么从Open表中删去具有不可解先辈的节点； n转第2步。【例【例4.2】 t1、t2、t3的节点是终止节点，的节点

11、是终止节点，A 、 B 、 C为不可解的端节点为不可解的端节点123A4t1t3CBt25(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列表列表内容内容n 4.0 4.0 与或树表示与或树表示n 4.1 4.1 与与/ /或树的普通搜索或树的普通搜索n 4.2 4.2 与与/ /或树的广度优先搜索或

12、树的广度优先搜索n 4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n 4.4 4.4 与或树的启发式搜索与或树的启发式搜索n 4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n与/或树的深度优先搜索算法：n1把初始节点S0放入 Open表中； n2把Open表的第一个节点取出放入Closed表，并记该节点为n n； n3假设节点n的深度等于dm，那么转第5步的第n 点； n4假设节点n可扩展，那么做以下任务：n扩展节点 n，将其子节点放入 Open表的首部，并为每一n 个子节点设置指向父节点的指针； n调查这些子

13、节点中能否有终止节点。假设有，那么标志这些n 终止节点为可解节点，并用可解标志过程对其父节点及n 先辈节点中的可解节点进展标志。假设初始节点S0可以n 被标志为可解节点，就得到了解树，搜索胜利，退出搜n 索过程；假设不能确定S0为可解节点，那么从Open表中删n 去具有可解先辈的节点； n转第2步。4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n5假设节点n不可扩展，那么做以下任务：n标志节点n为不可解节点； n运用不可解标志过程对节点n的先辈中不可解的节点进展标志。假设初始节点S0也被标志为不可解节点，那么搜索失败，阐明原始问题无解，退出搜索过程；假设不能确定为不可解节点，那

14、么从Open表中删去具有不可解先辈的节点； n转第2步。4.3 4.3 与与/ /或树的深度优先搜索或树的深度优先搜索n【例4.3】n对上例所给出的与或树，假设按有解深度优先搜索，且给定dm=4。n那么其扩展节点的顺序为：1，3，5，2，4n其解树与上例一样。123A4t1t3CBt25内容内容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

15、 博弈树的启发式搜索博弈树的启发式搜索4.4 4.4 与或树的启发式搜索与或树的启发式搜索 与或树的启发式搜索过程是一种利用搜索过程所得到的启发性信息寻觅最优解树的过程。对搜索的每一步，算法都试图找到一个最有希望成为最优解树的子树希望树。n4.4.1 解树的代价与希望树n最优解树 n指代价最小的那棵解树。4.4 4.4 与或树的启发式搜索与或树的启发式搜索n如何计算解树的代价？目的目的目的目的初始节点初始节点abc4.4 4.4 与或树的启发式搜索与或树的启发式搜索n解树的代价可按如下规那么计算：n1假设n为终止节点：n n2假设n为或节点，且子节点为n1，n2，nk， n n3假设n为与节点

16、，且子节点为n1，n2，nk， n和代价法：n最大代价法：n4假设n是端节点，但又不是终止节点：n5根节点的代价即为解树的代价。n【例4.4】计算解树的代价。n左边的解树n和代价：n最大代价：n右边的解树n和代价：n最大代价：S0ABt1Ct3Et2Dt4F22463521终止节点：终止节点：t1, t2, t3 和和 t4 端节点：端节点：E 和和 F 4.4 4.4 与或树的启发式搜索与或树的启发式搜索n希望树n为了找到最优解树，搜索过程的任何时辰都应该选择那些最有希望成为最优解树一部分的节点进展扩展。由这些节点及其父节点所构成的子树，称为希望树。n【定义】希望解树Tn1初始节点S0在希望

17、树T中； n2假设n是具有子节点n1，n2，nk的或节点，那么n的n 某个子节点ni在希望树T中的充分必要条件是: n hni= min cn，ni hni 1ik n3假设n是与节点，那么n的全部子节点都在希望树T中。.nn1nk4.4 4.4 与或树的启发式搜索与或树的启发式搜索n4.4.2 与或树的启发式搜索过程n与或树的启发式搜索过程是不断地选择、修正希望树的过程，其搜索过程如下：n1把初始节点S0放入Open表中，计算hS0； n2计算希望树T； n3依次在Open表中取出T的端节点放入Closed表，并n 记该节点为n； n4假设节点n为终止节点，那么做以下任务：n标志节点n为可解

18、节点； n在T上运用可解标志过程，对n的先辈节点中的一切可解节点进展标志； n假设初始节点S0可以被标志为可解节点，那么T就是最优解树，胜利退出； n否那么，从Open表中删去具有可解先辈的一切节点； n转第2步。4.4 4.4 与或树的启发式搜索与或树的启发式搜索n5假设节点n不是终止节点，但可扩展，那么做以下任务：n 扩展节点n，生成n的一切子节点； n 把这些子节点都放入 Open表中，并为每一个子节点设置指向父节点 n的指针； n 计算这些子节点及其先辈节点的h值； n 转第2步。n6假设节点n不是终止节点，且不可扩展，那么做以下任务： n 标志节点n为不可解节点； n 在T上运用不可

19、解标志过程，对n的先辈节点中的一切不可解节点进展标志； n 假设初始节点S。可以被标志为不可解节点，那么问题无解，失败退出； n 否那么，从Open表中删去具有不可解先辈的一切节点；n 转第2步。4.4 4.4 与或树的启发式搜索与或树的启发式搜索n【例4.5】假设搜索过程每次扩展节点时都同扩展两层，且按一层或节点、一层与节点的间隔方式进展扩展。887S0ADBCEF3332希望树希望树T : 扩展节点扩展节点 S0 后后4.4 4.4 与或树的启发式搜索与或树的启发式搜索S0ADBCEF8332 3222776119S0ADBCEF8332 3222776119GKHILJ0022264.4

20、 4.4 与或树的启发式搜索与或树的启发式搜索S0DEF8332 3222776119IGKHLJ002226MNP003229ABC内容内容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 博弈树的启发式搜索博弈树的启发式搜索4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索n4.5.1 概述n机遇性博弈n存在不可预测性的博弈。n双人完备

21、信息博弈n两位选手对垒，轮番走步，每一方不仅知道对方曾经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。n任何一方走步时，都是选择对本人最为有利，而对另一方最为不利的行动方案。n假设博弈的一方为MAX，另一方为MIN。n在博弃过程的每一步，可供MAX和MIN选择的行动方案都能够有多种。4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索MINMAXMINMAXMINMAX分分钱钱币币问问题题对方先走我方必胜4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索n博弈树n把双人完备信息博弈过程用图表示出来，就可得到一棵与/或树。n下一步该MAX走步的节点称为M

22、AX节点。n下一步该MIN走步的节点称为MIN节点。n博弈树具有如下特点：n博弈的初始形状是初始节点；n博弈树中的“或节点和“与节点是逐层交替出现n 的；n整个博弈过程一直站在某一方的立场上，一切能使自n 己一方获胜的结局都是本原问题，相应的节点是可解n 节点；一切使对方获胜的结局都是不可解节点。4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索n假定站在MAX方的立场：n可供本人选择的行动方案之间是“或的关系。n缘由是自动权掌握在MAX手里，选择哪个方案完全是由本人决议的。n可供MIN选择的行动方案之间那么是“与的关系。n缘由是自动权掌握在MIN的手里，任何一个方案都有能够被MIN选中。n

23、MAX必需防止那种对本人最为不利的情况的发生。4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索n4.5.2 针对可穷举搜索情况极大极小过程4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索n4.5.3 固定深度的极大极小过程n对于某些情况，要生成整个搜索树是不能够的。一种可行的方法是用当前正在调查的节点生成一棵部分博弈树n-层预判n-ply look-ahead。n1利用估价函数f(n)对叶节点进展静态评价：n假设该节点对MAX有利，其估价函数取正值；n假设该节点对MIN有利，其估价函数取负值；n假设该节点对双方有利，其估价函数取接近于0的值。n2计算非叶节点的值，必需从叶节点向上倒退n

24、MAX节点：其倒退值应该取其后继节点估值的最大值。nMIN节点：其倒推值应该取其后继节点估值的最小值。n3反复步骤2，直至求出初始节点的倒推值。4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索对假想形状空间的对假想形状空间的4层预判极小极大过程，叶子节点显示了启发值，内部形状显示了向上传播的值层预判极小极大过程，叶子节点显示了启发值，内部形状显示了向上传播的值4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索n【例4.6】九宫游戏。n设MAX方的棋子用标志，MIN方的棋子用标志，并规定MAX方先走步。n解：n为了对叶节点进展静态估值，规定估价函数eP如下：n假设 P是 MAX的必胜局，

25、那么 eP= + n假设 P是 MIN的必胜局， 那么 eP= - n假设P对MAX、MIN都是胜负未定局，那么e(P)= e(+P)e(-P)ne+P：棋局 P上有能够使成三子一线的数目。ne-P：棋局 P上有能够使成三子一线的数目。n 一字棋棋盘一字棋棋盘4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索X有有6条能够的胜利道路条能够的胜利道路O有有5条能够的胜利道路条能够的胜利道路PPPX有有4条能够的胜利道路条能够的胜利道路O有有6条能够的胜利道路条能够的胜利道路X有有5条能够的胜利道路条能够的胜利道路O有有4条能够的胜利道路条能够的胜利道路运用到九宫游戏开局挪动的运用到九宫游戏开局挪动的2层预判极小极大过程层预判极小极大过程两种能够的两种能够的MAX第二步挪动第二步挪动对对X在接近结局的挪动运用极小极大过程在接近结局的挪动运用极小极大过程4.5 4.5 博弈树的启发式搜索博弈树的启发式搜索n【例4.7】 0-33-3-3-21-36-30316011极大极小ab0 5 -33 3 -30 2 2 -3 0 -23 0 4 1-3-368 94.5 4.5 博弈树的启发式搜索博弈树的启发式搜索n4.5.4 -剪枝n极小极大过程性能分析：n极小极大过程需求对搜索空间进展两遍分析，第一遍是向下降到预判层并在那里运用启发评价，第