J4 ›› 2006, Vol. 28 ›› Issue (9): 100-102.
• 论文 • 上一篇 下一篇
刘晓玲 李肯立 郑光勇
出版日期:
发布日期:
Online:
Published:
摘要：
背包问题属于著名的NP完全问题，在信息密码学和数论研究中有着极其重要的应用。在深入分析背包问题现有并行算法的基础上，本文提出了一种基于采样和MIMD结构的背包问题并行求解算法，并给出了算法性能的理论分析和在IBMP690超级计算机上的实验结果。实验结果表明，当背包实例的维数n≥40时，本算法的并行效率可达60％以上。因此，本并行算法具有较好的可扩展性，能应用于各种MIMD结构的并行机上有效地求解背包问题。
关键词: 背包问题 并行算法 采样 MIMD 二表算法
Abstract:
The knapsack problem is a famous NP-complete problem. It is very important in the research on cryptosystems and number theory. Based on the proposed p arallel algorithms for the knapsack problem, a new parallel algorithm by sampling for solving the knapsack problem based on MIMD supercomputers is propo sed in the paper. Then the performance is theoretically analyzed. Next the experimental results of the knapsack instances randomly generated are given on the IBM P690 supercomputer. The experimental results show the parallel efficiency can exceed 60% when solving the larger scale knapsack instances（n≥ ≥40）. Thus it is proved that the proposed parallel algorithm is scalable and effective on MIMD parallel supercomputers.
Key words: （knapsack problem, parallel algorithm, sampling, MIMD, two-list algorithm）
刘晓玲 李肯立 郑光勇. 基于采样和MIMD结构的背包问题并行算法[J]. J4, 2006, 28(9): 100-102.
0 / / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://joces.nudt.edu.cn/CN/
http://joces.nudt.edu.cn/CN/Y2006/V28/I9/100
