人工智能 第3章(确定性推理3-与或树搜索).ppt

《人工智能 第3章(确定性推理3-与或树搜索).ppt》由会员分享，可在线阅读，更多相关《人工智能 第3章(确定性推理3-与或树搜索).ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人人 工工 智智 能能Artificial Intelligence(AI)许建华许建华南京师范大学计算机科学与技术学院南京师范大学计算机科学与技术学院2011年秋季年秋季第第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表表：存放待扩展的节点，此时是队列：存放待扩展的节点，此时是队列CLOSED表表：存放已扩展的

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

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

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

9、、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、无叶节点，转到、无叶节点，转到3步步OPEN=4,5,6,7 CLOSED=1,2,3 第三大循环第三大循环

10、（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表的末端表的末端5、无叶节点，转到、无叶节点，转到3步步OPEN=6,7,8,9,B,C CLOSED

11、=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步）：步）：OPEN=7,8,9,B,C,t1,10 CLOSED=1,2,3,4,5,6 3

12、、从、从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表表的末端的末端5、无叶节点，转到、无叶节点，转到3步步OPEN=9,B,C,t1,10,11,1

13、2,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中删除含有可解先辈节点的节点中删除含有可解先辈节点的节点第九大循环第九大循环（3、4、5、6、7、8步）：步）：OPEN=B,C,t1,10,11,12,A

14、,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、实现可解标志过程（可以判断节点、实现可解标志过程（可以判断节点10、6、3可可解）解）7、可以判断起始节点可

15、以判断起始节点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解的性质解的性质：如果有解，宽度优先搜索能够保证求得一棵解如果有解，宽度优先搜索能够保证求得一棵解树，它的最深的叶节点具有最小深度树，它的最深的叶节点具有最小深度3

16、.4.2 深度优先搜索深度优先搜索 在与或树的深度优先搜索中，同样要设置一个在与或树的深度优先搜索中，同样要设置一个深深度界限度界限对于等于深度界限的节点，不再扩展，并将其标对于等于深度界限的节点，不再扩展，并将其标志为不可解节点，并在搜索过程中实行不可解标志为不可解节点，并在搜索过程中实行不可解标志过程志过程1、起始节点、起始节点S送送OPEN表表2、若、若S为叶节点，则成功结束，否则继续为叶节点，则成功结束，否则继续3、取取出出OPEN表表第第一一个个节节点点（记记作作n)，送送到到CLOSED表表与或树深度优先搜索算法与或树深度优先搜索算法：4、若节点若节点 n 的深度等于深度界限，则将

17、的深度等于深度界限，则将 n 标志为标志为不可解节点，并转不可解节点，并转10；否则继续；否则继续5、扩扩展展节节点点 n，生生成成全全部部后后继继节节点点，置置于于 OPEN表前面，并设置指向表前面，并设置指向 n 的指针的指针6、（分三种情况）、（分三种情况）如如果果 n 无无后后继继节节点点，则则标标志志为为不不可可解解节节点点，并并转转l0，否则继续否则继续若若有有后后继继节节点点为为叶叶节节点点，则则将将这这些些叶叶节节点点标标志志为为可解节点，并继续；否则转可解节点，并继续；否则转37、实行可解标志过程、实行可解标志过程8、若若起起始始节节点点为为可可解解节节点点，则则算算法法成成

18、功功结结束束；否则，继续下一步否则，继续下一步9、从从OPEN表表中中删删除除含含有有可可解解先先辈辈节节点点的的节节点点，并转并转310、实行不可解标志过程、实行不可解标志过程11、若若起起始始节节点点为为不不可可解解，则则失失败败结结束束，否否则则，继继续下一步续下一步12、从、从OPEN表中删去含有不可解先辈节点的节点表中删去含有不可解先辈节点的节点13、转、转31、第第4步步要要判判断断从从OPEN表表取取出出来来的的节节点点的的深深度度。如果等于深度界限，认定它为不可解节点如果等于深度界限，认定它为不可解节点2、第第5步步将将扩扩展展出出来来的的节节点点放放到到OPEN的的前前端端，

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

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