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

Backtracking algorithm of dynamic state space tree

作　　者：任小康[1] 吴尚智[1] 苟平章[1] 

机构地区：[1]西北师范大学数学与信息科学学院,甘肃兰州730070

出　　处：《计算机工程与设计》2007年第4期755-756,759,共3页Computer Engineering and Design

摘　　要：介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法。以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用。The knapsack problem and 0-1 knapsack problem are introduced, the backtracking algorithm （one of the basic methods of the computer algorithm design） and the concept of state space are described, a backtracking algorithm based on dynamic state space tree which is useful for resolving linear programming is proposed. Take 0-1 knapsack problem for example, in contrast to static state space tree algorithm, the new algorithm spends less times and it helps to extend the application of backtracking algorithm.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]