- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
共有12种操作，它们分别是：
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)
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
10
猴子摘香蕉问题的解
(a,b,0,0) 初始状态
Goto(b) Pushbox(c)
Goto(b)
(b,b,0,0) Climbbox
Pushbox(c) (c,c,0,0)
(b ,b,1,0)
Climbbox Pushbox(a)
(c,c,1,0)
(a,a,0,0)
a
Pushbox(c)
Pushbox(a)
19
4.3 状态空间搜索的结构 用来描述结点之间关系：祖先、后裔、父母、子女、兄弟
D A
E C
B
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
20
4.4 问题的状态空间表示法
图的结点和弧分别表示问题求解过程中解题状态和解题步骤。
初始状态对应于实际问题的已知信息, 是图中的根结点。 目标就是实际问题的解。 状态空间搜索将问题求解过程表现为从初始状态到目标状
态寻找这个路径的过程。
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
16
4.3 状态空间搜索的结构
图是结点及连接它们的边的集合。 如果图中每个结点都有一个或多个描述符(标记)使之与
6
83
21 4
765
7
283
714
65
8
23
184
765
9
23
184
765
10
28
143
765
11
283
145
76
12 13
283 283
16 4 1 64
7 5 75
14
83
15
16 17 18 19 20
283 12 3 23 4 2 8 283 283
21 4
71 4 8 4 1 8 14 3 14 5 6 4
4.1 用搜索法对问题求解
一个问题可以形式化地定义为四个组成部分： 初始状态 可能行动的描述 目标测试 路径耗散 问题的解就是从初始状态到目标状态的路径
寻找解的过程就是搜索
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
6
A B
123
一个问题可以形式化地定义为四个组成部分：
初始状态
可能行动的描述
目标测试
路径耗散
A
A
B
B
123
123
S0=(1, 1)
S4=(2, 2)
S8=(3, 3)
二阶梵塔问题的初始状态和目标状态
操作分别用A(i, j)和B(i, j)表示: A(i, j): 把金片A从第i号钢针移到j号钢针上； B(i, j): 把金片B从第i号钢针移到第j号钢针上。
其他结点区别开来, 这样的图称为标记图。 有方向性的弧连接的图是有向图。 图中的弧也可以做上标记，用来给关系取名或表示权
值。当一对结点间有多条弧相连时，这种方法可以使 之区别。
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
Grasp
(c,c,1,1) 目标状态
c
b
猴子摘香蕉问题的状态空间图
解序列为： {Goto(b), Pushbox(c), Climbbox, Grasp}
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
11
3. 八数码问题
724
5
6
831
12 345 678
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
12
八数码问题
状态：状态描述了8个棋子中的每一个以及空位在棋盘的9 个方格上的分布。
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
3
4.1 用搜索法对问题求解
状态空间的理论是我们用来回答这些疑问最主要的工具。
图由结点集和连接结点对的弧或边的集合组成。 结点：问题求解中的不同状态（棋局 / 推理结果） 弧：状态之间的转换（一步走棋 / 一条规则运用）
y表示猴子是否在箱子上，当
a
猴子在箱子上时，y取1，否则y
取0；
c
b
z表示猴子是否拿到香蕉，当 拿到香蕉时z取1，否则z取0。
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
17
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)} 有向图
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
2
4.1 用搜索法对问题求解
要成功地设计和实现搜索算法: 问题求解器是否一定能找到一个解? 问题求解器是否能终止运行, 或是否会陷入一个死循环? 当问题求解器找到解时, 找到的是否是最好的解? 搜索过程的时间与空间复杂性如何? 怎样才能最有效地降低搜索的复杂性? 怎样设计才能最有效地利用描述语言?
解：全部可能的问题状态共有以下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)
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
初始状态：任何状态都可以被指定为初始状态。注意要到 达任何一个给定的目标，可能的初始状态中恰好只有一半 可以作为开始。
后继函数：用来产生通过四个行动（把空位向Left，Right ，Up或Down移动）能够达到的合法状态。
目标测试：用来检测状态是否能匹配所要求的目标格局。
路径耗散：每一步的耗散值为1，因此整个路径的耗散值为 路径中的步数。
Department of Computer Science & Technology, Nanjing University Artificial Intelligence Spring
4
4.2 问题实例
1. 二阶梵塔问题 2. 设有三根钢针，它们的编号分别是1号、2号和3号。在初
始情况下，1号钢针上穿有A、B两个金片，A比B小，A 位于B的上面。要求把这两个金片全部移到另一根钢针 上，而且规定每次只能移动一个金片，任何时刻都不能 使大的位于小的上面。
(x, x, 0, 0)→(v, v, 0, 0)
Climbbox: 猴子爬上箱子，即
(x, x, 0, 0)→(x, x, 1, 0)
Grasp；猴子拿到香蕉，即
(Dcep,acrt,me1n,t o0f C)o→mp(ucte,r Scci,en1ce, &1T)echnology, Nanjing University Artificial IntComputer Science & Technology, Nanjing University Artificial Intelligence Spring
13
S0 2 8 3 1
14 765
2
283 14
765
3
23 1 84 765
4
283 14 765
5
283 16 4 75
9
初始状态:
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，即
7
A B
