(搜索推理技术与或树搜索)课件.ppt

1、人人 工工 智智 能能Artificial Intelligence(AI)许建华许建华南京师范大学计算机科学与技术学院南京师范大学计算机科学与技术学院2010年秋季年秋季第第3章章 搜索原理搜索原理 3.1 图的搜索策略图的搜索策略3.2 盲目搜索盲目搜索3.3 启发式搜索启发式搜索3.4 与或树搜索（与或树搜索（补充补充）3.5 博弈树搜索（博弈树搜索（补充补充）3.6 消解原理消解原理3.4 与或树搜索（补充）与或树搜索（补充）问题归约法问题归约法原始问题原始问题中间问题中间问题 本原问题集本原问题集 操作符操作符与或图与或图起始节点起始节点中间节点中间节点终叶节点终叶节点生成生成“与与

2、”、“或或”后继后继节点的有向弧节点的有向弧 1、终叶节点终叶节点是可解的（因为它们与本原问题相关是可解的（因为它们与本原问题相关联的）联的）2、如果某一个非终叶节点含有、如果某一个非终叶节点含有“或或”后继节点，后继节点，那么，只要有一个后继节点是可解的，这一个非终那么，只要有一个后继节点是可解的，这一个非终叶节点就是可解的叶节点就是可解的3、如果某一个非终叶节点含有、如果某一个非终叶节点含有“与与”后继节点，后继节点，那么，只要所有后继节点是可解的，这一个非终叶那么，只要所有后继节点是可解的，这一个非终叶节点才是可解的节点才是可解的可解节点可解节点的定义是（递归地）的定义是（递归地）：1、

3、没有后裔的非终叶节点是不可解节点、没有后裔的非终叶节点是不可解节点2、如果某一个非终叶节点含有、如果某一个非终叶节点含有“或或”后继节点，后继节点，那么，只要当所有的后继节点都不可解时，这一那么，只要当所有的后继节点都不可解时，这一个非终叶节点才是不可解的个非终叶节点才是不可解的3、如果某一个非终叶节点含有、如果某一个非终叶节点含有“与与”后继节点，后继节点，那么，只要有一个后继节点是不可解的，这一个那么，只要有一个后继节点是不可解的，这一个非终叶节点就是不可解的非终叶节点就是不可解的不可解节点不可解节点的定义（递归地）是的定义（递归地）是：根据可解与不可解节点的递归定义，用递归的方根据可解与

4、不可解节点的递归定义，用递归的方式作用于某一个与或图，以标出所有的可解节点式作用于某一个与或图，以标出所有的可解节点与不可解节点与不可解节点可解标志过程可解标志过程与与不可解标志过程不可解标志过程:若初始节点被标志为可解节点，算法成若初始节点被标志为可解节点，算法成功结束（功结束（有解有解）若起始节点被标志为不可解节点，则搜若起始节点被标志为不可解节点，则搜索失败结束（索失败结束（无解无解）算法结束的条件算法结束的条件：与或图的解图与或图的解图：由最少的可解节点所构成的子图，这些节由最少的可解节点所构成的子图，这些节点能够使问题的起始节点是可解的点能够使问题的起始节点是可解的与或树与或树：除了

5、起始节点，每一个节点只有一：除了起始节点，每一个节点只有一个父节点个父节点与或图与或图：除了起始节点，每一个节点允许有除了起始节点，每一个节点允许有多个父节点多个父节点两者的关系两者的关系：与或树是与或图的特例：与或树是与或图的特例约定约定：当一个节点生成后继节点时，它们是搜：当一个节点生成后继节点时，它们是搜索过程中没有产生过的节点，并且以后也不会索过程中没有产生过的节点，并且以后也不会再生成它们。再生成它们。（每一个节点只允许生成一次每一个节点只允许生成一次）3.4.1 宽度优先搜索宽度优先搜索 两个基本符号两个基本符号：OPEN表表：存放待扩展的节点，此时是队列：存放待扩展的节点，此时是

6、队列CLOSED表表：存放已扩展的节点：存放已扩展的节点1、起始节点、起始节点 S 送送 OPEN 表表2、若、若 S 为叶节点，则成功结束，否则，继续为叶节点，则成功结束，否则，继续3、取出、取出 OPEN 表的第一个节点（记作表的第一个节点（记作 n），并送），并送 到到CLOSED 表表与或树宽度优先搜索算法与或树宽度优先搜索算法：4、扩展节点、扩展节点 n，生成其全部后继节点，送，生成其全部后继节点，送OPEN表末端，并设置指向表末端，并设置指向 n 的指针的指针说明说明：此时可能出现三种情况：此时可能出现三种情况节点节点 n 无后继节点无后继节点节点节点 n 有后继节点、并有叶节点有

7、后继节点、并有叶节点节点节点 n 有后继节点、但无叶节点有后继节点、但无叶节点5、若、若 n 无后继节点，标志无后继节点，标志 n 为不可解，并转为不可解，并转9（10、11）；若后继节点中有叶节点，则标志）；若后继节点中有叶节点，则标志这些叶节点为可解节点，并继续（这些叶节点为可解节点，并继续（6、7、8）；）；否则转否则转36、实行可解标志过程、实行可解标志过程7、若起始节点、若起始节点S标志为可解，则找到解而结束，标志为可解，则找到解而结束，否则继续否则继续8、从、从OPEN表中删去含有可解先辈节点的节点，表中删去含有可解先辈节点的节点，并转并转39、实行不可解标志过程、实行不可解标志过

8、程10、若起始节点、若起始节点S标志为不可解，则失败而结束，标志为不可解，则失败而结束，否则继续否则继续11、从、从OPEN表中删去含有不可解先辈节点的节点表中删去含有不可解先辈节点的节点12、转、转3例例说明说明：先扩展出来的节点画在左边：先扩展出来的节点画在左边算法的运行过程算法的运行过程初始化初始化：节点节点 1 送送OPEN表，且不为叶节点表，且不为叶节点OPEN=1 CLOSED=3、从、从OPEN表中取出节点表中取出节点1，并送到，并送到CLOSED表表4、扩展节点、扩展节点1，生成后继节点，生成后继节点2、3，并送到，并送到OPEN表的末端表的末端5、无叶节点，转到、无叶节点，转

9、到3步步OPEN=2，3 CLOSED=1 第一大循环第一大循环（算法的算法的3、4、5步步）：3、从、从OPEN表中取出节点表中取出节点2，并送到，并送到CLOSED表表4、扩展节点、扩展节点2，生成后继节点，生成后继节点4、5，并送到，并送到OPEN表的末端表的末端5、无叶节点，转到、无叶节点，转到3步步OPEN=3,4,5 CLOSED=1,2 第二大循环第二大循环（3、4、5步）：步）：3、从、从OPEN表中取出节点表中取出节点3，并送到，并送到CLOSED表表4、扩展节点、扩展节点3，生成后继节点，生成后继节点6、7，并送到，并送到OPEN表的末端表的末端5、无叶节点，转到、无叶节点

10、，转到3步步OPEN=4,5,6,7 CLOSED=1,2,3 第三大循环第三大循环（3、4、5步）：步）：3、从、从OPEN表中取出节点表中取出节点4，并送到，并送到CLOSED表表4、扩展节点、扩展节点4，生成后继节点，生成后继节点8、9，并送到，并送到OPEN表的末端表的末端5、无叶节点，转到、无叶节点，转到3步步OPEN=5,6,7,8,9 CLOSED=1,2,3,4 第四大循环第四大循环（3、4、5步）：步）：3、从、从OPEN表中取出节点表中取出节点5，并送到，并送到CLOSED表表4、扩展节点、扩展节点5，生成后继节点，生成后继节点B、C，并送到，并送到OPEN表的末端表的末端

11、5、无叶节点，转到、无叶节点，转到3步步OPEN=6,7,8,9,B,C CLOSED=1,2,3,4,5 第五大循环第五大循环（3、4、5步）：步）：3、从、从OPEN表中取出节点表中取出节点6，并送到，并送到CLOSED表表4、扩展节点、扩展节点6，生成后继节点，生成后继节点t1、10，并送到，并送到OPEN表的末端表的末端5、有叶节点、有叶节点6、实现可解过程（无法判断节点、实现可解过程（无法判断节点6是否可解）是否可解）7、无法判断起始节点是否可解、无法判断起始节点是否可解8、OPEN表中无节点可以删除（转到表中无节点可以删除（转到3）第六大循环第六大循环（3、4、5、6、7、8步）：

12、步）：OPEN=7,8,9,B,C,t1,10 CLOSED=1,2,3,4,5,6 3、从、从OPEN表中取出节点表中取出节点7，并送到，并送到CLOSED表表4、扩展节点、扩展节点7，生成后继节点，生成后继节点11、12，并送到，并送到OPEN表的末端表的末端5、无叶节点，转到、无叶节点，转到3步步OPEN=8,9,B,C,t1,10,11,12 CLOSED=1,2,3,4,5,6,7 第七大循环第七大循环（3、4、5步）：步）：3、从、从OPEN表中取出节点表中取出节点8，并送到，并送到CLOSED表表4、扩展节点、扩展节点8，生成后继节点，生成后继节点A，并送到，并送到OPEN表表的

13、末端的末端5、无叶节点，转到、无叶节点，转到3步步OPEN=9,B,C,t1,10,11,12,ACLOSED=1,2,3,4,5,6,7,8第八大循环第八大循环（3、4、5步）：步）：3、从、从OPEN表中取出节点表中取出节点9，并送到，并送到CLOSED表表4、扩展节点、扩展节点9，生成后继节点，生成后继节点 t2、t3，并送到，并送到OPEN表的末端表的末端5、有叶节点、有叶节点6、实现可解标志过程（可以判断节点、实现可解标志过程（可以判断节点9、4、2可解）可解）7、无判断起始节点、无判断起始节点1可解可解8、从、从OPEN中删除含有可解先辈节点的节点中删除含有可解先辈节点的节点第九大

14、循环第九大循环（3、4、5、6、7、8步）：步）：OPEN=B,C,t1,10,11,12,A,t2,t3 CLOSED=1,2,3,4,5,6,7,8,9 OPEN=t1,10,11,12,t2,t3CLOSED=1,2,3,4,5,6,7,8,9说明说明：对于：对于OPEN表中的叶节点直接移到表中的叶节点直接移到CLOSED表，不作任何处理表，不作任何处理删除删除XXX3、从、从OPEN表中取出节点表中取出节点10，并送到，并送到CLOSED表表4、扩展节点、扩展节点10，生成后继节点，生成后继节点 t4、13，并送到，并送到OPEN表的末端表的末端5、有叶节点、有叶节点6、实现可解标志过

15、程（可以判断节点、实现可解标志过程（可以判断节点10、6、3可可解）解）7、可以判断起始节点、可以判断起始节点1可解。算法结束可解。算法结束第十大循环第十大循环（3、4、5、6、7步）：步）：OPEN=11,12,A,t2,t3,t4,13 CLOSED=1,2,3,4,5,6,7,8,9,t1,10 搜索过程演示搜索过程演示123457689BCt1101112At2t3t413“与或树与或树”的深度：的深度：1、规定起始节点深度为、规定起始节点深度为02、其它节点深度等于其父节点的深度加、其它节点深度等于其父节点的深度加1解的性质解的性质：如果有解，宽度优先搜索能够保证求得一棵解如果有解，

16、宽度优先搜索能够保证求得一棵解树，它的最深的叶节点具有最小深度树，它的最深的叶节点具有最小深度3.4.2 深度优先搜索深度优先搜索 在与或树的深度优先搜索中，同样要设置一个在与或树的深度优先搜索中，同样要设置一个深深度界限度界限对于等于深度界限的节点，不再扩展，并将其标对于等于深度界限的节点，不再扩展，并将其标志为不可解节点，并在搜索过程中实行不可解标志为不可解节点，并在搜索过程中实行不可解标志过程志过程1、起始节点、起始节点S送送OPEN表表2、若、若S为叶节点，则成功结束，否则继续为叶节点，则成功结束，否则继续3、取出、取出OPEN表第一个节点（记作表第一个节点（记作n)，送到，送到CLO

17、SED表表与或树深度优先搜索算法与或树深度优先搜索算法：4、若节点、若节点 n 的深度等于深度界限，则将的深度等于深度界限，则将 n 标志为标志为不可解节点，并转不可解节点，并转10；否则继续；否则继续5、扩展节点、扩展节点 n，生成全部后继节点，置于，生成全部后继节点，置于 OPEN表前面，并设置指向表前面，并设置指向 n 的指针的指针6、（分三种情况）、（分三种情况）如果如果 n 无后继节点，则标志为不可解节点，并无后继节点，则标志为不可解节点，并转转l0，否则继续，否则继续若有后继节点为叶节点，则将这些叶节点标志为若有后继节点为叶节点，则将这些叶节点标志为可解节点，并继续；否则转可解节点

18、，并继续；否则转37、实行可解标志过程、实行可解标志过程8、若起始节点为可解节点，则算法成功结束；、若起始节点为可解节点，则算法成功结束；否则，继续下一步否则，继续下一步9、从、从OPEN表中删除含有可解先辈节点的节点，表中删除含有可解先辈节点的节点，并转并转310、实行不可解标志过程、实行不可解标志过程11、若起始节点为不可解，则失败结束，否则，、若起始节点为不可解，则失败结束，否则，继续下一步继续下一步12、从、从OPEN表中删去含有不可解先辈节点的节点表中删去含有不可解先辈节点的节点13、转、转31、第第4步要判断从步要判断从OPEN表取出来的节点的深度。表取出来的节点的深度。如果等于深

19、度界限，认定它为不可解节点如果等于深度界限，认定它为不可解节点2、第第5步将扩展出来的节点放到步将扩展出来的节点放到OPEN的前端，的前端，即即OPEN是堆栈是堆栈与宽度优先算法相比，深度优先算法的特殊之处与宽度优先算法相比，深度优先算法的特殊之处：注意注意由于深度限制，深度优先搜索算法有可能找不由于深度限制，深度优先搜索算法有可能找不到解到解例：例：注注：后生成的节点画在左边：后生成的节点画在左边162A354BttC7t8tt深度界限为深度界限为4课堂练习课堂练习：用宽度和深度优先搜索算法找出解树：用宽度和深度优先搜索算法找出解树提示提示：对于宽度优先搜索，先生成的节点画在左；：对于宽度优

20、先搜索，先生成的节点画在左；对于深度优先搜索，后生成的节点画在左对于深度优先搜索，后生成的节点画在左说明说明：先扩展的节点画在左边先扩展的节点画在左边1234567t1t2t3与或树的宽度与或树的宽度优先搜索优先搜索说明说明：后扩展的节点画在左边后扩展的节点画在左边12354XXt5t6深度界限为深度界限为4与或树的深度与或树的深度优先搜索优先搜索例例：某一个问题可能的解决方案可以表示成下列一棵与或某一个问题可能的解决方案可以表示成下列一棵与或树，请用宽度和深度优先搜索算法找出各自的解决方案？树，请用宽度和深度优先搜索算法找出各自的解决方案？可解可解不可解不可解与或树宽度优先与或树宽度优先搜索过程搜索过程（左先右后左先右后）XXXX与或树深度优先与或树深度优先搜索过程搜索过程（左先右后左先右后）XXXX其他搜索算法：其他搜索算法：与或树的代价优先搜索（和代价最小，与或树的代价优先搜索（和代价最小，最大代价最小）最大代价最小）与或图的启发搜索算法与或图的启发搜索算法AO*要掌握的算法要掌握的算法：与或树的宽度优先搜索算法与或树的宽度优先搜索算法与或树的深度优先搜索算法与或树的深度优先搜索算法