资源受限最小赋权树形图的一种贪婪分解启发式算法

发布时间：2018-06-25 02:56

  本文选题：受限资源 + 树形图　； 参考：《西南师范大学学报(自然科学版)》2017年08期

【摘要】：资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.
[Abstract]:The resource-constrained least weighted tree graph problem (RMWA) is NP-difficult. A new greedy decomposition heuristic algorithm is proposed for the RMWA problem. RMWA model is decomposed into a minimum weighted tree graph problem and n independent special knapsack problems by decomposing objective functions and constraints. For these n independent special knapsack problems, a greedy algorithm is designed to find its solution, whose time complexity is O (nmlog2m), and then adjusts the solution to satisfy the constraint condition of tree graph to obtain a feasible solution of the problem. The total complexity of the algorithm is O (nm2). Finally, an example is given to illustrate the greedy decomposition heuristic algorithm.
【作者单位】： 云南大学旅游文化学院;云南大学数学系;
【基金】：国家自然科学基金项目(11126355) 云南省教育厅科学研究基金项目(2017ZDX270) 云南大学旅游文化学院项目(2015XY08)
【分类号】：O157.6;TP301.6

【相似文献】

相关期刊论文 前10条

1 李诗珍;;配送中心订单分批拣货模型及种籽启发式算法[J];起重运输机械;2009年01期

2 王庆贞;赵雁;钟斌;王玉龙;;车辆优化调度算法研究初探[J];黑龙江科技信息;2010年03期

3 王乐善;_5良震;;求图的总体最佳2—划分的有效启发式算法[J];安徽大学学报(自然科学版);1983年02期

4 徐亦文;运输路径问题的一个新启发式算法[J];上海机械学院学报;1987年02期

5 郭耀煌,范莉莉;货运汽车调度的一种启发式算法[J];系统工程;1989年01期

6 陈驻民;羊英;;混流企业中基于瓶颈的启发式算法的应用[J];武汉理工大学学报(信息与管理工程版);2010年02期

7 郑攀;胡思继;张晨;;机门指派模型建立与启发式算法设计[J];系统工程学报;2011年01期

8 马磊;任成磊;韩定定;;模块度优化启发式算法应用[J];现代电子技术;2012年19期

9 黄干平,刘娟;解“时间表问题”的启发式算法[J];武汉大学学报(自然科学版);1996年01期

10 赵赫,杜端甫;TSP的邻域搜索算法的分析和改进[J];中国管理科学;1997年01期

相关会议论文 前10条

1 罗守成;唐国春;;二维集装箱问题的一个启发式算法[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

2 刘青松;孔云峰;党兰学;王震;;元启发式算法在校车路径规划中的应用[A];第七届全国地理学研究生学术年会论文摘要集[C];2012年

3 刘嘉敏;马广煜;黄有群;;基于组合的三维集装箱装入启发式算法的研究[A];全国第13届计算机辅助设计与图形学（CAD/CG）学术会议论文集[C];2004年

4 何正文;徐渝;;多模式项目支付进度问题的优化模型及启发式算法[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

5 赵文丹;汪定伟;郭小萍;王贵成;;网络广告资源优化问题研究[A];第二十九届中国控制会议论文集[C];2010年

6 杨士准;谢政;陈挚;熊李军;;k约束QoS问题的启发式算法[A];中国通信学会第六届学术年会论文集（下）[C];2009年

7 刘金朋;魏长江;;启发式算法求最短路径的一种高效率实现方法[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年

8 范敏;邹平;朱兴东;;一种启发式离散化算法及其Delphi实现[A];第二届中国智能计算大会论文集[C];2008年

9 王文瀚;杜斌;朱俊;贾树晋;;集成MILP与启发式的混合算法求解板坯设计问题[A];中国计量协会冶金分会2012年会暨能源计量与节能降耗经验交流会论文集[C];2012年

10 冯德鸿;唐加福;郭琦;李辉;;订货批量问题改进的相关策略启发式算法与仿真分析[A];2007系统仿真技术及其应用学术会议论文集[C];2007年

相关博士学位论文 前9条

1 李福清;交通规划中专用道设置问题建模和求解研究[D];广东工业大学;2016年

2 赖向京;原子团簇结构预测的现实途径—高性能启发式算法[D];华中科技大学;2012年

3 黎展滔;具有成组约束的柔性流水车间作业计划制定的启发式算法[D];广东工业大学;2012年

4 曹斌;生物启发式智能计算及其应用的研究[D];吉林大学;2012年

5 董兴业;启发式算法及其在同顺序流水作业问题中的应用[D];北京交通大学;2008年

6 古继兴;KOD多播技术与Steiner树启发式算法[D];上海交通大学;2007年

7 胡大伟;设施定位和车辆路线问题模型及其启发式算法研究[D];长安大学;2008年

8 杨玉珍;基于元启发式算法的带生产约束作业车间调度问题若干研究[D];华东理工大学;2014年

9 任志磊;组合优化问题的特化与泛化算法设计[D];大连理工大学;2013年

相关硕士学位论文 前10条

1 朱玺睿;氯氧镁板材生产线优化研究[D];东北林业大学;2015年

2 尹青山;绿色微数据中心与NGPON融合网络部署规划研究[D];大连海事大学;2015年

3 石闯;基于启发式算法的Ad Hoc网络QoS路由协议的研究与仿真[D];东北大学;2013年

4 张毅;启发式算法的自调参数方法研究[D];西安工程大学;2016年

5 周书橙;护士排班的启发式算法研究与排班管理系统的设计实现[D];北京交通大学;2016年

6 任平飞;基于启发式算法的云计算负载均衡问题研究[D];哈尔滨工业大学;2016年

7 戈丽娜（Galina Deeva）;配送过程中提货送货问题的静态动态方法的应用效果研究[D];哈尔滨工业大学;2016年

8 刘赛赛;基于增强学习的启发式和元启发式搜索的参数调优策略[D];电子科技大学;2016年

9 李鹏;定制衣柜零件分拣方式及效能分析[D];南京林业大学;2016年

10 刘志宏;合同组批系统中优化算法的研究[D];东北大学;2013年

，

本文编号：2064222