10
a
c
b
初始状态: S0: (a, b, 0, 0) S1: (b, b, 0, 0) S2: (c, c, 0, 0) S3: (c, c, 1, 0) S4: (c, c, 1, 1) 目标状态
a c b
允许的操作为: Goto(u)：猴子走到位置u，即 (w, x, 0, 0)→(u, x, 0, 0) Pushbox(v): 猴子推着箱子到水平位置v，即 (x, x, 0, 0)→(v, v, 0, 0) Climbbox: 猴子爬上箱子，即 (x, x, 0, 0)→(x, x, 1, 0) Grasp；猴子拿到香蕉，即 (c, c, 1, 0 )→(c, c, 1, 1)
有向图
19
4.3 状态空间搜索的结构
有根图具有唯一一个称为根的结点,从根结点出发到图
中任何结点都存在相应路径。
A B C F G H D
E
I
J
有根树,一个家庭关系的例子
20
4.3 状态空间搜索的结构
用来描述结点之间关系：祖先、后裔、父母、子女、兄弟
E
D
C A B
21
4.4 问题的状态空间表示法
初始状态：任何状态都可以被指定为初始状态。注意要到达任何 一个给定的目标，可能的初始状态中恰好只有一半可以作为开始 。 后继函数：用来产生通过四个行动（把空位向Left，Right，Up 或Down移动）能够达到的合法状态。
目标测试：用来检测状态是否能匹配所要求的目标格局。
路径耗散：每一步的耗散值为1，因此整个路径的耗散值为路径 中的步数。
A B
A B
A B
2 3
1
2
3
1
1
2
S8=(3, 3)
3
S0=(1, 1)
S4=(2, 2)
二阶梵塔问题的初始状态和目标状态 操作分别用A(i, j)和B(i, j)表示:
A(i, j): 把金片A从第i号钢针移到j号钢针上；
B(i, j): 把金片B从第i号钢针移到第j号钢针上。 共有12种操作，它们分别是：
,产生新的条件,向目标靠近;目标驱动推理着眼于目标, 寻找产生目标的规则,通过反向连续的规则和子目标进 行反向推理直至找到问题给出的条件。
采用哪种方式取决于求解问题的结构。
29
4.5.1 数据驱动和目标驱动的搜索
目标驱动搜索可用于下列情况:
——问题的说明中给出了目标或假设, 或者很容易用公 式来表示它们。 ——有大量的规则适用于问题的条件,因而可以推出许 多结论和结果, 较早地选好目标可剪掉空间中许多分枝, 使目标驱动搜索的效率更高。 ——问题没有给出数据,必须在求解中获取。
图的结点和弧分别表示问题求解过程中解题状态和解题步骤。
初始状态对应于实际问题的已知信息, 目标就是实际问题的解。
是图中的根结点。
状态空间搜索将问题求解过程表现为从初始状态到目标状
态寻找这个路径的过程。
22
4.4 问题的状态空间表示法
[定义] 状态空间搜索 状态空间是一个四元组[N,A,S,GD]: N是图中状态结点集,代表问题求解过程中的各种状态。 A 是结点间弧(或链)的集合,代表问题求解过程的各个步骤。 S 是N的非空子集,包含问题的初始状态。 GD 是N的非空子集,包含问题的目标状态。 GD中的状态可用两种方式中的任一种来描述： 搜索中遇到了目标状态的可检测的性质； 欲搜索的路径的性质。 图中从S中结点到GD中结点的路径称为求解路径。 搜索算法的任务是在问题空间里找到一条求解路径。它包含了一系 列使问题得到解决的操作(算子)。
11
猴子摘香蕉问题的解
(a,b,0,0) Goto(b) Pushbox(c)
初始状态
Goto(b)
(b,b,0,0)
Climbbox (b ,b,1,0)
a c b
Pushbox(c)
Climbbox (c,c,1,0)
(c,c,0,0)
Pushbox(a)
(a,a,0,0)
Pushbox(c)
其他结点区别开来, 这样的图称为标记图。
有方向性的弧连接的图是有向图。

图中的弧也可以做上标记，用来给关系取名或表示权 值。当一对结点间有多条弧相连时，这种方法可以使 之区别。
18
E
D
C
A B
结点集={A, B, C, D, E}
弧集={(A,B), (A,D), (B,C), (C,B), (C,D), (D,A),(D,E), (E,C), (E,D)}
32
4.5.2 图搜索的实现
应用回溯算法
A
1 B E 2 F 6 5 J7 8 9 10 D
C
3
G goal
H 4
I
图一个假想状态空间的深度优先回溯搜索
33
4.5.2 图搜索的实现 定义一个回溯搜索的算法。设:
SL
为状态表,列出了当前路径上的状态。
NSL DE CS
为新状态表, 包含了等待评估的结点,其后裔结 点还未被扩展。
14
S0
2 8 3 1 4 7 6 5
1
2
2 8 3 1 4 7 6 5
3
2 3 1 8 4 7 6 5
4
2 8 3 1 4 7 6 5
5
2 8 3 1 6 4 7 5
6
8 3 2 1 4 7 6 5
7
2 8 3 7 1 4 6 5
8
2 3 1 8 4 7 6 5
9
2 3 1 8 4 7 6 5
10
30
4.5.1 数据驱动和目标驱动的搜索
数据驱动搜索可用于下列情况:
——问题的初始说明给出了全部或大部分数据。 ——存在大量可能的目标,但对实际问题的条件及给定的 信息加以运用的方法很少 。 ——难以形成一个目标或假设。
31
4.5.2 图搜索的实现
状态空间搜索的基本思想:
“扩展”是指对该节 点用某个可用操作 进行作用，生成该 节点的一组子节点
4
4.1 用搜索法对问题求解
状态空间的理论是我们用来回答这些疑问最主要的工具。
图由结点集和连接结点对的弧或边的集合组成。
结点：问题求解中的不同状态（棋局 / 推理结果）
弧：状态之间的转换（一步走棋 / 一条规则运用）
5
4.2 问题实例
1. 二阶梵塔问题
设有三根钢针，它们的编号分别是1号、2号和3号。在初始 情况下，1号钢针上穿有A、B两个金片，A比B小，A位 于B的上面。要求把这两个金片全部移到另一根钢针上， 而且规定每次只能移动一个金片，任何时刻都不能使大 的位于小的上面。 解：全部可能的问题状态共有以下9种： S0=(1, 1) S1=(1, 2) S2=(1, 3) S3=(2, 1) S4=(2, 2) S5=(2, 3) S6=(3, 1) S7=(3, 2) S8=(3, 3)
6
问题的初始状态集合: 目标状态集合:
S={S0} =(1, 1) G={S4, S5}={(2,2),(3,3)}
初始状态S0和目标状态S4、S8如图所示
A B
A B
A B
2 3
1
2
3
1
1
2
S8=(3, 3)
3
S0=(1, 1)
S4=(2, 2)
二阶梵塔问题的初始状态和目标状态
7
一个问题可以形式化地定义为四个组成部分： 初始状态 可能行动的描述 目标测试 路径耗散
• 先把问题的初始状态作为当前扩展节点对其进行扩展， 生成一组子节点
• 然后检查问题的目标状态是否出现在这些子节点中。
• 若出现，则搜索成功，找到了问题的解；若没出现， 则再按照某种搜索策略从已生成的子节点中选择一个节 点作为当前扩展节点。 • 重复上述过程，直到目标状态出现在子节点中或者没 有可供操作的节点为止。
A(1, 2) A(1, 3) A(2, 1) A(2, 3) A(3, 1) A(3, 2)
B(1, 2) B(1, 3) B(2, 1) B(2, 3) B(3, 1) B(3, 2)
8
(1,1) A(1,2) (2,1) B(1,3) (2,3) A(2,3) A(1,3) (3,1) B(1,2) (3,2) A(3,2)
A 100 125 E 100 125 D 100 125 75 C B 50
75
50
图 旅行推销员问题的一个例子
[A,D,C,B,E,A]:
开销为450
目标要求的是有最小开销的完整回路。
25
4.4 问题的状态空间表示法
多种可能解题路径的方法。 目标是开销最小的路径。 遍历搜索旅行推销员问题的复杂度为(N-1)!
(3,3)
(1,3)
(1,2)
(2,2)
从初始节点(1, 1)到目标节点(2, 2)及(3, 3)的任何一条路径都是问题的一个解。 最短的路径长度是?
9
2 猴子摘香蕉问题
解： 4元组 （w, x, y, z）
其中：
w表示猴子的水平位置； x表示箱子的水平位置； y表示猴子是否在箱子上，当 猴子在箱子上时，y取1，否则y 取0； z表示猴子是否拿到香蕉，当 拿到香蕉时z取1，否则z取0。
23
4.4 问题的状态空间表示法 例： 旅行推销员问题 假设一个推销员要到5个城市去访问,然后回家。问题 是要找到一条最短的路径,使得推销员访问过每个城 市后回到出发地。假定推销员在A城, 他最后要返回 原地。
A 75 125 E 100 125 D 100
24
100
B 50
125 75C50ຫໍສະໝຸດ 4.4 问题的状态空间表示法
第五章 搜索问题求解