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

摘要

资源受限的最小赋权树形图问题(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(nm log2m) and the whole heuristic algorithm runs in O(nm2).Also, we give some example to illustrate how this new heuristic algorithm works.