求解度约束最小生成树问题的新算法

doi:10.3778/j.issn.1002-8331.2010.36.011

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (36): 40-42.DOI: 10.3778/j.issn.1002-8331.2010.36.011

求解度约束最小生成树问题的新算法

孙小军¹，刘三阳²，王志强³

1.宝鸡文理学院数学系，陕西宝鸡 721013
2.西安电子科技大学理学院，西安 710071
3.总装备部驻天水地区军事代表室，陕西宝鸡 721006

收稿日期:2009-08-19 修回日期:2009-10-09 出版日期:2010-12-21 发布日期:2010-12-21
通讯作者: 孙小军

New algorithm for solving degree constrained minimum spanning tree problem

SUN Xiao-jun¹，LIU San-yang²，WANG Zhi-qiang³

1.Department of Mathematics，Baoji College of Arts & Science，Baoji，Shaanxi 721013，China
2.School of Science，Xidian University，Xi’an 710071，China
3.General Armament Department Military Representative Office in Tianshui Region，Baoji，Shaanxi 721006，China

Received:2009-08-19 Revised:2009-10-09 Online:2010-12-21 Published:2010-12-21
Contact: SUN Xiao-jun

摘要/Abstract

摘要： 针对网络设计和组合优化中的度约束最小生成树问题，基于第k最小生成树的求解算法，提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换，逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树，最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤，并证明了算法的正确性。最后通过仿真结果和一个运输实例，表明了该算法在解决度约束最小生成树问题中的有效性。

关键词: 度, 度约束, 最小生成树, 第k最小生成树, 最小k度生成树

Abstract: Regarding the characteristics of degree-constrained minimum spanning tree problem in network design and combinatorial optimization，a new algorithm for the the k-degree minimum spanning tree on a designated point is presented on the base of the k minimum spanning tree’s algorithm.This new algorithm is supposed to change the minimum spanning tree in the optimal and operable way，and gradually make the degree of the designated point to be closer to the i-degree minimum spanning tree and finally reach the k-degree minimum spanning tree in network G.The correctness of this algorithm is proved by the given specific steps.Finally，the simulation and a practical transportation example turn out that the new algorithm is effective in the degree constrained minimum spanning tree problem.

Key words: degree, degree-constrain, minimum spanning tree, the k minimum spanning tree, the k-degree minimum spanning tree

中图分类号:

TP301.6

孙小军¹，刘三阳²，王志强³. 求解度约束最小生成树问题的新算法[J]. 计算机工程与应用, 2010, 46(36): 40-42.

SUN Xiao-jun¹，LIU San-yang²，WANG Zhi-qiang³. New algorithm for solving degree constrained minimum spanning tree problem[J]. Computer Engineering and Applications, 2010, 46(36): 40-42.

[1]	张波，徐黎明，黄志伟，要小鹏. 梯度策略的多目标GANs帕累托最优解算法[J]. 计算机工程与应用, 2021, 57(9): 89-95.
[2]	张岐山，陈露露. 基于均衡接近度灰关联的Slope One算法[J]. 计算机工程与应用, 2021, 57(9): 96-102.
[3]	王永贵，李倩玉. 基于KNN-GBDT的混合协同过滤推荐算法[J]. 计算机工程与应用, 2021, 57(9): 103-108.
[4]	杨春霞，李欣栩，吴佳君，刘天宇. 基于注意力交互机制的层次网络情感分类[J]. 计算机工程与应用, 2021, 57(9): 134-139.
[5]	牟清萍，张莹，张东波，王新杰，杨知桥. 目标丢失判别机制的视觉跟踪算法及应用研究[J]. 计算机工程与应用, 2021, 57(9): 140-147.
[6]	王林，柴江云. 深度神经网络在多场景车辆属性识别中的研究[J]. 计算机工程与应用, 2021, 57(9): 162-167.
[7]	黄冬宜，杨兵，吴子豪，匡佳一，颜泽明. 用于全市蜂窝流量预测的时空全连接卷积网络[J]. 计算机工程与应用, 2021, 57(9): 168-175.
[8]	周伦钢，孙怡峰，王坤，吴疆，黄维贵，李炳龙. 目标多种多值属性的端端快速识别网络[J]. 计算机工程与应用, 2021, 57(9): 182-190.
[9]	张成，戴俊峰，熊闻心. 融合LeNet-5改进的扫描文档手写日期识别[J]. 计算机工程与应用, 2021, 57(9): 207-211.
[10]	张朕通，单玉刚，袁杰. 联合多尺度和注意力机制的遥感影像检测[J]. 计算机工程与应用, 2021, 57(9): 212-216.
[11]	武文杰，宋文爱，高雪梅，杨吉江，王青，黄丽萍，雷毅. 基于X线的成人OSA计算机辅助诊断综述[J]. 计算机工程与应用, 2021, 57(9): 1-8.
[12]	许昊，张凯，田英杰，种法广，王子超. 深度神经网络图像描述综述[J]. 计算机工程与应用, 2021, 57(9): 9-22.
[13]	冉蓉，徐兴华，邱少华，崔小鹏，欧阳斌. 基于深度卷积神经网络的裂纹检测方法综述[J]. 计算机工程与应用, 2021, 57(9): 23-35.
[14]	李晓筱，胡晓光，王梓强，杜卓群. 基于深度学习的实例分割研究进展[J]. 计算机工程与应用, 2021, 57(9): 60-67.
[15]	兰红，黄敏. 融合KNN优化的密度峰值和FCM聚类算法[J]. 计算机工程与应用, 2021, 57(9): 81-88.

求解度约束最小生成树问题的新算法

New algorithm for solving degree constrained minimum spanning tree problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics