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

详细信息    查看全文 | 推荐本文 |

英文篇名：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; 关键词：回溯法 ; 分枝限界法 ; 0-1背包问题 英文关键词：backtracking;;branch and bound method;;0-1 knapsack problem 中文刊名：DNZS 英文刊名：Computer Knowledge and Technology 机构：海南师范大学信息科学技术学院; 出版日期：2018-04-15 出版单位：电脑知识与技术 年：2018 期：v.14 基金：国家自然科学基金项目(No:61362016);; 海南省自然科学基金项目(No:617121);; 海南省高等学校教育教学改革研究项目(No:HNJG2014-33);; 海南省教育科学规划(No:QJY201710130,QJY13516015);; 中央电教馆全国信息技术课题(No:166233260) 语种：中文; 页：DNZS201811020 页数：3 CN：11 ISSN：34-1205/TP 分类号：50-52

摘要

主要对回溯法与分枝限界法进行了分析与研究。首先介绍了两种算法的基本概念,引出它们的基本解题思想与过程。然后运用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.

引文

[1]董鹏.吴艳群.张春民.应用回溯算法求解多枢纽选址问题[J].交通与计算机,2004(8).
    [2]胡金初.计算机算法[M].北京:清华大学出版社#北京交通大学出版社,2009.
    [3]王春梅.分支限界算法的研究与实现[J].现代电子技术,2011.
    [4]李春葆.算法设计与分析[M].北京:清华大学出版社,2015.