| 基于动态状态树的回溯算法 |
| |
| 引用本文： | 任小康,吴尚智,苟平章.基于动态状态树的回溯算法[J].计算机工程与设计,2007,28(4):755-756,759. |
| |
| 作者姓名： | 任小康 吴尚智 苟平章 |
| |
| 作者单位： | 西北师范大学数学与信息科学学院,甘肃兰州730070 |
| |
| 摘 要： | 介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法.以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用.
|
| 关 键 词： | 背包问题 状态空间 回溯 算法 树 动态 状态树 回溯算法 tree state space dynamic algorithm 应用 时间 线性规划问题 求解 树方法 状态空间树 算法设计 阐述 背包问题 |
| 文章编号： | 1000-7024（2007）04-0755-02 |
| 修稿时间： | 2006-06-13 |
Backtracking algorithm of dynamic state space tree |
| |
| REN Xiao-kang,WU Shang-zhi,GOU Ping-zhang.Backtracking algorithm of dynamic state space tree[J].Computer Engineering and Design,2007,28(4):755-756,759. |
| |
| Authors: | REN Xiao-kang WU Shang-zhi GOU Ping-zhang |
| |
| Affiliation: | College of Mathematics and information Science, Northwest Normal University, Lanzhou 730070, China |
| |
| Abstract: | 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. |
| |
| Keywords: | knapsack problem state space backtracking algorithm tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
