4
76 5
（目标状态）
可以使用的操作：空格左移，空格上移，空格右 移，空格下移。 要求应用深度优先搜索策略寻找从初始状态到目 标状态的解路径。
2020/6/29
人工智能导论 - 刘珊
14
28 3
1 14
76 5
3.5 盲目搜索
28 3
2
14
76 5
6
7
23
3 18 4
76 5
8
9
28 3
4 16 4
23 4 18
76 5
28 3
4 16 4
75
10
11
28 3 28 3
16 4 16 4
75 7 5
18
19
28 3 28 3 6 4 16
17 5 75 4
28 3
5
14
76 5
12
13
28
28 3
14 3 14 5
76 5 76
20
21
28 14 3 76 5
28 3 14 5
76
22
23 24
– 宽度优先搜索（广度优先搜索） – 深度优先搜索 – 等代价搜索
2020/6/29
人工智能导论 - 刘珊
3.5 盲目搜索
8
状态空间的宽度优先搜索
3.5 盲目搜索
• 定义
– 以接近起始节点的程度逐层扩展节点的搜索方 法
• 基本思想
– 从初始节点S0开始逐层向下扩展，在第n层节 点还没有全部搜索完之前，不进入第n+1层节 点的搜索。
– 首先扩展最新产生的(即最深的)节点。
• 基本思想
– 从初始节点S0开始，选择最新产生的节点考察 扩展，直到找到目标节点为止。
– OPEN表中总是将新产生的节点放在OPEN表的 前端。
2020/6/29
人工智能导论 - 刘珊
13
八数码难题
3.5 盲目搜索
28 3
1
4
76 5
（初始状态）
12 3
8
是否有后继节点
是
为目标节点？
否
人工智能导论 - 刘珊
3.5 盲目搜索
失败
成功
10
八数码难题
3.5 盲目搜索
28 3
1
4
76 5
（初始状态）
12 3
8
4
76 5
（目标状态）
可以使用的操作：空格左移，空格上移，空格右 移，空格下移。 要求应用宽度优先搜索策略寻找从初始状态到目 标状态的解路径。
2020/6/29
12 3 12 3 78 4 8 4
6 5 76 5
八数码难题的 深度优先搜索树
右图：
父节点
2020/6/29
人工智能导论 - 刘珊
6
第三章 确定性推理
• 3.1 推理概述 • 3.2 自然演绎推理 • 3.3 消解原理 • 3.4 图搜索概述 • 3.5 盲目搜索 • 3.6 启发式搜索
2020/6/29
人工智能导论 - 刘珊
7
盲目搜索
• 特点：不需重排OPEN表 • 状态空间的盲目搜索 • 与或图的盲目搜索 • 类型
第三章 确定性推理
• 3.1 推理概述 • 3.2 自然演绎推理 • 3.3 消解原理 • 3.4 图搜索概述 • 3.5 盲目搜索 • 3.6 启发式搜索
2020/6/29
人工智能导论 - 刘珊
1
搜索
3.4 图搜索概述
• 定义
– 依靠经验，利用已有知识，根据问题的实际情 况，不断寻找可利用知识，从而构造一条代价 最小的推理路线，使问题得以解决的过程称为 搜索。
人工智能导论 - 刘珊
11
28 3
1 14
76 5
3.5 盲目搜索
28 3
2
14
76 5
6
7
23
3 18 4
76 5
8
9
8 3 28 3
21 4 71 4
76 5
65
14
15
83 21 4 76 5
28 3 71 4
65
23 1 8 44 76 5
23 18 4 76 5
16 17
12 3 84
76 5
2020/6/29
人工智能导论 - 刘珊
3.4 图搜索概述
4
图 搜 索 过 程 框 图
2020/6/29
开始
3.4 图搜索概述
把S0放入OPEN表
OPEN表为空表？
是
否
把OPEN表中第一个节点(n)移至CLOSED表
失败
n为目标节点吗？
是 成功
否 扩展n，把其后继节点放入OPEN表
的末端，提供返回节点n的指针
– 顶点或节点、边、环 – 有限图、简单图、带权图、连通图、网络
• 隐式图
– 子集树、排列树
• 图的存储
– 邻接矩阵：表示顶点之间相邻关系的矩阵 – 邻接表：由边表和顶点表两部分组成
2020/6/29
人工智能导论 - 刘珊
3
图搜索
• 穷举搜索 • 启发式搜索 • 术语
– 问题状态、状态空间 – 解状态：一些问题状态 – 答案状态：一些解状态 – 状态空间树：解空间的树结构 – 活节点、E-节点、死节点 – 节点深度 – 路径、路径代价 – 节点扩展
• 类型
– 盲目搜索：按预定的控制策略进行搜索，在搜 索过程中获得的中间信息并不改变控制策略。
– 启发式搜索：在搜索中加入了与问题有关的启 发性信息，用于指导搜索朝着最有希望的方向 前进，加速问题的求解过程并找到最优解。
2020/6/29
人工智能导论 - 刘珊
2
图
3.4 图搜索概述
• 一种限制最少的数据结构。 • 显式图
75
28 3
5
14
76 5
8 3 28 3 21 4 71 4
76 5
65
14
15
83 21 4 76 5
28 3 71 4
65
23 18 4
76 5
16
12 3 84
76 5
23 18 4 76 5
22
23 24
25 26
27
83 81 3 21 4 2 4 76 5 76 5
28 3 28 3 7 4 714 61 5 6 5
– Open表中的节点总是按进入的先后排序。
• 特点
– 一种高代价搜索，但若有解存在，必能找到
2020/6/29
人工智能导论 - 刘珊
9
宽 度 优 先 算 法 框 图
2020/6/29
开始
把S0放入OPEN表
OPEN表为空表？
是
否
把第一个节点(n)从OPEN表移至 CLOSED表
扩展n，把n的后继节点放入OPEN 表的末端，提供返回节点n的指针
25 26
27Leabharlann 8 3 8 1 3 2 8 3 2 8 3 12 3 12 3
21 4 2 4 7 4 7 1 4 7 8 4 8 4
76 5 76 5 61 5 6 5
6 5 76 5
八数码难题的 宽度优先搜索树
2020/6/29
人工智能导论 - 刘珊
12
状态空间的深度优先搜索
3.5 盲目搜索
• 定义
修改指针方向
S0
Path1
n
Path2
m
重排OPEN表
提高效率 p
的关键
人工智能导论 - 刘珊
5
图搜索
3.4 图搜索概述
OPEN表：存放刚生成的节 状态节点 父节点
点，也称为未扩展节点表。 OPEN表的一般形式如右图：
CLOSED表：存放已经扩
展或将要扩展的节点。
编号
状态节点
CLOSED表的一般形式如