| 一种求解背包问题的自适应算法 |
| |
| 引用本文： | 江华,谭新星,李祥.一种求解背包问题的自适应算法[J].计算机工程,2008,34(4):7-9. |
| |
| 作者姓名： | 江华 谭新星 李祥 |
| |
| 作者单位： | 贵州大学计算机理论与软件研究所,贵阳,550025;广东韶关学院计算机系,韶关,512005;广东韶关学院计算机系,韶关,512005;贵州大学计算机理论与软件研究所,贵阳,550025 |
| |
| 摘 要： | 针对二表算法和动态二表算法求解背包问题，提出一个并行自适应算法，能用 个处理机、 的时间、 的空间求解背包问题 ，根据处理机的数目以及存储器的容量来选择参数，充分利用已有的硬件资源，以求得最快的求解速度。实验结果证明了该算法的有效性。
|
| 关 键 词： | 背包问题 NP问题 并行算法 时间-存储器-处理机折中 |
| 文章编号： | 1000-3428（2008）04-0007-03 |
| 收稿时间： | 2007-05-21 |
| 修稿时间： | 2007年5月21日 |
Adaptive Algorithm for Solving Knapsack Problem |
| |
| JIANG Hua,TAN Xin-xing,LI Xiang.Adaptive Algorithm for Solving Knapsack Problem[J].Computer Engineering,2008,34(4):7-9. |
| |
| Authors: | JIANG Hua TAN Xin-xing LI Xiang |
| |
| Affiliation: | (1. Institute of Computer Theory and Software, Guizhou University, Guiyang 550025; 2. Department of Computer, Guangzhou Shaoguan University, Shaoguan 512005) |
| |
| Abstract: | Based on the two-list algorithm and the two-list four-table algorithm, this paper proposes parallel adaptive algorithm for solving the knapsack problem. It uses processors, time, and memory to solve the knapsack problem , whose parameter can be selected by numbers of processors and amounts of memory that can make full use of the existing hardware resources to find the fastest solution. Experimental results show that the algorithm is effective. |
| |
| Keywords: | knapsack problem NP problem parallel algorithm time-memory-processor tradeoff |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
