基于动态状态树的回溯算法分析

摘要：

首先阐述作为算法设计基本策略之一的回溯算法以及状态空间树的概念，然后提出将两者相结合的求解问题的思路，说明结合了回溯算法的动态状态树在求解既没有最优子结构也没有贪心选择性质一类问题上的突出优点。而且，该结合算法的时间复杂度远小于静态状态树，一系列的特性都突出表现了动态状态树在回溯算法应用上的诸多优点。

关键词：回溯算法、背包问题、状态树

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2015-10-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共2页

页码：59-60