| 求解度约束最小生成树的快速近似算法 |
| |
| 引用本文： | 宋海洲. 求解度约束最小生成树的快速近似算法[J]. 系统工程学报, 2006, 21(3): 232-236 |
| |
| 作者姓名： | 宋海洲 |
| |
| 作者单位： | 华侨大学数学系,福建,泉州,362021 |
| |
| 基金项目： | 福建省自然科学基金计划资助项目(z0511028) |
| |
| 摘 要： | 针对带有度约束的最小生成树问题,给出了一种快速近似算法.首先给出了快速近似算法的核心思想:在不违反度约束和不形成圈的前提下,每次加入权最小的边.其次给出了实现快速近似算法的具体步骤,并且证明了该算法的计算时间复杂度是图的顶点数的多项式函数,证明了算法的有效性定理.大量的数值试验表明该近似算法性能良好.最后在此算法的基础上,给出了求解TSP问题的一种快速近似算法.
|
| 关 键 词： | 度约束 生成树 算法 旅行商问题 |
| 文章编号： | 1000-5781（2006）03-0232-05 |
| 收稿时间： | 2004-05-20 |
| 修稿时间： | 2004-05-202005-04-16 |
Fast approximation algorithm for the degree-constrained minimum spanning tree problem |
| |
| SONG Hai-zhou. Fast approximation algorithm for the degree-constrained minimum spanning tree problem[J]. Journal of Systems Engineering, 2006, 21(3): 232-236 |
| |
| Authors: | SONG Hai-zhou |
| |
| Affiliation: | Department of Mathematics, Huaoqiao University, Quanzhou 362021, China |
| |
| Abstract: | A fast approximation algorithm for the degree-constrained minimum spanning tree problem is proposed in this paper.First,the kernel ideal of the fast approximation algorithm is given as follows: An edge that possesses minimal weight is added if the added edge will not disobey degree-constraint and will not form a circle.Second,the concrete steps of the fast approximation algorithm are presented.Furthermore,it is proved that the time complexity of the algorithm is polynomial function of the number of vertex,and the validity theorem of the algorithm is proved.Many numerical tests show that the fast approximation algorithm has very good performance.Finally,a fast approximation algorithm for traveling salesman problems is given. |
| |
| Keywords: | degree-constrained spanning tree algorithm TSP |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
