2021
9
8.1.1 问题的解空间
对于n=3的0/1背包问题，其解空间树如图8.1.1-2所示，树中的 8个叶子结点分别代表该问题的8个可能解。
1 1
2
1
0
0
9
1
0
3
1
0
4
5
6
1
0
10
1
0
7
8
11
12
图8.1.1-2
3
1
0
14 15
2021
对物品1的选择 对物品2的选择 对物品3的选择
10
8.1.1 问题的解空间
Q
？ 解空间大小： 88 8!
2021
8
8.1.1 问题的解空间
三、状态空间树：解空间的树结构
问题的解空间一般用解空间树（Solution Space Trees, 也称状态空间树）的方式组织，树的根结点位于第1层， 表示搜索的初始状态，第2层的结点表示对解向量的第一 个分量做出选择后到达的状态，第1层到第2层的边上标出 对第一个分量选择的结果，依此类推，从树的根结点到叶 子结点的路径（也可能是根节点到任何一个树中结点，但 不含搜索失败的结点），就构成了解空间的一个可能解。
40
45
51
56
61
3 4 2 4 3 2 3 4 1 4 1 32 4 1 4 1 2 3 21 3 1 2
4 6 9 11 14 16 20 22 25 27 30 32 36 38 41 43 46 48 52 54 57 59 62 64
4 34 2 2 3 4 3 4 13 1 4 24 12 12 3 3 12 1
假设集合Si的大小是mi ，解空间的大小为m=m1m2…mn。
2021
6
8.1.1 问题的解空间
显式约束条件常见的例子是：
当 xi≥0
即 Si={所有非负实数}
当 xi=0或xi=1
即 Si={0，1}
当 li xi ui 即
Si {a : li a ui}
注意：“解空间”是指满足显式约束条件的元组，并非一般意 义上的解。
隐式约束：规定解空间中那些实际上满足目标约束的向量。
2021
7
8.1.1 问题的解空间
例 8皇后问题 。
12345678
1
解的表示：X=(x1,x2,…,x8)
2
Q Q
显式约束: xi∈Si ，1≤i≤8， Si={1,2,3,4,5,6,7,8}
3 4Q 5 6Q
Q Q
隐式约束：
7
Q
任何两个皇后不能相互攻击 8
2021
5
8.1.1 问题的解空间
二、显式约束与隐式约束
用回溯法求解，它的解一般要求满足一组综合约束条件，这些 约束条件分为以下两类：
显式约束：限定每个xi只从一个给定的集合Si上取值。 为了用回溯法求解一个具有n个输入的问题，一般情况下， 将 其 可 能 解 表 示 为 满 足 某 个 约 束 条 件 的 等 长 向 量 X=(x1, x2, …, xn)，其中分量xi (1≤i≤n)的取值范围是某个有限集合 Si={ai1, ai2, …, aimi}，所有可能的解向量构成了问题的解空间。
第8章 回溯法
8.1 概 述 8.2 图问题中的回溯法 8.3 组合问题中的回溯法 8.4 实验项目——0/1背包问题
2021
1
8.1 概 述
8.1.1 问题的解空间 8.1.2 回溯法的设计思想 8.1.3 回溯法的求解过程 8.1.4 回溯法的算法描述 8.1.5 回溯法的时空性能
2021
2
8.1.1 问题的解空间
5 7 10 12 15 17 21 23 26 28 31 33 37 39 42 44 47 49 53 55 58 60 63 65
图8.1.1-4 n=4的TSP问题的解空间树
2021
4 34 2 2 3 4 3 4 13 1 4 24 12 12 3 3 12 1 5 7 10 12 15 17 21 23 26 28 31 33 37 39 42 44 47 49 53 55 58 60 63 65
解向量：由根结点到叶结点的路径所定义
图8.1.1-3 n=4的八皇后问题解空间树
2021
11
8.1.1 问题的解空间
对于n=4的TSP问题，其解空间树如图8.1.1-4所示，树中 的24个叶子结点分别代表该问题的24个可能解，例如结点5代 表一个可能解，路径为1→2→3→4→1，长度为各边代价之和。
1
1
4
2
3
2
18
34
50
Hale Waihona Puke 2 341 341 24
1 23
3
8
13
19 24
29 35
一、解空间概述 复杂问题常常有很多的可能解，这些可能解构成了
问题的解空间。
解空间也就是进行穷举的搜索空间，所以，解空间中 应该包括所有的可能解。
确定正确的解空间很重要，如果没有确定正确的解空 间就开始搜索，可能会增加搜索很多无用解，或者根本 就搜索不到正确的解。
2021
3
8.1.1 问题的解空间
例如：桌子上有6根火柴棒，要求以这6根火柴棒为边搭建4 个等边三角形。
{ ( ), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3) }
（2）可能解由一个等长向量{x1, x2, …, xn}组成，其中 xi=1(1≤i≤n)表示物品i装入背包，xi=0表示物品i没有装入背包， 当n=3时，其解空间是：
{(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) }
(a) 二维搜索空间无解
(b) 三维搜索空间的解
图8.1.1-1 错误的解空间将不能搜索到正确答案
2021
4
8.1.1 问题的解空间
对于任何一个问题，可能解的表示方式和它相应的解释隐 含了解空间及其大小。
例如，对于有n个物品的0/1背包问题，其可能解的表示方 式可以有以下两种：
（1）可能解由一个不等长向量组成，当物品i(1≤i≤n)装入背包 时，解向量中包含分量i，否则，解向量中不包含分量i，当n=3 时，其解空间是：
4皇后问题的解空间树
1
2
18
1
2
3
4 34
2 34
1 34
1 24
50 1 23
3
8
13
19
24
29 35
40
45
51
56
61
3 4 2 4 3 2 3 4 1 4 1 32 4 1 4 1 2 3 21 3 1 2
4 6 9 11 14 16 20 22 25 27 30 32 36 38 41 43 46 48 52 54 57 59 62 64