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

On New Heuristic Greedy Decomposition Algorithm for Resource Constrained Minimum Weight Arborescence Problem

作　　者：杨子兰[1] 朱娟萍[2] 李睿[1] 

机构地区：[1]云南大学旅游文化学院,云南丽江674199 [2]云南大学数学系,昆明650091

出　　处：《西南师范大学学报（自然科学版）》2017年第8期18-24,共7页Journal of Southwest China Normal University(Natural Science Edition)

基　　金：国家自然科学基金项目(11126355);云南省教育厅科学研究基金项目(2017ZDX270);云南大学旅游文化学院项目(2015XY08)

摘　　要：资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.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（nmlog2m）and the whole heuristic algorithm runs in O（nm2）.Also,we give some example to illustrate how this new heuristic algorithm works.

关 键 词：受限资源 树形图 背包问题 分解 贪婪算法 启发式算法 

分 类 号：O157.6[理学—数学]