回溯法 - 下载本文

第8章 回溯法 ............................................................................................................................... 1 8.1 概 述 ................................................................................................................................... 1 8.1.1 问题的解空间树 ........................................................................................................... 1 8.1.2 回溯法的设计思想 ....................................................................................................... 2 8.1.3 回溯法的时间性能 ....................................................................................................... 3 8.1.4 一个简单的例子——素数环问题 ............................................................................... 4 8.2 图问题中的回溯法 ............................................................................................................... 5 8.2.1 图着色问题 ................................................................................................................... 5 8.2.2 哈密顿回路问题 ........................................................................................................... 8 8.3 组合问题中的回溯法 ......................................................................................................... 10 8.3.1 八皇后问题 ................................................................................................................. 10 8.3.2 批处理作业调度问题 ................................................................................................. 13 习题8 .......................................................................................................................................... 16

1

第8章 回溯法

教学重点 回溯法的设计思想;各种经典问题的回溯思想 教学难点 批处理作业调度问题的回溯算法

知识点

问题的解空间树

教学内容 回溯法的设计思想 和 回溯法的时间性能 教学目标 图着色问题

哈密顿回路问题 八皇后问题 批处理作业调度问题

教学要求

了解

理解 √ √ √

掌握 熟练掌握 √ √ √ √

8.1 概 述

回溯法(back track method)在包含问题的所有可能解的解空间树中,从根结点出发,按照深度优先的策略进行搜索,对于解空间树的某个结点,如果该结点满足问题的约束条件,则进入该子树继续进行搜索,否则将以该结点为根结点的子树进行剪枝。回溯法常常可以避免搜索所有的可能解,所以,适用于求解组合数较大的问题。

8.1.1 问题的解空间树

复杂问题常常有很多的可能解,这些可能解构成了问题的解空间(solution space),并且可能解的表示方式隐含了解空间及其大小。用回溯法求解一个具有n个输入的问题,一般情况下,将问题的可能解表示为满足某个约束条件的等长向量X=(x1, x2, ?, xn),其中分量xi(1≤i≤n)的取值范围是某个有限集合Si={ai,1, ai,2, ?, ai,ri},所有可能的解向量构成了问题的解空间。例如,对于有n个物品的0/1背包问题,其可能解由一个等长向量{x1, x2, ?, xn}组成,其中xi=1(1≤i≤n)表示物品i装入背包,xi=0表示物品i没有装入背包,则解空间由长度为n的0/1向量组成。当n=3时,其解空间是:

1

{(0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1) }

问题的解空间一般用解空间树(solution space tree,也称状态空间树)的方式组织,树的根结点位于第1层,表示搜索的初始状态,第2层的结点表示对解向量的第一个分量做出选择后到达的状态,第1层到第2层的边上标出对第一个分量选择的结果,依此类推,从树的根结点到叶子结点的路径就构成了解空间的一个可能解。

例如,对于n=3的0/1背包问题,其解空间树如图8.1所示,树中第i层与第i+1层(1≤i≤n)结点之间的边上给出了对物品i的选择结果,左子树表示该物品被装入了背包,右子树表示该物品没有被装入背包。树中的8个叶子结点分别代表该问题的8个可能解,例如结点8代表一个可能解(1, 0, 0)。

11 0 H 对物品1的选择 29

H 1 H 0 1 0 对物品2的选择

313 610 H 0 1 H 0 1 H 0 1 1 0 对物品3的选择 451181214 715H H H H H H H 图8.1 0/1背包问题的解空间树及其含义

8.1.2 回溯法的设计思想

回溯法从解空间树的根结点出发,按照深度优先策略搜索满足约束条件的解。在搜索至树中某结点时,先判断该结点对应的部分解是否满足约束条件,也就是判断该结点是否包含问题的(最优)解,如果肯定不包含,则跳过以该结点为根的子树,即所谓剪枝(pruning);否则,进入以该结点为根的子树,继续按照深度优先策略搜索。

需要强调的是,问题的解空间树是虚拟的,并不需要在算法运行时构造一棵真正的树结构。由于问题的解向量X=(x1, x2, ?, xn)中的每个分量xi(1≤i≤n)都属于一个有限集合Si={ai,1, ai,2, ?, ai,ri},因此,回溯法可以按某种顺序(例如字典序)依次考察笛卡儿积S1×S2×?×Sn中的元素。初始时,令解向量X为空,然后,从根结点出发,选择S1的第一个元素作为解向量X的第一个分量,即x1= a1,1,如果X=(x1)是问题的部分解,则继续扩展解向量X,选择S2的第一个元素作为解向量X的第2个分量;否则,选择S1的下一个元素作为解向量X的第一个分量,即x1= a1,2。依此类推,一般情况下,如果X=(x1, x2, ?, xi)是问题的部分解,则选择Si+1的第一个元素作为解向量X的第i+1个分量时,有下面三种情况:

(1)如果X=(x1, x2, ?, xi+1)是问题的最终解,则输出这个解。如果问题只希望得到一个解,则结束搜索,否则继续搜索其他解;

(2)如果X=(x1, x2, ?, xi+1)是问题的部分解,则继续构造解向量的下一个分量; (3)如果X=(x1, x2, ?, xi+1)既不是问题的部分解也不是问题的最终解,则存在下

2

面两种情况:

① 如果xi+1= ai+1,k不是集合Si+1的最后一个元素,则令xi+1= ai+1,k+1,即选择Si+1

的下一个元素作为解向量X的第i+1个分量;

② 如果xi+1= ai+1,k是集合Si+1的最后一个元素,就回溯到X=(x1, x2, ?, xi),选择Si的下一个元素作为解向量X的第i个分量,假设xi= ai,k,如果ai,k不是集合Si的最后一个元素,则令xi= ai,k+1;否则,就继续回溯到X=(x1, x2, ?, xi-1)。

例如,对于n=3的0/1背包问题,三个物品的重量为{20, 15, 10},价值为{20, 30, 25},背包容量为25,从图8.1所示的解空间树的根结点开始搜索,搜索过程如下:

(1)从结点1选择左子树到达结点2,由于选取了物品1,故在结点2处背包剩余容量是5,获得的价值为20;

(2)从结点2选择左子树到达结点3,由于结点3需要背包容量为15,而现在背包仅有容量5,因此结点3导致不可行解,对以结点3为根的子树实行剪枝;

(3)从结点3回溯到结点2,从结点2选择右子树到达结点6,结点6不需要背包容量,获得的价值仍为20;

(4)从结点6选择左子树到达结点7,由于结点7需要背包容量为10,而现在背包仅有容量5,因此结点7导致不可行解,对以结点7为根的子树实行剪枝;

(5)从结点7回溯到结点6,在结点6选择右子树到达叶子结点8,而结点8不需要容量,构成问题的一个可行解(1, 0, 0),背包获得价值20;

按此方式继续搜索,得到的搜索空间如图8.2所示。 10 1 H

92 H H 0 1 0 1

103 613 H H 1 0 0 不可行解 0 1 1 1187 14 1512H H H H 不可行解 价值=20 价值=55 价值=30 价值=25 价值=0

图8.2 0/1背包问题的搜索空间

8.1.3 回溯法的时间性能

一般情况下,在问题的解向量X=(x1, x2, ?, xn)中,分量xi (1≤i≤n)的取值范围为某

个有限集合Si={ai,1, ai,2, ?, ai,ri},因此,问题的解空间由笛卡儿积A=S1×S2×?×Sn构成,并且第1层的根结点有|S1|棵子树,则第2层共有|S1|个结点,第2层的每个结点有|S2|棵子树,则第3层共有|S1|×|S2|个结点,依此类推,第n+1层共有|S1|×|S2|×?×|Sn|个结点,他们都是叶子结点,代表问题的所有可能解。

回溯法实际上属于蛮力穷举法,当然不能指望它有很好的最坏时间复杂性,遍历具有指数阶个结点的解空间树,在最坏情况下,时间代价肯定为指数阶。然而,从本章介绍的几个算法来看,他们都有很好的平均时间性能。回溯法的有效性往往体现在当问题

3

规模n很大时,在搜索过程中对问题的解空间树实行大量剪枝。但是,对于具体的问题实例,很难预测回溯法的搜索行为,特别是很难估计出在搜索过程中所产生的结点数,这是分析回溯法的时间性能的主要困难。

8.1.4 一个简单的例子——素数环问题

1 【问题】把整数{1, 2, ?, 20}填写到一个环中,要求每个

整数只填写一次,并且相邻的两个整数之和是一个素数。例如,

2 4 图8.3所示就是整数{1, 2, 3, 4}对应的一个素数环。

3 【想法】这个素数环有20个位置,每个位置可以填写的

整数有1~20共20种可能,可以对每个位置从1开始进行试探,图8.3 一个素数环 约束条件是正在试探的数满足如下条件:

(1)与已经填写到素数环中的整数不重复; (2)与前面相邻的整数之和是一个素数;

(3)最后一个填写到素数环中的整数与第一个填写的整数之和是一个素数。 在填写第k个位置时,如果满足上述约束条件,则继续填写第k+1个位置;如果1~20个数都无法填写到第k个位置,则取消对第k个位置的填写,回溯到第k-1个位置。

【算法实现】设数组a[n]表示素数环,为了和C++语言的数组下标一致,素数环的位置为0~n-1,算法用C++语言描述如下:

void PrimeCircle(int n) //填写1~n共n个整数 {

int i, k;

for (i = 0; i < n; i++ ) //将数组a[n]初始化为0 a[i] = 0;

a[0] = 1; k = 1; //指定第0个位置填写1 while (k >=1) { a[k] = a[k]+1; while (a[k] <= n) if (Check(k) == 1) break; //位置k可以填写整数a[k] else a[k] = a[k] + 1; //试探下一个数 if (a[k] <= n && k == n - 1) { //求解完毕,输出解 for (i = 0; i < n; i++) cout<

4