- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
与或图的解图： 与或图的解图： 由最少的可解节点所构成的子图， 由最少的可解节点所构成的子图，这些节 点能够使问题的起始节点是可解的
与或树：除了起始节点，每一个节点只有一 除了起始节点，
个父节点
与或图：除了起始节点，每一个节点允许有 除了起始节点，
多个父节点
两者的关系：与或树是与或图的特例
约定：当一个节点生成后继节点时，它们是搜 当一个节点生成后继节点时，
5、若 n 无后继节点 ， 标志 n 为不可解 ， 并转 、 无后继节点， 为不可解，并转9 （10、11）；若后继节点中有叶节点 ，则标志 、 ） 若后继节点中有叶节点， 这些叶节点为可解节点， 并继续（ 、 、 ） 这些叶节点为可解节点 ， 并继续 （ 6、 7、 8） ； 否则转3 否则转
6、实行可解标志过程 、 7、若起始节点 标志为可解，则找到解而结束， 、若起始节点S标志为可解 则找到解而结束， 标志为可解， 否则继续 8、从OPEN表中删去含有可解先辈节点的节点， 、 表中删去含有可解先辈节点的节点， 表中删去含有可解先辈节点的节点 并转3 并转
索过程中没有产生过的节点，并且以后也不会 索过程中没有产生过的节点， 再生成它们。 每一个节点只允许生成一次） 再生成它们。（每一个节点只允许生成一次）
3.4.1 宽度优先搜索 两个基本符号：
OPEN表：存放待扩展的节点，此时是队列 表 存放待扩展的节点， CLOSED表：存放已扩展的节点 表
与或树宽度优先搜索算法： 与或树宽度优先搜索算法：
第二大循环（ 、 、 步 第二大循环（3、4、5步）： 3、从OPEN表中取出节点 ，并送到 、 表中取出节点2，并送到CLOSED表 表中取出节点 表 4、扩展节点2，生成后继节点 、5，并送到 、扩展节点 ，生成后继节点4、 ，并送到OPEN 表的末端 5、无叶节点，转到3步 、无叶节点，转到 步
解的性质：
如果有解，宽度优先搜索能够保证求得一棵解 如果有解， 树，它的最深的叶节点具有最小深度
3.4.2 深度优先搜索
在与或树的深度优先搜索中，同样要设置一个深 在与或树的深度优先搜索中，同样要设置一个深 度界限 对于等于深度界限的节点，不再扩展， 对于等于深度界限的节点，不再扩展，并将其标 志为不可解节点，并在搜索过程中实行不可解标 志为不可解节点， 志过程
X X
X
第十大循环（ 、 、 、 、 步 第十大循环（3、4、5、6、7步）： 3、从OPEN表中取出节点 ，并送到 、 表中取出节点10，并送到CLOSED表 表中取出节点 表 4、扩展节点10，生成后继节点 t4、13，并送到 、扩展节点 ， 、 ， OPEN表的末端 表的末端 5、有叶节点 、 6、实现可解标志过程（可以判断节点10、6、3可 、实现可解标志过程（可以判断节点 、 、 可 解） 7、可以判断起始节点1可解。算法结束 、可以判断起始节点 可解。 可解
人
工
智
能
Artificial Intelligence (AI)
许建华 xujianhua@ 南京师范大学计算机科学与技术学院 2010年秋季 年秋季
第3章 搜索原理 章
3.1 图的搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 与或树搜索（补充） 与或树搜索（补充） 3.5 博弈树搜索（补充） 博弈树搜索（补充） 3.6 消解原理
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步 、无叶节点，转到 步
不可解节点的定义（递归地） 不可解节点的定义（递归地）是： 的定义
1、没有后裔的非终叶节点是不可解节点 、 2、 如果某一个非终叶节点含有 “ 或 ” 后继节点 ， 、 如果某一个非终叶节点含有“ 后继节点， 那么，只要当所有的后继节点都不可解时， 那么，只要当所有的后继节点都不可解时，这一 个非终叶节点才是不可解的 3、 如果某一个非终叶节点含有 “ 与 ” 后继节点 ， 、 如果某一个非终叶节点含有“ 后继节点， 那么，只要有一个后继节点是不可解的， 那么，只要有一个后继节点是不可解的，这一个 非终叶节点就是不可解的
删除 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, t3} CLOSED= {1, 2, 3, 4, 5, 6, 7, 8, 9} 说明：对于 说明：对于OPEN表中的叶节点直接移到 表中的叶节点直接移到 CLOSED表，不作任何处理 表
3.4 与或树搜索（补充） 与或树搜索（补充）
问题归约法 原始问题 中间问题 本原问题集 操作符 与或图 起始节点 中间节点 终叶节点 生成“ 生成“与”、“ 或”后继 节点的有向弧
可解节点的定义是（递归地）： 可解节点的定义是（递归地） 的定义是
1、终叶节点是可解的（ 因为它们与本原问题相关 、 终叶节点是可解的（ 是可解的 联的） 联的） 2、如果某一个非终叶节点含有“或 ” 后继节点， 、 如果某一个非终叶节点含有“ 后继节点， 那么，只要有一个后继节点是可解的，这一个非终 那么，只要有一个后继节点是可解的， 叶节点就是可解的 3、如果某一个非终叶节点含有“与 ” 后继节点， 、 如果某一个非终叶节点含有“ 后继节点， 那么，只要所有后继节点是可解的， 那么，只要所有后继节点是可解的，这一个非终叶 节点才是可解的
第六大循环（ 、 、 、 、 、 步 第六大循环（3、4、5、6、7、8步）： 3、从OPEN表中取出节点 ，并送到 、 表中取出节点6，并送到CLOSED表 表中取出节点 表 4、扩展节点6，生成后继节点 、10，并送到 、扩展节点 ，生成后继节点t1、 ，并送到OPEN 表的末端 5、有叶节点 、 6、实现可解过程（无法判断节点6是否可解） 、实现可解过程（无法判断节点 是否可解 是否可解） 7、无法判断起始节点是否可解 、 8、OPEN表中无节点可以删除（转到 ） 、 表中无节点可以删除（ 表中无节点可以删除 转到3）
OPEN= { 5, 6, 7, 8, 9 } CLOSED= { 1, 2, 3, 4 }
第五大循环（ 、 、 步 第五大循环（3、4、5步）： 3、从OPEN表中取出节点 ，并送到 、 表中取出节点5，并送到CLOSED表 表中取出节点 表 4、扩展节点5，生成后继节点 、C，并送到 、扩展节点 ，生成后继节点B、 ， OPEN表的末端 表的末端 5、无叶节点，转到3步 、无叶节点，转到 步 OPEN= { 6, 7, 8, 9, B, C } CLOSED= { 1 , 2, 3, 4, 5 }
OPEN= {9, B, C, t1, 10, 11, 12, A} CLOSED= {1, 2, 3, 4, 5, 6, 7, 8}
第九大循环（ 、 、 、 、 、 步 第九大循环（3、4、5、6、7、8步）： 3、从OPEN表中取出节点 ，并送到 、 表中取出节点9，并送到CLOSED表 表中取出节点 表 4、扩展节点9，生成后继节点 t2、t3，并送到 、扩展节点 ， 、 ， OPEN表的末端 表的末端 5、有叶节点 、 6、实现可解标志过程（可以判断节点9、4、2可解） 、实现可解标志过程（可以判断节点 、 、 可解 可解） 7、无判断起始节点1可解 、无判断起始节点 可解 8、从OPEN中删除含有可解先辈节点的节点 、 中删除含有可解先辈节点的节点
OPEN= { 4, 5, 6, 7 } CLOSED= { 1 , 2, 3 }
第四大循环（ 、 、 步 第四大循环（3、4、5步）： 3、从OPEN表中取出节点 ，并送到 、 表中取出节点4，并送到CLOSED表 表中取出节点 表 4、扩展节点4，生成后继节点 、9，并送到 、扩展节点 ，生成后继节点8、 ，并送到OPEN 表的末端 5、无叶节点，转到3步 、无叶节点，转到 步
9、实行不可解标志过程 、 10、 若起始节点 标志为不可解 ， 则失败而结束 ， 、 若起始节点S标志为不可解 则失败而结束， 标志为不可解， 否则继续 11、从OPEN表中删去含有不可解先辈节点的节点 、 表中删去含有不可解先辈节点的节点 12、转3 、
例
说明： 说明：先扩展出来的节点画在左边
OPEN= { 3, 4, 5 } CLOSED= { 1, 2 }
第三大循环（ 、 、 步 第三大循环（3、4、5步）： 3、从OPEN表中取出节点 ，并送到 、 表中取出节点3，并送到CLOSED表 表中取出节点 表 4、扩展节点3，生成后继节点 、7，并送到 、扩展节点 ，生成后继节点6、 ，并送到OPEN 表的末端 5、无叶节点，转到3步 、无叶节点，转到 步
1、起始节点 S 送 OPEN 表 、 2、若 S 为叶节点，则成功结束，否则，继续 、 为叶节点，则成功结束，否则， 3、取出 OPEN 表的第一个节点（记作 n ），并送 、 表的第一个节点（ 到CLOSED 表
4、扩展节点 n ，生成其全部后继节点，送OPEN 、 生成其全部后继节点， 表末端， 表末端，并设置指向 n 的指针 说明：此时可能出现三种情况 说明： 节点 n 无后继节点 有后继节点、 节点 n 有后继节点、并有叶节点 有后继节点、 节点 n 有后继节点、但无叶节点
算法的运行过程
初始化： 初始化： 节点 1 送OPEN表，且不为叶节点 表
Hale Waihona Puke OPEN= { 1 } CLOSED= { }
第一大循环（算法的 、 、 步 第一大循环（算法的3、4、5步）： 3、从OPEN表中取出节点 ，并送到 、 表中取出节点1，并送到CLOSED表 表中取出节点 表 4、扩展节点1，生成后继节点 、3，并送到 、扩展节点 ，生成后继节点2、 ， OPEN表的末端 表的末端 5、无叶节点，转到3步 、无叶节点，转到 步 OPEN= { 2，3 } ， CLOSED= { 1 }
