回溯法和分枝限界法的分析和比较,本论文可用于回溯法论文范文参考下载，回溯法相关论文写作参考研究。
回溯法论文参考文献：
摘 要：主要对回溯法与分枝限界法进行了分析与研究.首先介绍了两种算法的基本概念,引出它们的基本解题思想与过程.然后运用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点调整测量法和电机扭矩值法比较
摘 要： 滚切式定尺剪剪刃间隙调整的精确程度，直接影响剪刃的平行程度，剪切钢板时剪刃受力不均匀，剪刃间隙调整装置里面的上下楔铁自润滑滑板磨损不均。
基于利奇语义七分法来网络热词洪荒之力
摘 要：本文以利奇的语义七分法为理论基础，研究表明此词汇在2016年使用次数为历史最高，广泛应用于文化科学，文学，经济管理学等十种语境，并且在不。
语义七分法视角下幽默话语分析
摘 要：幽默一直以来都是言学家研究的热点问题，而幽默话语的形成离不开语义和语境。本文以Leech的语义七分法为理论框架，从美剧《破产姐妹》中选取。
基于分型转折点证券时间序列分段表示法
摘 要：证券时间序列是证券交易价格的一组观测数据，是一种有其自身显著的特点的时间序列，针对这些特点我们提出一种基于分形理论与K线图形特点的分段方。