《人工智能第3章确定性推理3-与或树搜索》由会员分享，可在线阅读，更多相关《人工智能第3章确定性推理3-与或树搜索（57页珍藏版）》请在金锄头文库上搜索。
1、人 工 智 能 Artificial Intelligence (AI) 许建华 xujianhua 南京师范大学计算机科学与技术学院 2011年秋季 第3章 确定性推理 3.1 图的搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 与或树搜索（补充） 3.5 博弈树搜索（补充） 3.6 消解原理 3.4 与或树搜索（补充） 问题归约法 原始问题 中间问题 本原问题集 操作符 与或图 起始节点 中间节点 终叶节点 生成“与”、“ 或”后继 节点的有向弧 1、终叶节点是可解的（因为它们与本原问题相关 联的） 2、如果某一个非终叶节点含有“或”后继节点，那 么，只要有一个后继节点是可解的，这
2、一个非终叶 节点就是可解的 3、如果某一个非终叶节点含有“与”后继节点， 那么，只要所有后继节点是可解的，这一个非终叶 节点才是可解的 可解节点的定义是（递归地）： 1、没有后裔的非终叶节点是不可解节点 2、如果某一个非终叶节点含有“或”后继节点， 那么，只要当所有的后继节点都不可解时，这一 个非终叶节点才是不可解的 3、如果某一个非终叶节点含有“与”后继节点 ，那么，只要有一个后继节点是不可解的，这一 个非终叶节点就是不可解的 不可解节点的定义（递归地）是： 根据可解与不可解节点的递归定义，用递归的方 式作用于某一个与或图，以标出所有的可解节点 与不可解节点 可解标志过程与不可解标志过程:
3、若初始节点被标志为可解节点，算法成 功结束（有解） 若起始节点被标志为不可解节点，则搜 索失败结束（无解） 算法结束的条件： 与或图的解图： 由最少的可解节点所构成的子图，这些节 点能够使问题的起始节点是可解的 与或树：除了起始节点，每一个节点只有一 个父节点 与或图：除了起始节点，每一个节点允许有 多个父节点 两者的关系：与或树是与或图的特例 约定：当一个节点生成后继节点时，它们是搜 索过程中没有产生过的节点，并且以后也不会 再生成它们。（每一个节点只允许生成一次） 3.4.1 宽度优先搜索 两个基本符号： OPEN表：存放待扩展的节点，此时是队列 CLOSED表：存放已扩展的节点 1、起始
4、节点 S 送 OPEN 表 2、若 S 为叶节点，则成功结束，否则，继续 3、取出 OPEN 表的第一个节点（记作 n ），并送 到CLOSED 表 与或树宽度优先搜索算法： 4、扩展节点 n ，生成其全部后继节点，送OPEN 表末端，并设置指向 n 的指针 说明：此时可能出现三种情况 节点 n 无后继节点 节点 n 有后继节点、并有叶节点 节点 n 有后继节点、但无叶节点 5、若 n 无后继节点，标志 n 为不可解，并转9（ 10、11）；若后继节点中有叶节点，则标志这 些叶节点为可解节点，并继续（6、7、8）； 否则转3 6、实行可解标志过程 7、若起始节点S标志为可解，则找到解而结束 ，
5、否则继续 8、从OPEN表中删去含有可解先辈节点的节点 ，并转3 9、实行不可解标志过程 10、若起始节点S标志为不可解，则失败而结束，否 则继续 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，并送到CLOS
6、ED表 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 第三大循环（3、4、5步）： 3、从OPEN表中取出节点4，并送到CLOSED表 4、扩展节点4，生成后继节点8、9，并送到OPEN 表的末端 5、无叶节点，转到3步 OPEN= 5, 6, 7, 8, 9 CLOS
7、ED= 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= 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、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, 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,
9、12, A CLOSED= 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, t2, t3 CLOSED= 1, 2, 3, 4, 5, 6, 7, 8, 9 OPEN= t1, 10, 11, 12, t2,
10、t3 CLOSED= 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, t3, t4, 13 CLOSED= 1, 2, 3, 4, 5, 6, 7, 8, 9, t1, 10 搜索过程演示 1 2
11、 3 45 76 89BC t 1 1 0 11 1 2 A t 2 t 3 t 4 13 “与或树”的深度： 1、规定起始节点深度为0 2、其它节点深度等于其父节点的深度加1 解的性质： 如果有解，宽度优先搜索能够保证求得一棵解 树，它的最深的叶节点具有最小深度 3.4.2 深度优先搜索 在与或树的深度优先搜索中，同样要设置一个深 度界限 对于等于深度界限的节点，不再扩展，并将其标 志为不可解节点，并在搜索过程中实行不可解标 志过程 1、起始节点S送OPEN表 2、若S为叶节点，则成功结束，否则继续 3、取出OPEN表第一个节点（记作n )，送到 CLOSED表 与或树深度优先搜索算法： 4
12、、若节点 n 的深度等于深度界限，则将 n 标志为 不可解节点，并转10；否则继续 5、扩展节点 n ，生成全部后继节点，置于 OPEN 表前面，并设置指向 n 的指针 6、（分三种情况） 如果 n 无后继节点，则标志为不可解节点，并转 l0，否则继续 若有后继节点为叶节点，则将这些叶节点标志为 可解节点，并继续；否则转3 7、实行可解标志过程 8、若起始节点为可解节点，则算法成功结束； 否则，继续下一步 9、从OPEN表中删除含有可解先辈节点的节点， 并转3 10、实行不可解标志过程 11、若起始节点为不可解，则失败结束，否则， 继续下一步 12、从OPEN表中删去含有不可解先辈节点的节点
13、13、转3 1、第4步要判断从OPEN表取出来的节点的深度 。如果等于深度界限，认定它为不可解节点 2、第5步将扩展出来的节点放到OPEN的前端， 即OPEN是堆栈 与宽度优先算法相比，深度优先算法的特殊之处： 注意 由于深度限制，深度优先搜索算法有可能找不 到解 例： 注：后生成的节点画在左边 1 62 A3 54 Btt C7 t8 tt 深度界限为4 课堂练习：用宽度和深度优先搜索算法找出解树 提示：对于宽度优先搜索，先生成的节点画在左； 对于深度优先搜索，后生成的节点画在左 说明： 先扩展的节点画在左边 1 2 3 4 56 7 t 1 t 2 t 3 与或树的宽度 优先搜索 说明： 后扩展的节点画在左边 1 2 3 54 X X t5 t6 深度界限为4 与或树的深度 优先搜索 例：某一个问题可能的解决方案可以表示成下列一棵与或 树，请用宽度和深度优先搜索算法找出各自的解决方案？ 可解 不可解 与或树宽度优先 搜索过程 （左先右后） XX XX 与或树深度优先 搜索过程 （左先右后） XXXX 其他搜索算法： 与或树的代价优先搜索（和代价最小， 最大代价最小） 与或图的启发搜索算法AO* 要掌握的算法： 与或树的宽度优先搜索算法 与或树的深度优先搜索算法
