0-1背包问题多重分枝-限界算法的改进

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

0-1背包问题多重分枝-限界算法的改进

李鸣山, 陈碧波

文章导航 > 武汉大学学报 ( 信息科学版) > 1995 > 20(4): 353-358

李鸣山, 陈碧波. 0-1背包问题多重分枝-限界算法的改进[J]. 武汉大学学报 ( 信息科学版), 1995, 20(4): 353-358.

引用本文:

李鸣山, 陈碧波. 0-1背包问题多重分枝-限界算法的改进[J]. 武汉大学学报 ( 信息科学版), 1995, 20(4): 353-358.

Li Mingshan, Chen Bibo. An Improvement on the Multi-Branch-and-Bound Algorithm for 0-1 Knapsack Problems[J]. Geomatics and Information Science of Wuhan University, 1995, 20(4): 353-358.

Citation:

Li Mingshan, Chen Bibo. An Improvement on the Multi-Branch-and-Bound Algorithm for 0-1 Knapsack Problems[J]. Geomatics and Information Science of Wuhan University, 1995, 20(4): 353-358.

0-1背包问题多重分枝-限界算法的改进

武汉测绘科技大学计算机科学与工程系, 武汉市珞喻路39号, 430070

作者简介:
李鸣山,男,58岁,副教授,现从事人工智能、算法理论研究。

中图分类号: O211.65;TP312PA

An Improvement on the Multi-Branch-and-Bound Algorithm for 0-1 Knapsack Problems

Dept of Computer Science and Engineering, WTUSM, 39 LuoyuRoad, Wuhan, China 1 430070

摘要: 对0-l背包问题多重分枝一限界算法^[1]作了改进。经改进的算法仅用一棵状态空间树描述问题的解空间。引入了虚拟背包的概念,简化了限界函数的计算。新的算法较大地提高了搜索最优解的效率。
- 整数规划 /
- 0-1背包 /
- 分枝-限界算法
Abstract: This paper has improved on the multi-branch-and-bound algorithm for 0-1 knapsack problems^[1].The method uses one state space tree to describe the solution space of the problem.A new concept,fictitious knapsack,is given to simplify counting the upper bound function.This improved algorithm can solve 0-1 knapsack problems with more than one knapsack efficiently.
- integer-programming /
- 0-1 knapsack /
- multi-branch-and-bound alogrithm

[1]	李爽, 李德仁, 程承旗, 陈波, 沈欣, 童晓冲. 空天网格化星间通视及路由路径规划算法 . 武汉大学学报 ( 信息科学版), 2021, 46(1): 50-57. doi: 10.13203/j.whugis20200234
[2]	李改肖, 吕程, 彭认灿, 董箭. 一种利用双侧凸包扩张模型的路径快速规划算法 . 武汉大学学报 ( 信息科学版), 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
[3]	赵青, 陈勇, 罗斌, 张良培. 一种融合行人预测信息的局部路径规划算法 . 武汉大学学报 ( 信息科学版), 2020, 45(5): 667-675. doi: 10.13203/j.whugis20200105
[4]	余必秀, 初秀民, 柳晨光, 张豪, 毛庆洲. 基于改进A算法的无人航道测量船路径规划方法 . 武汉大学学报 ( 信息科学版), 2019, 44(8): 1258-1264. doi: 10.13203/j.whugis20170239*
[5]	占伟伟, 王伟, 陈能成, 王超. 一种利用改进A*算法的无人机航迹规划 . 武汉大学学报 ( 信息科学版), 2015, 40(3): 315-320.
[6]	柯宏发, 何可, 陈永光. 运动目标的MGM(1,N)轨迹预测算法 . 武汉大学学报 ( 信息科学版), 2012, 37(6): 662-666.
[7]	涂志刚, 谢伟, 熊淑芬, 秦前清. 一种高精度的TV-L~1光流算法 . 武汉大学学报 ( 信息科学版), 2012, 37(4): 496-499.
[8]	刘耀林, 夏寅, 刘殿锋, 洪晓峰. 基于目标规划与模拟退火算法的土地利用分区优化方法 . 武汉大学学报 ( 信息科学版), 2012, 37(7): 762-765.
[9]	宋迎春, 惠沈盈, 刘杰, 林东方. 基于分枝定界算法的整数最小二乘估计 . 武汉大学学报 ( 信息科学版), 2011, 36(10): 1241-1245.
[10]	张小红, 李星星. 非差模糊度整数固定解PPP新方法及实验 . 武汉大学学报 ( 信息科学版), 2010, 35(6): 657-660.
[11]	曹江丽, 孙潮义. 多目标遗传算法在水下机器人路径规划中的应用 . 武汉大学学报 ( 信息科学版), 2010, 35(4): 441-445.
[12]	沈照庆, 舒宁, 陶建斌. 一种基于NPA的加权“1 V m”SVM高光谱影像分类算法 . 武汉大学学报 ( 信息科学版), 2009, 34(12): 1444-1447.
[13]	朱长青, 符浩军, 杨成松, 王奇胜. 基于整数小波变换的栅格数字地图数字水印算法 . 武汉大学学报 ( 信息科学版), 2009, 34(5): 619-621.
[14]	方志祥, 宋莺. 嵌入式环境基于实时交通信息的多层次路径规划算法 . 武汉大学学报 ( 信息科学版), 2008, 33(4): 397-401.
[15]	唐健, 史文中, 孟令奎. 基于遗传算法的时相关动态车辆路径规划模型 . 武汉大学学报 ( 信息科学版), 2008, 33(8): 875-879.
[16]	周扬眉, 刘经南, 李信. 评价GPS相位模糊度整数解正确性的严密方法 . 武汉大学学报 ( 信息科学版), 2004, 29(11): 1004-1007.
[17]	任超, 欧吉坤, 袁运斌. 一种用于GPS整周模糊度OTF求解的整数白化滤波改进算法 . 武汉大学学报 ( 信息科学版), 2004, 29(11): 960-963.
[18]	李鸣山, 郑海虹. 0-1背包问题的多重分枝-限界算法 . 武汉大学学报 ( 信息科学版), 1995, 20(1): 83-87.
[19]	马克斯·, 昆斯. 联邦德国乡村空间的新规划 . 武汉大学学报 ( 信息科学版), 1990, 15(4): 1-5.
[20]	刘艳芳. 乡镇规划制图的探讨 . 武汉大学学报 ( 信息科学版), 1988, 13(1): 62-70.

WeChat

点击查看大图

计量

文章访问数: 677
HTML全文浏览量: 43
PDF下载量: 191
被引次数: 0

0-1背包问题多重分枝-限界算法的改进

武汉测绘科技大学计算机科学与工程系, 武汉市珞喻路39号, 430070

作者简介:
李鸣山,男,58岁,副教授,现从事人工智能、算法理论研究。

收稿日期: 1995-05-06
刊出日期: 1995-04-05

中图分类号: O211.65;TP312PA

关键词:

分枝-限界算法

摘要: 对0-l背包问题多重分枝一限界算法^[1]作了改进。经改进的算法仅用一棵状态空间树描述问题的解空间。引入了虚拟背包的概念,简化了限界函数的计算。新的算法较大地提高了搜索最优解的效率。

English Abstract

李鸣山, 陈碧波. 0-1背包问题多重分枝-限界算法的改进[J]. 武汉大学学报 ( 信息科学版), 1995, 20(4): 353-358.

引用本文:

李鸣山, 陈碧波. 0-1背包问题多重分枝-限界算法的改进[J]. 武汉大学学报 ( 信息科学版), 1995, 20(4): 353-358.

Li Mingshan, Chen Bibo. An Improvement on the Multi-Branch-and-Bound Algorithm for 0-1 Knapsack Problems[J]. Geomatics and Information Science of Wuhan University, 1995, 20(4): 353-358.

Citation:

Li Mingshan, Chen Bibo. An Improvement on the Multi-Branch-and-Bound Algorithm for 0-1 Knapsack Problems[J]. Geomatics and Information Science of Wuhan University, 1995, 20(4): 353-358.

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

我要投稿

投稿攻略

联系我们

二维码