4、扩展节点1，生成后继节点2、3，并送到 OPEN表的末端
5、无叶节点，转到3步
OPEN= { 2，3 }
CLOSED= { 1 }
第19页/共56页
第二大循环（3、4、5步）： 3、从OPEN表中取出节点2，并送到CLOSED表 4、扩展节点2，生成后继节点4、5，并送到OPEN
表的末端 5、无叶节点，转到3步
OPEN表的末端 5、无叶节点，转到3步
OPEN= { 8, 9, B, C, t1, 10, 11, 12 } CLOSED= { 1, 2, 3, 4, 5, 6, 7 }
第26页/共56页
第八大循环（3、4、5步）： 3、从OPEN表中取出节点8，并送到CLOSED表 4、扩展节点8，生成后继节点A，并送到OPEN表
到CLOSED 表
第11页/共56页
4、扩展节点 n ，生成其全部后继节点，送OPEN 表末端，并设置指向 n 的指针
说明：此时可能出现三种情况 ➢节点 n 无后继节点 ➢节点 n 有后继节点、并有叶节点 ➢节点 n 有后继节点、但无叶节点
第12页/共56页
5、若 n 无后继节点，标志 n 为不可解，并转9 （10、11）；若后继节点中有叶节点，则标志 这些叶节点为可解节点，并继续（6、7、8）； 否则转3
第3页/共56页
不可解节点的定义（递归地）是：
1、没有后裔的非终叶节点是不可解节点 2、如果某一个非终叶节点含有“或”后继节点， 那么，只要当所有的后继节点都不可解时，这一 个非终叶节点才是不可解的
3、如果某一个非终叶节点含有“与”后继节点， 那么，只要有一个后继节点是不可解的，这一个 非终叶节点就是不可解的
与或图的解图： 由最少的可解节点所构成的子图，这些节 点能够使问题的起始节点是可解的
第7页/共56页
与或树：除了起始节点，每一个节点只有一
个父节点
与或图：除了起始节点，每一个节点允许有
多个父节点
两者的关系：与或树是与或图的特例
第8页/共5生过的节点，并且以后也不会 再生成它们。（每一个节点只允许生成一次）
第15页/共56页
第16页/共56页
例
说明：先扩展出来的节点画在左边
第17页/共56页
算法的运行过程
初始化： 节点 1 送OPEN表，且不为叶节点
OPEN= { 1 } CLOSED= { }
第18页/共56页
第一大循环（算法的3、4、5步）：
3、从OPEN表中取出节点1，并送到CLOSED表
第13页/共56页
6、实行可解标志过程 7、若起始节点S标志为可解，则找到解而结束，
否则继续 8、从OPEN表中删去含有可解先辈节点的节点，
并转3
第14页/共56页
9、实行不可解标志过程 10、若起始节点S标志为不可解，则失败而结束，
否则继续 11、从OPEN表中删去含有不可解先辈节点的节点 12、转3
第21页/共56页
第四大循环（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 }
第22页/共56页
第五大循环（3、4、5步）： 3、从OPEN表中取出节点5，并送到CLOSED表 4、扩展节点5，生成后继节点B、C，并送到
第2页/共56页
可解节点的定义是（递归地）：
1、终叶节点是可解的（因为它们与本原问题相关 联的）
2、如果某一个非终叶节点含有“或”后继节点， 那么，只要有一个后继节点是可解的，这一个非终 叶节点就是可解的
3、如果某一个非终叶节点含有“与”后继节点， 那么，只要所有后继节点是可解的，这一个非终叶 节点才是可解的
第9页/共56页
3.4.1 宽度优先搜索 两个基本符号：
OPEN表：存放待扩展的节点，此时是队列 CLOSED表：存放已扩展的节点
第10页/共56页
与或树宽度优先搜索算法：
1、起始节点 S 送 OPEN 表 2、若 S 为叶节点，则成功结束，否则，继续 3、取出 OPEN 表的第一个节点（记作 n ），并送
第4页/共56页
可解标志过程与不可解标志过程:
根据可解与不可解节点的递归定义，用递归的方 式作用于某一个与或图，以标出所有的可解节点 与不可解节点
第5页/共56页
算法结束的条件： ➢ 若初始节点被标志为可解节点，算法成 功结束（有解） ➢ 若起始节点被标志为不可解节点，则搜 索失败结束（无解）
第6页/共56页
OPEN= { 3, 4, 5 } CLOSED= { 1, 2 }
第20页/共56页
第三大循环（3、4、5步）： 3、从OPEN表中取出节点3，并送到CLOSED表 4、扩展节点3，生成后继节点6、7，并送到OPEN
表的末端 5、无叶节点，转到3步
OPEN= { 4, 5, 6, 7 } CLOSED= { 1 , 2, 3 }
表的末端 5、有叶节点 6、实现可解过程（无法判断节点6是否可解） 7、无法判断起始节点是否可解 8、OPEN表中无节点可以删除（转到3）
第24页/共56页
OPEN= { 7, 8, 9, B, C, t1, 10 } CLOSED= { 1 , 2, 3, 4, 5, 6 }
第25页/共56页
第七大循环（3、4、5步）： 3、从OPEN表中取出节点7，并送到CLOSED表 4、扩展节点7，生成后继节点11、12，并送到
第3章 搜索原理
3.1 图的搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 与或树搜索（补充） 3.5 博弈树搜索（补充） 3.6 消解原理
第1页/共56页
3.4 与或树搜索（补充）
问题归约法 原始问题 中间问题
本原问题集 操作符
与或图 起始节点
中间节点
终叶节点
生成“与”、“ 或”后继 节点的有向弧
OPEN表的末端 5、无叶节点，转到3步
OPEN= { 6, 7, 8, 9, B, C } CLOSED= { 1 , 2, 3, 4, 5 }
第23页/共56页
第六大循环（3、4、5、6、7、8步）： 3、从OPEN表中取出节点6，并送到CLOSED表 4、扩展节点6，生成后继节点t1、10，并送到OPEN