收缩背包问题的并行分枝界限算法

来源 :计算机研究与发展 | 被引量 : 0次 | 上传用户：kantstop

【摘要】

：

收缩背包问题(collapsing knapsack problem，CKP)是0-1背包问题的变体，其中背包的容量为所装物品数量的非增函数，针对并行计算的需要，在对CKP问题分解的基础上，给出了求解每个子问

【作者】

：

陈国良吴明顾钧

【机构】

：

中国科学技术大学计算机科学与技术系,香港科技大学

【出处】

：

计算机研究与发展

【发表日期】

：

2001年6期

【关键词】

：

收缩背包问题并行分枝界限算法计算机 NP问题 CKP branch and bound parallel algorithm Dawning-1000

【基金项目】

：

国家重点基础研究发展计划(973计划)

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

收缩背包问题(collapsing knapsack problem，CKP)是0-1背包问题的变体，其中背包的容量为所装物品数量的非增函数，针对并行计算的需要，在对CKP问题分解的基础上，给出了求解每个子问题的分枝界限算法；提出了基于MIMD-DM的收缩背包问题的并行分枝界限算法；并在曙光1000上设计和实现了该算法，以消息传递方式来解决子算法最优解的播送问题，同时给出了子问题的求解顺序，讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响.

其他文献

赋强公证债权文书排斥诉权的范围分析

2008年《最高人民法院关于当事人对具有强制执行效力的公证债权文书的内容有争议提起诉讼人民法院是否受理的批复》（以下简称《批复》）明确了强制执行公证债权文书被法院裁定不

期刊

赋强公证诉权恢复不予执行

浅析新形势下如何加强国有企业廉洁文化建设

在国有企业的建设发展中,企业文化建设占据着非常重要的地位,在企业文化中,保障企业文化和企业建设发展朝着正确方向前进的,恰恰是企业廉洁文化,尤其是对于国有企业而言,廉洁

期刊

国有企业廉洁文化建设路径分析

中国价格改革的过去和对未来的展望

中国价格改革的过去和对未来的展望路南一、中国经济体制改革前的价格体制１９５３年以后，特别是在完成了对农业、手工业和资本主义工商业的社会主义改造以后，中国逐步走上以指令性计划

期刊

中国价格改革价格体制

我的同学杨振宁

冯友兰先生说：在人生成功的过程中，须具有三种因素：（1）天才：学问方面，天才成分占得多。有无发明与创作是不止以得多少分数、几年毕业所能达成的。（2）努力：道德方面，努力成分占得多。每个

期刊

杨振宁同学尽善尽美冯友兰成分成功天才分数

对高职高专公共英语教学改革的初探

剖析了高职高专英语教学滞后的现状,强调了公共英语课程教改的必要性,并就如何进行教改提出初步探索和建议。

期刊

英语教学外语能力分层教学复合型人才

国家与社会的和谐：社会治理的起点

本文回顾了关于“国家与社会”视角的三篇重要文献，在总结中国传统社会、西方社会的经验之后，提出要澄清国家与社会的关系与权力的转移变化，倡导国家与社会之间适合历史文化特点

期刊

国家社会社会治理

离子方程式的常见设错方式例析

一、利用产物违背事实设错例1下列反应的离子方程式正确的是（）。

期刊

离子方程式设错方式例析产物反应

职中生英语学习兴趣的激发策略

职中生因为普遍英语基础较差,加之缺乏高考的压力等原因往往丧失英语学习的兴趣。对此,教师可以通过营造浓郁的英语学习氛围、创造运用英语的条件、适当降低教学目标、充分利

期刊

职中英语兴趣策略

如何培养中学生的英语自主学习能力

该文从学习动机,学习策略,评价方式等三方面论述在英语教学中培养中学生英语自主学习能力的策略。

期刊

英语自主学习能力动机策略评价方式

重视员工思想教育构筑风险防控的坚固长城

本文根据自身丰富的银行管理工作经验，首先阐述了企业员工思想教育的必要性，同时深入分析银行基层员工思想教育存在的主要问题，并提出了切实可行的加强员工思想教育的关键策略，以

期刊

商业银行员工思想教育

收缩背包问题的并行分枝界限算法

与本文相关的学术论文