回溯算法.doc

第12章 回溯在许多实际问题中，我们都要面临在很多选择中做一些决策，但是没有足够的信息帮助我们做出好的决策。同时，在做出一个决策后，接下来又要在许多新的选择中做一个决策。经过一系列的决策后，才有可能得到问题的解。对于这样的问题，当无法利用前面介绍过的算法进行求解时，一个好的解决方法就是利用回溯算法。12.1 基本概念在详细介绍回溯法之前，我们先介绍树的概念。我们知道，树由一系列的节点构成，在本书中，我们对节点在树中的角色，给它以不同的称呼，如图12.1所示。椭圆形表示根节点，浅灰色的圆圈表示内部节点，深灰色的圆圈表示叶子节点。有了树的概念后，我们就可以方便地用树来描述回溯法。树的每个节点，有若干个分支，可以看作面临许多选择，从一个节点沿着某分支进入下一个节点，表示在做了一个决策后，到达一个新节点，即将又面临许多选择。类似上述过程，一直到达叶子节点。因此回溯法可以看作是从根节点出发，经过一系列的节点，到达一个个的叶子节点。从根节点到达某个叶子节点的路径可以看作问题的一个解，而叶子可以看作搜索的目标。回溯法就是搜索出所有的叶子节点，然后选择一个满足要求的叶子节点。回溯是一种简单而非常强大的求解问题的方法，它系统地在所有可能的选择中搜索问题的一个最优解。如果把做的决策序列用一个向量来表示，回溯法就是以深度优先的方式逐步确定的值，直到找到问题的解。回溯法尝试不同的决策序列，直到找到一个决策序列满足问题的目标。回溯通过穷举所有的决策序列保证解的正确性。当然，决策序列的多少，即解的多少极大地影响回溯法的效率。为了获得问题的解，我们从出发，逐步扩展部分解，通过尝试解元素的一个值，然后测试扩展出的是否还是一个部分解，如果是，则继续往下搜索，如果不是，则尝试的其他值，依次类推，直到找到问题的解。一般地，用回溯法求解问题的步骤如下1) 定义问题的解空间，这个解空间必须至少包含问题的一个最优解；令表示解元素的取值范围，则问题的解空间为，通常，这个解空间很大，因此搜索一个目标解的计算量常常是无法想象的。为了提高回溯法的效率，我们必须有效组织解空间。2) 组织解空间以便更容易地搜索问题的解，典型的解空间组织方式是一棵树或一个图；3) 用深度优先的方式搜索问题的解，并用限界函数来避免搜索一个无解的子空间。下面我们分析回溯算法中所涉及的一些关键概念。先介绍解空间的概念，任何时候，问题的解包括做一系列的决策，如果我们把决策序列用图画出来，它就像一棵树。前面我们已经介绍了树能够很好的描述回溯法的求解过程，因此，把问题的解空间组织成一棵树，把树的叶子当作解空间中的一个解，可以很方便的进行回溯搜索。这棵树，也常称为解空间树。有时问题是要从一个集合的所有子集中搜索一个集合，作为问题的解。有时从一个集合的排列中搜索一个排列，作为问题的解。回溯可以很方便地遍历一个集合的所有子集或所有的排列。当问题是需要求个元素的子集，以便达到某种优化目标时，我们可以把这个解空间组织成一棵子集树。一个有个元素的集合有多少个子集?如果每个的大小为，对每个，则有个子集。当很大时，解空间是非常巨大的。子集树的结构如图12.2所示。图12.2中，解元素的值对应第层节点的一个分支。 图12.2 子集树对于子集树，回溯法的伪代码如下 Backtrack(i)1 if in then Update(x)2 else3 for each do4 5 if and then6 Backtrack(i+1) 其中，表示搜索的层数，即假定已经搜索到部分解，通过尝试解元素的一个值，然后测试扩展出的是否还是一个部分解，这由约束条件和限界条件 和决定，后面将根据具体例子说明如何设计约束条件和限界条件。第1行判断是否到了叶子节点，如果是则Update(x)，即更新有关解的信息。第3行，对取值范围中的每个值，执行第4行后，在第5行判断是否满足约束条件和限界条件，如果满足，则回溯下一层。当问题是需要求个元素的一个排列，以便达到某种优化目标时，我们可以把这个解空间组织成一棵排列树。个元素的集合有多少个排列?建立一个含个元素的数组，的值是数组中下标从1到的一个元素并且之前从未出现过，对应排列中的第个元素，那么共有个排列，排列树的结构如图12.3所示。图12.3 排列树中，集合中的元素是数组的下标。图12.3 排列树事实上，对于排列树，可以采取下述回溯算法BacktrackPerm(i) 1 if in then Update(x) 2 else 3 for ji to n do 4 5 if and then 6 BacktrackPerm(i+1) 7 BacktrackPerm(i)算法中，假定已经搜索到部分解，通过尝试解元素的一个值，其中可取，由于排列中，为了保证每个元素不同，因此可以通过交换来实现。然后在第5行利用C(i)和B(i)来测试扩展出的是否还是一个部分解。从Backtrack(i)算法可以看出，回溯法事实上是一个递归算法，因此，我们可以利用更有效率的循环算法来实现，即迭代回溯算法，例如，对于子集树的递归算法，其相应的迭代回溯算法如下：IterateBacktrack()1 i 12 while i0 do3 while is not exhausted do4 next element in 5 if i=n then Update(x)6 else if and then i i+17 i i-1IterateBacktrack()算法中，搜索从第1层开始，第3行表示对的取值范围中的每个元素进行枚举，第4行中，令为中的下一个元素，第5行判断如果搜索到叶子节点，则Update(x)，否则如果满足约束条件和限界条件，则继续往下搜索。第7行进行回溯。 从上面的回溯算法可以看出，在每一层节点，能否往下搜索，取决于约束函数和限界函数。利用约束函数和限界函数来剪除无用的分支，集中搜索那些最有希望获得解的分支，是提高回溯算法搜索效率的关键。因此为了改进搜索的性能，利用回溯至少需要考虑1) 如何发掘约束函数；2) 对于求最大值（最小值）问题，怎样计算上界（下界），从而利用这个信息来构造限界函数；3) 如何利用约束函数和限界函数来剪除无用的分支。对于第1）点，约束函数一般可以从问题的描述中找到，对于问题中不容易发现的约束函数，经过仔细分析，也是比较容易寻找到的。对于第2）点，设计限界函数是需要技巧的。一般来说，对于求解最大值问题，我们计算当前节点的上界值。如果当前最大目标函数值不小于，那么剪掉该分支，否则继续。因为从根节点到叶子节点的目标函数值一定不大于，所以如果，那么它表明正在搜索的节点是无希望的(即死节点)，所以要剪掉当前节点。如图12.4所示类似地，对于求解最小值问题，我们计算当前节点的下界值。如果当前最大目标值不大于，那么剪掉该分支，否则继续。因为从根节点到叶子节点的目标值必须不小于，所以如果，那么它表明正在搜索的节点是无希望的，即死节点，所以要剪掉当前节点。如图12.4所示12.2 集装箱装载问题给定个集装箱，集装箱的重量为，以及一艘船，船的载重量为。集装箱装载问题是在不超过船的载重量的前提下装载尽可能多的集装箱。由于集装箱问题是从个集装箱里选择一部分集装箱，而对每个集装箱，可装上船，也可不装。假设解可以由向量表示，表示集装箱被装上船，表示集装箱不装上船。因此集装箱装载问题可以描述如下：由于解元素表示集装箱可装可不装，即，因此解空间的大小为，可以把解空间组织成一棵有个叶子的子集树。如图12.5所示。每个内部节点对应两个分支，1分支和0分支。如果是1分支，表示相应集装箱装上船。否则不装上船。图12.5令表示从根节点到第层节点为止装入船的重量，即部分解的重量，可计算如下 假设已经知道部分解，由于，则试探取值1，即从第层节点往1分支走的约束函数为 若，则停止搜索1分支，否则，继续搜索。此外，当试探取值0，显然不会违反约束，因此可以继续往下搜索。下面，我们给出回溯的递归算法如下BacktrackLoading(i)1 if in then 2 if cwbestw then 3 bestwcw4 else 5 if C(i) W then / C(i)= cw+ wi 6 cwcw+ wi7 BacktrackLoading(i+1)8 cwcw-wi9 BacktrackLoading(i+1)BacktrackLoading(i)算法中，第1行判断如果到了叶子节点，则表明已经找到一个解，如果该解的装载重量比当前最好的更大，则更新当前最好的重量。第4行表示，还没有搜到叶子节点，第5行判断试探走1分支，其约束函数值是否超过了船的载重量，如果没有，则继续往下搜索，并更新当前的装载重量，否则，进行剪支。第9行对0分支，无条件进行回溯。由于装载问题的子集树中叶子节点的数目为，因此BacktrackLoading(i)算法的时间复杂度为。例12.1 给定一个装载实例：，我们可以图示回溯的过程，如图12.6所示。初始化，首先调用BacktrackLoading(1)，因此执行第6行，调用BacktrackLoading(2)，不满足约束条件，因此停止搜索第1层节点的1分支及其下面层。然后调用BacktrackLoading(2)，调用BacktrackLoading(3)，调用BacktrackLoading(4)，不满足约束条件，因此停止搜索第3层节点的1分支及其下面层。然后调用BacktrackLoading(4)，这样可以得到一个解1, 0, 1, 0。图12.6回溯算法BacktrackLoading(i)没有利用限界函数，下面我们给出一个改进的回溯算法。其基本思想是在BacktrackLoading(i)的基础上利用限界函数其中，表示剩余集装箱的总重量，它可计算如下 若，则停止搜索第层及其下面的层，否则，继续搜索。其中，表示到目前为止所得到的最大重量。下面给出改进回溯法的伪代码如下ImprovedBacktrackLoading(i)1 if in then 2 if cwbestw then bestwcw3 else 4 rr-wi 5 if C(i) W then 6 cwcw+wi7 ImprovedBacktrackLoading(i+1)8 cwcw-wi9 if B(i)bestw then 10 ImprovedBacktrackLoading(i+1)11 rr+wiImprovedBacktrackLoading(i)算法与BacktrackLoading(i)算法不同的是在第9行，对于0分支，需要判断是否满足限界函数，以及增加估计下界的过程，因此整个时间复杂度与BacktrackLoading(i)算法相同。对例12.1，我们利用改进的回溯法进行求解，图解过程如图12.7所示。搜索到A节点，此时约束函数值为8，限界函数值为19，此时，试探装集装箱2，往1分支搜索的时候，违背约束条件，节点B被剪支。回溯回去，往0分支，可以搜索到节点D，此时往1分支走，会违背约束条件，因此节点E被剪支。从D节点往0分支走，得到一个解1, 0, 1, 0，Bestw=10。回溯到C节点，可以继续搜索到F节点，此时的解1, 0, 0, 1，Bestw=11。由于找到了更好的解，因此解被更新。回溯到根节点，往0分支走，由于G节点的限界函数值为11不会比当前最好的载重量Bestw=11大，因此节点G被剪支。通过利用限界函数，极大地提高了搜索的效率。图12.7上述两个回溯算法，只给出了最优装载重量的计算，为了构造最优解，我们必须在伪代码中添加保存解的过程，对上面的回溯算法稍加修改，就可以得到如下算法ImprovedBacktrackLoading1(i)1 if in then 2 if cwbestw then 3 bestwcw4 for j1 to n do5 bestxjxj6 else 7 rr-wi 8 if C(i) W then xi 19 cwcw+wi10 ImprovedBacktrackLoading1(i+1)11 cwcw-wi12 if B(i)bestw then xi 013 ImprovedBacktrackLoading1(i+1)14 rr+wiImprovedBacktrackLoading1(i)算法在第3行需要考虑保存最好的解，因此需要时间，因此ImprovedBacktrackLoading1(i)算法的时间复杂度为。12.3 0/1背包问题第6章已经介绍了0/1背包问题，并且给出了一个有效的动态规划算法。现在，我们给出0/1背包问题的回溯算法。由于每个物品可以装进背包，也可不装，令表示物品被装进背包，表示物品不装进背包，因此解可以由向量 表示，其中，解空间的大小为，因此解空间可用有个叶子节点的子集树来表示，如图12.5所示。解空间第层节点的分支可由的值决定。 令表示目前到第层已经装入背包的物品总重量，即部分解的重量，它可计算如下 假设已经知道部分解，由于，则试探取值1，则第层节点1分支的约束函数为 因此若，则停止搜索1分支，否则，继续搜索。如果仅用约束函数，我们已经能够写出回溯算法，但是效率不高，为了提高搜索的效率，我们引进限界函数其中，表示目前到第层节点已经装入背包的物品价值表示剩余物品的总价值若，则停止搜索第层的节点及其下面的层，否则，继续搜索。其中，表示目前所得到的最好价值。当时，则停止搜索，因此越小，越小，剪掉的分支就越多。我们是否可以剪掉更多的分支呢? 答案是可以，我们只要构造更小的即可。具体地说，我们可以通过构造更好的限界函数来实现。 首先，先将物品以单位重量价值递减的顺序进行排列考虑第层，背包的剩余容量为，用贪心算法把剩余的物品放进背包，直到碰到装不进背包的物品为止，即物品放不进去。因此 (12.1)按照第7章贪心算法的结论，上述剩余物品的价值已经是最优的，因为对剩余物品的装载不存在比上述贪心装载方案还优的方案。因此，由(12.1)式计算的已经最优，它的值比原始值小，因此可以剪掉更多的分支。详细地计算的伪代码如下r(i)1 rw W- cw2 b cv 3 while i +1n and wi+1 rw do4 rw rw-wi+15 b b+vi+16 ii+17 if i +1 n then b b+vi+1/wi+1rw8 return b下面，我们给出结合上述限界函数的回溯算法BacktrackKnapsack(i)1 if in then 2 if cvbestv then 3 bestvcv4 for j1 to n do5 bestxj xj6 else 7 if C(i) W then xi 18 cwcw+wi; cv cv+ vi9 BacktrackKnapsack(i+1)10 cwcw-wi; cvcv-vi11 if B(i)bestv then xi 012 BacktrackKnapsack(i+1) BacktrackKnapsack(i)算法除了更新当前价值cv外，其伪代码与ImprovedBacktrackLoading1(i)类似，时间复杂度的分析也类似，这里就不再说明。图12.8例12.2， 给定一个背包实例：。其单位重量价值比。按单位重量价值比排序可得一个新的实例： ，。 从图12.8可知，沿着子集树的左分支一直搜索到第3层的节点，由于该节点1分支的约束函数值为11，超过了背包的载重量，因此剪掉该分支。第3层节点的0分支总是可行的，因此我们可以搜索到一个解，其总价值为20，即到目前为止找到的最大价值。然后回溯到第2层节点的0分支，由于小于当前找到的最大价值20，因此，剪掉该分支。重复上述过程，我们就会发现，由于剪掉了大量的分支，计算效率得到了明显的提高。12.4 着色问题地图着色是图论中最经典的问题之一，其描述是给定一幅地图(平面图)，给地图上的国家着色，使得具有公共边界的任何一对国家有不同的颜色，问需要多少种颜色？ 上个世纪最著名问题是猜想所有平面图仅用四种颜色就能对平面图着色，使得相邻的区域有不同的颜色。对大多数地图，找到合法的着色方案是很容易的。对某些地图，要找到合法的着色方案却是相对困难的。四色猜想吸引了众多科学家的兴趣和热情，然而一直悬而未决，直到1976年，美国计算机科学家Appel和Haken借助计算机，通过枚举分析，证明了此猜想是成立的，即所有平面图仅用四种颜色就可着色。将国家看作一个顶点，如果两个国家相邻，则在两个国家之间引入一条边，这样地图着色问题就可以转化为顶点着色问题。如图12.9所示。 (a) (b)图12.9因而问题转化为需要多少种颜色来着色顶点使得相邻的顶点有不同的颜色。例如图12.9(a)和(b)只需要四种颜色就可以满足问题的要求。下面我们考虑更一般的着色问题：给定一个无向图，需要对图中的每个顶点用种颜色中的一种进行着色，使得相邻的两个顶点有不同的颜色。从问题的描述可知，相邻的顶点必须用不同的颜色，我们没有足够的信息来选择颜色，每个选择会得到新的选择子集。一个或多个选择序列可以得到一个解，也有可能得不到，因此着色问题可以用回溯算法来解决。对种颜色编号为，由于每个顶点可从种颜色中选择一种着色，如果图的顶点数为，则解空间的大小为种，解空间是非常巨大的。我们可以把解空间组织成一棵多叉树，如图12.10所示。与前面几个例子的二叉树还是有所不同，着色问题的解空间为一棵多叉树。由于着色问题的解空间太大，因此，寻找合适的剪支函数无疑会提高搜索的效率。然而，着色问题没有明显的约束函数。而且着色问题也不是最优化问题，它只要求找到一种可行的着色方案就可以了，限界函数在这里也不起作用。唯一可用的约束函数是相邻的两个顶点需要着不同的颜色。图12.10令顶点的颜色为，因此解向量为，同时，我们令数组表示顶点和顶点是否相邻，如果=1，表示顶点和顶点相邻，=0表示顶点和顶点不相邻。因此求解顶点着色问题的回溯算法如下BacktrackColoring(i)1if in then 2 sum sum+13else for j1 to m do4 xij5 if Ok(i) then BacktrackColoring(i+1) 其中约束函数Ok(i)的伪代码如下Ok(i)1 for j1 to i-1 do2 if wi, j=1 and xj=xi then return False3 return TrueBacktrackColoring(i)算法中，对每个内部节点的，其子节点的一种着色是否可行，需要判断子节点的着色与相邻的个顶点的着色是否相同，因此共需要，而整个解空间树共有个内部节点，因此，BacktrackColoring(i)算法的时间复杂度为。12.5 n皇后问题给定一个的棋盘，皇后问题就是在棋盘上放置个皇后，使得个皇后两两之间互不攻击。任何两个处于同一列、同一行、同一条对角线上的皇后都会互相攻击。图12.11给出了8个皇后的一个合法布局。解决皇后问题最自然的办法是从个位置中选个位置，但是这种枚举算法的解空间的大小为，解空间太大。如果令表示皇后的列位置，问题的解向量可以表示为，因为限制皇后在不同的行，对每个皇后，可从个列位置中选择一个，因此解空间的大小为。因而，解空间可以组织成一棵子集树。若进一步限制每个皇后在不同列，解空间大小可以从减少到，因而，解空间可以组织成一棵排列树。由此可见，不同的表示，其解空间的大小也不一样。下面考虑解空间用子集树来表示的情形。如图12.12所示。图中黑色节点是死节点，是考虑了约束函数得到的子集树。下面，我们进一步形式化约束函数。图12.12由于任意两个皇后不允许在同一行或在同一列或在同一对角线上。由于已经排除在同一行的情形，因此只考虑在同一列或在同一对角线上的条件。两个皇后在同一列的条件，比较容易判断。假设两个皇后被放在位置和，若它们在同一列当且仅当。从解析几何可知，两个皇后在同一条对角线上当且仅当它们所在的直线的斜率为1或者-1，即 或者将上述条件改写一下，可得 因此，我们的约束条件变为或者根据上述约束函数，用来判断两个皇后是否在同一列或同一行的程序如下Place(k)1 for j1 to k-1 do2 if or then3 return False4 return True程序Place(k)的输入为，表示当前要放置的是皇后，皇后能否放置在列，就要判断放置在的皇后是否与前面已经放置的皇后产生冲突。有了判断任意两个皇后产生冲突的方法后，我们就可以写出下列回溯算法BacktrackNqueens()1 x1 02 k 13 while k0 do4 while xkn-1 do5 xk xk +1 6 if Place(k) then 7 if k=n then NumSolNumSol +18 else8 k k+19 xk 010 k k-1BacktrackNqueens()算法中，第1至2行进行初始化，第5行表示皇后试着放下一列，第6行判断皇后是否与已经放置的前面个皇后是否冲突，如果没有冲突，则第7行测试皇后是否已经到了叶子节点，如果到叶子节点，则返回一个合法解，否则放置下一个皇后。第10行执行回溯。与前面介绍的递归回溯算法不同的是，BacktrackNqueens()算法是一个循环回溯算法，由于该算法避免了参数的反复传递以及中间值的保存，效率要比递归回溯高。因此，平时在设计回溯算法时，应该尽量采用循环的方式来实现。12.6 旅行商问题旅行商问题（TSP）是组合优化领域中的著名难题之一，也是计算复杂性理论、图论等许多理论中的一个经典问题。旅行商问题最早在20世纪20年代由著名数学家兼经济学家Karl Menger提出。问题的一般描述为：旅行商从驻地出发，经过每个所要访问的城市一次且只经过一次，并最终返回驻地。问如何安排旅行的路线才能使旅行的总路程最短。旅行商问题在军事、通信、电路板的设计、大规模集成电路、基因排序等领域具有广泛的应用。其形式化的描述如下给定一个完全无向带权图，其每一边有一非负整数权值（或代价）。目的是要找出G的一条经过每个顶点一次且仅经过一次的回路，即汉密尔顿回路，使回路的总权值最小。即 图12.13给出了一个旅行商实例。其中回路有(1，2，4，3，1)，(1，4，2，3，1)，(1，3，2，4，1)等，其中(1，3，2，4，1)的代价为25，为最优回路。既然回路是包括所有顶点的环， 我们可以选择任意一个顶点为起点(该顶点也是终点)。 假设将个顶点编号为，并选择顶点1 为起点和终点，则每个回路可以被描述成顶点序列 ，顶点序列为顶点的一个排列，因此解空间的大小为，而且解空间可以组织成一棵排列树，如图12.14所示。其中，第1层节点有3个分支，分别是选择顶点2，3，4。 图12.14 图12.14中，每条从根到叶子节点的路径定义一条路线。解空间大小为3!。令表示从顶点到顶点的权值或代价，若，表示顶点和顶点之间没有边。因此，我们马上得到一个很自然的约束条件。如果当前顶点与当前路径中的末端点没有边相连，即，则不必搜索顶点所在的分支。否则继续。当然，这个约束函数不是很有效，假如是一个完全图，则该约束函数没有什么用。而解空间很大，因此我们必须构造有效的限界函数。令到第层为止所构造路径的权和为假设已经知道部分解，则从第层节点选择顶点往下走的限界函数为 若，则停止搜索分支及其下面的层，否则继续搜索。其中，表示目前为止找到的最佳回路的权和。有了限界函数，我们可以写出下列回溯算法BacktrackTSP(i)1 if i= n then 2 if wxn-1, xn and wxn,1 then3 if cw+ wxn-1, xn+wxn,1bestw then4 bestwcw+wxn-1, xn+ wxn,15 for j 1 to n do6 bestxj xj 7 else for j i to n-1 do8 if wxi-1, xj and cw+ wxi-1, xj n then 2 if ff1 then f2if2i-1+txj, 29 else f2if1+txj, 210 f f + f2i11 if f n then 2 if hbesth then3 besthh4 for j 1 to n do5 bestxj xj 6 else for j i to n do7 xi xj 8 h cut(xi)9 if hbesth then10 BacktrackCutting(i +1)11 xi xj 上述算法的剪支过程非常简单，如果能设计出更好的剪支函数，例如考虑当前的浪费空间，则可以得到更有效的算法。此外，切割的过程是对于当前考虑的矩形，我们寻找一个可行的位置，如果我们考虑当前最左下解的位置，来寻找一个可切割的矩形，效果是否可以更好呢？回溯的过程是否需要修改，读者可以思考，见习题12.15。12.9 小结本章内容主要参考了文献7, 16。前面我们介绍了回溯算法的经典应用，事实上，回溯算法还大量应用在游戏问题中，例如典型的迷宫问题等，它也是第14章启发式搜索的基础，这里我们就不再详细介绍。回溯法不仅可以解决最优化问题，还可以用来解决判定问题。对于求解最优化问题，回溯法利用约束函数和限界函