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

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

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

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.