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

杨子兰,朱娟萍,李睿

doi:10.13718/j.cnki.xsxb.2017.08.004

西南师范大学学报(自然科学版)

留言板

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

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

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

杨子兰,朱娟萍,李睿. 资源受限最小赋权树形图的一种贪婪分解启发式算法[J]. 西南师范大学学报(自然科学版), 2017, 42(8). doi: 10.13718/j.cnki.xsxb.2017.08.004

引用本文:

杨子兰,朱娟萍,李睿. 资源受限最小赋权树形图的一种贪婪分解启发式算法[J]. 西南师范大学学报(自然科学版), 2017, 42(8). doi: 10.13718/j.cnki.xsxb.2017.08.004

YANG Zi-lan,ZHU Juan-ping,LI Rui. On New Heuristic Greedy Decomposition Algorithm for Resource Constrained Minimum Weight Arborescence Problem[J]. Journal of Southwest China Normal University(Natural Science Edition), 2017, 42(8). doi: 10.13718/j.cnki.xsxb.2017.08.004

Citation:

YANG Zi-lan,ZHU Juan-ping,LI Rui. On New Heuristic Greedy Decomposition Algorithm for Resource Constrained Minimum Weight Arborescence Problem[J]. Journal of Southwest China Normal University(Natural Science Edition), 2017, 42(8). doi: 10.13718/j.cnki.xsxb.2017.08.004

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

杨子兰,朱娟萍,李睿

云南大学旅游文化学院,云南丽江,674199 ; 云南大学数学系,昆明,650091

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

YANG Zi-lan,ZHU Juan-ping,LI Rui

摘要: 资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.
- 受限资源 /
- 树形图 /
- 背包问题 /
- 分解 /
- 贪婪算法 /
- 启发式算法
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.
- constrained resource；arborescence；knapsack problem；decomposition；greedy algorithm；heuristic algorithm /

计量

文章访问数: 1204
HTML全文浏览数: 628
PDF下载数: 69
施引文献: 0

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

杨子兰,朱娟萍,李睿

云南大学旅游文化学院,云南丽江,674199 ; 云南大学数学系,昆明,650091

关键词:

摘要: 资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.

English Abstract

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

云南大学旅游文化学院,云南丽江,674199 ; 云南大学数学系,昆明,650091

Keywords:

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.