人工智能 第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 与或树搜索（补充）,问题归约法原始问题中间问题 本原问题集 操作符,与或图起始节点中间节点终叶节点生成“与”、“或”后继节点的有向弧,1、终叶节点是可解的（因为它们与本原问题相关联的）2、如果某一个非终叶节点含有“或”后继节点，那么，只要有一个后继节点是可解的，这一个非终叶节点就是可解的3、如果某一个非终叶节点含有“与”后

2、继节点，那么，只要所有后继节点是可解的，这一个非终叶节点才是可解的,可解节点的定义是（递归地）：,1、没有后裔的非终叶节点是不可解节点2、如果某一个非终叶节点含有“或”后继节点，那么，只要当所有的后继节点都不可解时，这一个非终叶节点才是不可解的3、如果某一个非终叶节点含有“与”后继节点，那么，只要有一个后继节点是不可解的，这一个非终叶节点就是不可解的,不可解节点的定义（递归地）是：,根据可解与不可解节点的递归定义，用递归的方式作用于某一个与或图，以标出所有的可解节点与不可解节点,可解标志过程与不可解标志过程:,若初始节点被标志为可解节点，算法成功结束（有解）若起始节点被标志为不可解节点，则搜索

3、失败结束（无解）,算法结束的条件：,与或图的解图：由最少的可解节点所构成的子图，这些节点能够使问题的起始节点是可解的,与或树：除了起始节点，每一个节点只有一个父节点与或图：除了起始节点，每一个节点允许有多个父节点两者的关系：与或树是与或图的特例,约定：当一个节点生成后继节点时，它们是搜索过程中没有产生过的节点，并且以后也不会再生成它们。（每一个节点只允许生成一次）,3.4.1 宽度优先搜索,两个基本符号：OPEN表：存放待扩展的节点，此时是队列CLOSED表：存放已扩展的节点,1、起始节点 S 送 OPEN 表2、若 S 为叶节点，则成功结束，否则，继续3、取出 OPEN 表的第一个节点（记作

4、 n），并送 到CLOSED 表,与或树宽度优先搜索算法：,4、扩展节点 n，生成其全部后继节点，送OPEN表末端，并设置指向 n 的指针,说明：此时可能出现三种情况节点 n 无后继节点节点 n 有后继节点、并有叶节点节点 n 有后继节点、但无叶节点,5、若 n 无后继节点，标志 n 为不可解，并转9（10、11）；若后继节点中有叶节点，则标志这些叶节点为可解节点，并继续（6、7、8）；否则转3,6、实行可解标志过程7、若起始节点S标志为可解，则找到解而结束，否则继续8、从OPEN表中删去含有可解先辈节点的节点，并转3,9、实行不可解标志过程10、若起始节点S标志为不可解，则失败而结束，否则继

5、续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、5步）：,3、从OPEN表中取出节点2，并送到CLOSED表4、扩展节点2，生成后继节点4、5，并送到OPEN表的末端5、无叶节点，转到3步,OPEN=3,4,5 CLOSED=1,2,第二大循环（3、4、5步）：,

6、3、从OPEN表中取出节点3，并送到CLOSED表4、扩展节点3，生成后继节点6、7，并送到OPEN表的末端5、无叶节点，转到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表的末端5、无叶节点，转到3步,OPEN=6,7,8,9,B,C

7、 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步）：,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,1

8、1,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,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中删除含有可解先辈节点的节点,第九大循环（3、4、5

9、、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表，不作任何处理,删除,X,X,X,3、从OPEN表中取出节点10，并送到CLOSED表4、扩展节点10，生成后继节点 t4、13，并送到OPEN表的末端5、有叶节点6、实现可解标志过程（可以判断节点10、6、3可解）7、可以判断起始节点1可解。算法结束,第十大循环（3、4、5、6、7步）：,OPEN=11,12,A,t2,t

10、3,t4,13 CLOSED=1,2,3,4,5,6,7,8,9,t1,10,搜索过程演示,1,2,3,4,5,7,6,8,9,B,C,t1,10,11,12,A,t2,t3,t4,13,“与或树”的深度：1、规定起始节点深度为02、其它节点深度等于其父节点的深度加1,解的性质：如果有解，宽度优先搜索能够保证求得一棵解树，它的最深的叶节点具有最小深度,3.4.2 深度优先搜索,在与或树的深度优先搜索中，同样要设置一个深度界限对于等于深度界限的节点，不再扩展，并将其标志为不可解节点，并在搜索过程中实行不可解标志过程,1、起始节点S送OPEN表2、若S为叶节点，则成功结束，否则继续3、取出OPEN

11、表第一个节点（记作n)，送到CLOSED表,与或树深度优先搜索算法：,4、若节点 n 的深度等于深度界限，则将 n 标志为不可解节点，并转10；否则继续5、扩展节点 n，生成全部后继节点，置于 OPEN表前面，并设置指向 n 的指针,6、（分三种情况）如果 n 无后继节点，则标志为不可解节点，并转l0，否则继续若有后继节点为叶节点，则将这些叶节点标志为可解节点，并继续；否则转3,7、实行可解标志过程8、若起始节点为可解节点，则算法成功结束；否则，继续下一步9、从OPEN表中删除含有可解先辈节点的节点，并转3,10、实行不可解标志过程11、若起始节点为不可解，则失败结束，否则，继续下一步12、从

12、OPEN表中删去含有不可解先辈节点的节点13、转3,1、第4步要判断从OPEN表取出来的节点的深度。如果等于深度界限，认定它为不可解节点2、第5步将扩展出来的节点放到OPEN的前端，即OPEN是堆栈,与宽度优先算法相比，深度优先算法的特殊之处：,注意由于深度限制，深度优先搜索算法有可能找不到解,例：,注：后生成的节点画在左边,1,6,2,A,3,5,4,B,t,t,C,7,t,8,t,t,深度界限为4,课堂练习：用宽度和深度优先搜索算法找出解树,提示：对于宽度优先搜索，先生成的节点画在左；对于深度优先搜索，后生成的节点画在左,说明：先扩展的节点画在左边,1,2,3,4,5,6,7,t1,t2,t3,与或树的宽度优先搜索,说明：后扩展的节点画在左边,1,2,3,5,4,X,X,t5,t6,深度界限为4,与或树的深度优先搜索,例：某一个问题可能的解决方案可以表示成下列一棵与或树，请用宽度和深度优先搜索算法找出各自的解决方案？,可解,不可解,与或树宽度优先搜索过程（左先右后）,X,X,X,X,与或树深度优先搜索过程（左先右后）,X,X,X,X,其他搜索算法：与或树的代价优先搜索（和代价最小，最大代价最小）与或图的启发搜索算法AO*,要掌握的算法：与或树的宽度优先搜索算法与或树的深度优先搜索算法,