引用本文:杨子兰[1] 、朱娟萍[2] 、李睿[1].资源受限最小赋权树形图的一种贪婪分解启发式算法[J].西南师范大学学报(自然科学版),2017,42(8):
【打印本页】   【HTML】   【下载PDF全文】   查看/发表评论  【EndNote】   【RefMan】   【BibTex】
←前一篇|后一篇→ 过刊浏览    高级检索
本文已被:浏览 37次   下载   
分享到: 微信 更多
资源受限最小赋权树形图的一种贪婪分解启发式算法
杨子兰[1] 、朱娟萍[2] 、李睿[1]
作者单位
杨子兰[1] 、朱娟萍[2] 、李睿[1] 云南大学 旅游文化学院,云南 丽江,674199 云南大学 数学系,昆明,650091 
摘要:
资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.
关键词:  受限资源  树形图  背包问题  分解  贪婪算法  启发式算法
DOI:10.13718/j.cnki.xsxb.2017.08.004
分类号:O157.6
基金项目:
On New Heuristic Greedy Decomposition Algorithm for Resource Constrained Minimum Weight Arborescence Problem
YANG Zi-lan[1],ZHU Juan-ping[2],LI Rui[1]
Abstract:
The resource constrained minimum weight arborescence problem (RMWA) is NP-Hard.In this paper, a new heuristic greedy decomposition algorithm has been presented for this problem.By decomposing the objective function and the constraints, the RMWA model is decomposed into a minimum weight arborescence problem and special independent knapsack problems.A greedy algorithm is designed for solving these special knapsack problems, and the adjustment of the solution is followed.The greedy algorithm runs in time O(nm log2m) and the whole heuristic algorithm runs in O(nm2).Also, we give some example to illustrate how this new heuristic algorithm works.
Key words:  constrained resource  arborescence  knapsack problem  decomposition  greedy algorithm  heuristic algorithm
手机扫一扫看