回溯法与分枝限界法的分析与比较

杨超 何书前 郑志群 石春

摘要：主要对回溯法与分枝限界法进行了分析与研究。首先介绍了两种算法的基本概念，引出它们的基本解题思想与过程。然后运用0-1背包问题分别对回溯法，队列式分枝界限法和优先队列式分枝界限法进行详细的分析与说明。进一步总结算法的异同，研究发现回溯法解决问题时对内存空间的要求更低，而分枝限界法解决问题时需要的时间更短。

关键词：回溯法；分枝限界法；0-1背包问题

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）11-0044-03

Analysis and Comparison of Backtracking and Branch-and-bound Methods

YANG Chao ， HE Shu-qian， ZHENG Zhi-qun ，SHI Chun*

（School of Information Science and Technology， Hainan Normal University， Haikou 571158，China）

Abstract：This paper mainly analyzes and studies the backtracking and the branch-and-bound method. First， the basic concepts of the two algorithms are introduced， and their basic idea and process of solving the problem are introduced. Then the 0-1 knapsack problem is used to analyze and explain the backtracking method， the queue branch boundary method and the priority queue branch and boundary method in detail. By further summarizing the similarities and differences of the algorithm， it is found that the memory space requirement is lower when the backtracking method solves the problem， while the branch-and-bound method takes shorter time to solve the problem.

Key words： backtracking； branch and bound method； 0-1 knapsack problem

1 回溯法与分枝限界法

1.1 回溯法

回溯法指在一个解空间树中（树中包括问题的所有解），依照深度优先搜索的方法，从根结点出发搜索解空间树，得出问题所有解的算法[1]。算法对解空间树的某一点进行搜索时，应判断这一结点是否含有这个问题的解。如果不包含，则跳过对该结点为根的子树的搜索，逐层向其父节点回溯；否则，进入该子树，继续按深度优先策略搜索[2]。这种以深度优先方式搜索问题结点的算法称为回溯法。

1.2分枝界限法

分枝限界法指在一个解空间树中（树中包括问题的所有解），依照广度优先搜索或最小耗费优先搜索的方法[3]，对根结点的所有分枝结点进行搜索，得出根结点所有相邻结点，建立活结点表，对表中结点进行广度搜索或最小耗费得出最优解的算法。根据搜索方式的差异，分枝限界法分为两种。广度优先搜索对每个结点的所有分枝结点进行从左到右的搜索，搜索出所有可行解，通过比较他们的限界函数得出最优解。这种解决问题的方法称为队列式分枝限界法。最小耗费搜索需要计算每一个活结点的限界函数，依据函数值选择一个最好的结点成为扩展结点，使搜索最优解变得快捷。这种解决问题的方法称为优先队列式分枝限界法。

2 回溯法与分枝限界法基本解题思想与过程

2.1回溯法求解问题

如图1所示，利用回溯法对问题进行求解时，应先确定其解空间并保证解空间中至少含有一个解。为了使得回溯法搜索解空间时变得方便，要运用子集树和排列树把解空间组织起来进行深度优先搜索得到问题的所有解。下图讲述了回溯法如何对解空间树进行深度优先搜索：

如图2所示，回溯法从根结点出发，以深度优先方式搜索整个解空间[4]。在根结点处向纵深方向搜索一个新的结点，若这个新结点可以再向纵深方向搜索，则这个新结点成为活结点，即为扩展结点。反之，当前结点成为死结点。此时应回溯，移动至其父结点，使之成为当前的扩展结点。当回溯至根结点且所有结点都被标记时即搜索结束。

2.2分枝界限法求解问题

分枝限界法与回溯法类似，区别在于对于解空间树的搜索方式上的不同和搜索出的结果形式不同。分枝限界发采用的是广度优先或最小耗费优先搜索的方式，得出的结果一般是最優的解。

设有活结点[Ni]，有四个子孩子。我们可以通过设计限界函数来删除两个不必要的孩子结点。如下图所示：

图4所示，分枝限界法通过设置合理的限界函数来对解空间树进行剪枝处理，使分枝限界法搜索效率提高；也可以通过限界函数来判定最优解。

在对解空间树进行搜索时候，根据分枝限界法搜索方式的不同，可以制定不同的活结点表。队列式分枝限界法的活结点表中起始只有根结点，表中结点按照队列顺序出表，每个活结点出表后需要将它的子结点按从左到右的顺序进入表中，若子结点为叶子结点，则构成一个可行解，可以不用入表，当活结点表为空，算法结束。优先队列式分枝限界法建立的活结点表的不同之处在于，出表结点的顺序是通过限界函数的大小来决定。

分枝限界法中每个结点都保存了从开始结点到这个结点的路径或者是这个结点的双亲结点指针。因为分枝限界法对结点的处理是跳跃式的，只有这样才能在搜索到可行解时得到相对应的解向量。

3 用回溯法与分枝限界法求解0-1背包问题

3.1 问题描述

设n件物品的重量分别为[w1、w2、w3、…、wn]，用数组w[1..n]表示，物品的价值分别为[v1、v2、v3、…、vn]，用数组v[1..n]表示，求一个负重不超过W的背包最多可以装多少价值的物品。（n=3； W=30；w=（16，15，15）；v=（45，25，25））

3.2 问题分析

由题可知，以背包里物品价值和重量为状态，开始状态是背包里的价值和重量都为空，背包放入物体重量不超过30可以引出2个状态，又根据这些状态引出其他状态，这些状态和它们的关系构造了问题的解空间。

3.3 用回溯法解0-1背包问题

回溯法通过对解空间的组织得出解空间树，按照深度优先搜索解空间树，得出所有可行解，通过比较各个可行解背包里物品价值来得到最优解。如下图所示：

图5所示，w代表背包里的重量；v代表背包里物品的总价值；连线上的0代表下一个物体不放入背包，1代表下一个物体放入背包；圆圈里的字母代表回溯法搜索解空间树结点的顺序，按照字母表排序。由字母顺序可以看到，回溯法搜索解空间树时，优先向纵深方向搜索，每搜索到一个可扩展结点时将结点进行入栈操作，当搜索到的结点无法扩展时，对结点进行出栈操作，回溯到它的父结点继续向纵深搜索，直到回溯到根结点且根结点也无法扩展时算法才结束。此题回溯法搜索可行解过程如下：

首先由根結点A入栈；纵深搜索到B，B入栈；纵深搜索到C，由于C结点超重所以无法进行扩展，回溯到B；纵深搜索到D；纵深搜索到E，E超重；回溯到D；纵深搜索到F，F为叶子节点，得出一个可行解；回溯到D，D无法再扩展，回溯到B；B也无法扩展，回溯到A；纵深搜索到G；纵深搜索到H；纵深搜索到I，可行解；回溯到H；纵深搜索到J，可行解；回溯到H；回溯到G；纵深搜索到K；纵深搜索到L，可行解；回溯到K；纵深搜索到M，可行解；回溯到K；回溯到G；回溯到A，根结点A无法扩展，算法结束。

我们可以看到，这个问题一共有5个可行解，结点I所代表的可行解v最大，所以解出来当背包物品重量为30时，价值为50时的解为此题最优解。

3.4 用队列式分枝限界法解0-1背包问题

队列式分枝限界法通过对解空间的组织得出解空间树，按照广度优先搜索解空间树，得出可行解，通过比较各个可行解的限界函数ub得到最优解。图6为队列式分枝界限法解决0-1背包问题时的解空间树，树中结点内字母代表队列式分枝限界法搜索空间树时对各结点的访问顺序：

如图6所示，i表示解空间树的层，w表示重量，v表示价值 ，0-1背包问题各结点的限界函数ub设定方法如下：

设已装入总重量为e.w，已装入的总价值为e.v，物品k+1装入背包的部分重量为[wk+1]，物品k+1的单位价值为[vk+1]。

首先需要满足

[e.wi+e.wi+1<=W]

当下一个物品可以全部装入背包时，价值上界为：

[e.ub=e.v+j=i+1nv[j]]

当下一个物品不可全部装入背包时，价值上界为：

[e.ub=e.v+j=i+1kv[j]+wk+1*vk+1]

设队列FIFO[]， 此题队列式分枝限界法搜索可行解过程如下：

A进队，其ub=68，FIFO=[A]。

A出队，孩子结点B、C进队，B的ub=68，C的ub=50，FIFO=[B、C]。

B出队，因为D的w=31>30，舍弃该结点，E进队，其ub=68，FIFO=[C、E]。

C出队，F、G进队，F的ub=50，G的ub=25，FIFO=[E、F、G]。

E出队，因为右孩子H的w=31>30，舍弃该结点。得出左孩子I的ub=45，是一个可行解，暂时作为最大价值解maxv，解向量为（1、0、0）。FIFO=[F、G]。

F出队，得出左孩子J的ub=50>45，是一个可行解，暂时作为maxv，解向量为（0、1、1）。因为右孩子K的ub=25

G出队，得出左孩子L的ub=25，是一个可行解，解向量为（0、1、1）。因为右孩子M的ub=0

FIFO队列为空，算法结束。

maxv是结点I的ub，I的解向量为（0、1、1），w=30，v=50。所以当背包物品重量为30时，价值为50时的解为此题最优解。

3.5 用优先队列式分枝限界法解0-1背包问题

优先队列式分枝限界法通过对解空间的组织得出解空间树，按照最小耗费优先搜索解空间树，得出最优解。其限界函数ub的设定与队列式分枝限界法相同。下图为优先队列式分枝界限法解决0-1背包问题时的解空间树：

设队列FIFO[]， 此题优先队列式分枝限界法搜索可行解过程如下：

A进队，其ub=68，FIFO=[A]。

A出队，孩子结点B、C进队，B的ub=68，C的ub=50，B（ub）>C（ub）（B的ub大于C的ub），FIFO=[B、C]。

B出队，因为D的w=31>30，舍弃该结点，E进队，其ub=68，E（ub）>C（ub），FIFO=[E、C]。

E出队，右孩子F的w=31>30，舍弃该结点。左孩子G的ub=45，是一个可行解，暂时作为最大价值解maxv，解向量为（1、0、0）。FIFO=[C]。

C出队，左孩子H进队，其ub=50。由于右孩子的ub=25，小于maxv，舍弃该结点。 FIFO=[H]。

H出队，得出左孩子J的v=50>45，是一个可行解，暂时作为maxv，解向量为（0、1、1），因为右孩子K的ub=25

FIFO队列为空，算法结束。

maxv是结点J的ub，J的解向量为（0、1、1），w=30，v=50。所以当背包物品重量为30时，价值为50时的解为此题最优解。

4 总结

回溯法与分枝限界法都是将问题的解空间组织成为解空间树，在树上对问题的解进行搜索的算法，且两种算法都属于穷举法。回溯法运用深度优先搜索结点，堆栈存储结点，通常可以找出问题的所有解；分枝界限法运用的是广度优先或者是最小耗费优先搜索结点，队列或者优先队列存储结点，通常找出的是问题在某种意义上的最优解。相比与回溯法，分枝界限法对最优解的搜索效率会更高。但由于分枝限界法每个结点都需要存储路径或双亲结点，需要比较大的存储空间，所以在内存容量有限的情况下，回溯法对问题求解成功率会更大。

参考文献：

[1] 董鹏.吴艳群.张春民.应用回溯算法求解多枢纽选址问题[J]. 交通与计算机， 2004（8）.

[2] 胡金初. 计算机算法[M].北京：清华大学出版社#北京交通大学出版社，2009.

[3] 王春梅. 分支限界算法的研究与实现[J]. 现代电子技术，2011.

[4] 李春葆. 算法设计与分析[M]. 北京：清华大学出版社，2015.