文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 背包问题的最优并行算法
侵权投诉

背包问题的最优并行算法

分治法

1000-9825/2003/14(05)0891©2003 Journal of Software 软 件 学 报Vol.14, No.5背包问题的最优并行算法

李庆华+, 李肯立, 蒋盛益, 张 薇

(国家高性能计算中心(武汉),湖北 武汉 430074)

(华中科技大学 计算机科学与技术学院,湖北 武汉 430074)

An Optimal Parallel Algorithm for the Knapsack Problem

LI Qing-Hua+, LI Ken-Li, JIANG Sheng-Yi, ZHANG Wei

(National High Performance Computing Center (Wuhan), Wuhan 430074, China)

(School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China)+ Corresponding author: Phn: 86-27-87544471, Fax: 86-27-87544471, E-mail: liqh@263.net

doc.guandang.net

Received 2002-10-28; Accepted 2002-12-11

Li QH, Li KL, Jiang SY, Zhang W. An optimal parallel algorithm for the knapsack problem. Journal ofSoftware, 2003,14(5):891~896.Abstract:A new parallel algorithm for the knapsack problem is proposed, in which the method of divide andconquer is adopted. Based on an CREW-SIMD machine with shared memory, the proposed algorithm needsO(2n/4)1 ε processors, 0≤ε≤1, and O(2n/2) memory to find a solution for the n-element knapsack problem in O(2n/4

(2n/4)ε) time. The cost of the algorithm is O(2n/2), which is optimal and an improved result over the past researches.The wrong results in corresponding literatures are also pointed out in this paper.

Key words:

摘 要:knapsack problem; NP-complete; parallel algorithm; method of divide and conquer利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2n/4)1 ε个并行处理机单元,0≤ε≤1,O(2n/2)个存储单元,在O(2n/4(2n/4)ε)时间内求解n维背包问题,算法的成本为O(2n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.

关键词:背包问题;NP完全;并行算法;分治法

文献标识码: A中图法分类号:TP301

背包问题(也称子集和问题)可以描述如下:给定n个正整数W=(w1,w2,….,wn)和正整数M,要求寻找这样一个子集I {1,2,…,n},使得∑wi=M,i∈I.背包问题属于NP完全问题,直接的枚举搜索可能遍历问题的所有2n个解 Supported by the National Natural Science Foundation of China under Grant No.60273075 (国家自然科学基金); the NationalHigh-Tech Research and Development Plan of China under Grant No.863-306ZD-11-01-06 (国家高技术研究发展计划(863)); theNational High Performance Computing Foundation under Grant No.99313 (国家高性能计算基金)

第一作者简介: 李庆华(1940

第1页

你可能喜欢

  • 背包问题
  • 背包算法
  • 装箱问题
  • 遗传算法
  • 贪心算法
  • 并行计算
  • 关联规则算法
  • 回溯算法

热门文档

相关文档

  • 背包问题的最优并行算法

    如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 背包问题的最优并行算法 背包问题背包问题隐藏>> 1000-9825/2003/14(05...

  • 【论文】求解背包问题的并行混合遗传算法

    求解背包问题的并行混合遗传算法_专业资料。针对基本遗传算法在求解大规模问题时,...群体开始进化,并采用定期将各群体的最优个体输出给其他群体,使得最优个体共享,...

  • 背包问题无存储冲突的并行三表算法

    将求解背包问题著名的 二表算法的设计思想应用于三表搜索中, 利用分治策略和无存储冲突 的最优归并算法, 提出一种基于 ER EW SIM D 共享 存储模型的并行三表算法...

  • 【论文】基于采样和MIMD结构的背包问题并行算法

    基于采样和MIMD结构的背包问题并行算法_专业资料。背包问题属于著名的NP完全问题,在信息密码学和数论研究中有着极其重要的应用。在深入分析背包问题现有并行算法的基础...

  • _背包问题_算法设计及分析

    背包问题的最优并行算法 [J ] . [ 9 ] 刘西奎 ,李艳 , 许进 . 背包问题的遗传算法求解 [J ] . 华中科 [ 10 ] 虞安波 ,杨家本 . 多背包问题的...

  • 背包问题的二分网格算法

    ‘ 因此 , 〕 新算法的并行化可望为实际应 用中大规模背包问题的精确求解提供...而导致累积误差过大的现象 , 这种累积误差可使 最终解偏离 实际的精 确最优解...

  • 粒子群优化算法及其在背包问题中的应用

    问题,解决背包问题是解决组合优化所面临的问题之一,在现 实中有着广泛的应用背景,而粒子群算法作为群智能算法而言,它通过追随当前搜索到 的最优值来寻找全局最优...

  • 基于遗传算法求解01背包问题

    解决背包问题的算法有最优算法和启发式算法,最优算法包括穷举法、动态规划法、 ...超立方体_LO/1背包问题的并行算法〔J〕.西安电子科技大学学报,1995,22(3):...

  • 背包问题(1)

    年代首先进行了开创性的研究,利用贪婪算法求得 了 0-1 背包问题最优解的上界...模拟生物物理规律的并行近似算法不断涌现,例如遗传算法己经在 0/1 背包问题 上...

  • 0-1背包问题算法分析与研究

    最大的价值 2算法思想描述及其性能分析 21 常用算 法 .在对 背包 问题 的研...适于大规模并行:A ●遗传 算法 : 于大 规模 并行 ;适 不受 其搜 索空间 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email