杨超 何书前 郑志群 石春

摘要：主要对回溯法与分枝限界法进行了分析与研究。首先介绍了两种算法的基本概念，引出它们的基本解题思想与过程。然后运用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]，对根结点的所有分枝结点进行搜索，得出根结点所有相邻结点，建立活结点表，对表中结点进行广度搜索或最小耗费得出最优解的算法。根据搜索方式的差异，分枝限界法分为两种。广度优先搜索对每个结点的所有分枝结点进行从左到右的搜索，搜索出所有可行解，通过比较他们的限界函数得出最优解。……