| 求解度约束最小生成树的一种启发式方法 |
| |
| 引用本文： | 廖飞雄,马良.求解度约束最小生成树的一种启发式方法[J].上海理工大学学报(社会科学版),2007,29(2):142-144. |
| |
| 作者姓名： | 廖飞雄 马良 |
| |
| 作者单位： | 上海理工大学管理学院,上海200093 |
| |
| 基金项目： | 上海市重点学科建设项目 |
| |
| 摘 要： | 针对网络设计和优化中度约束最小生成树问题,提出了一种基于贪心思想的启发式算法求解度约束最小生成树.在最小生成树的基础上,将超过度约束的顶点降低度数使之满足度约束条件.经大量数据测试并与其他算法进行比较,表明了该算法的有效性和通用性.
|
| 关 键 词： | 度约束 生成树 启发式算法 |
| 修稿时间： | 6/6/2006 12:00:00 AM |
Heuristic algorithm for degree-constrained minimum spanning tree |
| |
| LIAO Fei-xiong,MA Liang.Heuristic algorithm for degree-constrained minimum spanning tree[J].Journal of University of Shanghai For Science and Technilogy(Social Science),2007,29(2):142-144. |
| |
| Authors: | LIAO Fei-xiong MA Liang |
| |
| Institution: | Business School, University of Shanghai for Science and Technology, Shanghai 200093, China |
| |
| Abstract: | For solving the problem of finding the degree-constrained minimum spanning tree(DCMST) in network design and optimization,a heuristic search method is proposed,in which based on minimum spanning tree,degrees of vertices over the constrained degrees are reduced to the required state.Series of numerical examples are tested and the results are compared with that of some other algorithms.Computational results show the effectiveness and generality of the method. |
| |
| Keywords: | degree-constrained spanning tree heuristic algorithm |
|
| 点击此处可从《上海理工大学学报(社会科学版)》浏览原始摘要信息 |
| 点击此处可从《上海理工大学学报(社会科学版)》下载免费的PDF全文 |
