首页> 中文期刊> 《软件学报》 >背包问题的最优并行算法

背包问题的最优并行算法

         

摘要

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

著录项

  • 来源
    《软件学报》 |2003年第5期|891-896|共6页
  • 作者单位

    国家高性能计算中心;

    武汉;

    湖北;

    武汉;

    430074;

    华中科技大学;

    计算机科学与技术学院;

    湖北;

    武汉;

    430074;

    国家高性能计算中心;

    武汉;

    湖北;

    武汉;

    430074;

    华中科技大学;

    计算机科学与技术学院;

    湖北;

    武汉;

    430074;

    国家高性能计算中心;

    武汉;

    湖北;

    武汉;

    430074;

    华中科技大学;

    计算机科学与技术学院;

    湖北;

    武汉;

    430074;

    国家高性能计算中心;

    武汉;

    湖北;

    武汉;

    430074;

    华中科技大学;

    计算机科学与技术学院;

    湖北;

    武汉;

    430074;

  • 原文格式 PDF
  • 正文语种 chi
  • 中图分类 理论、方法;
  • 关键词

    背包问题; NP完全; 并行算法; 分治法;

相似文献

  • 中文文献
  • 外文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号