| 基于最小代价和生成树的算法研究 |
| |
| 引用本文： | 吴龙树,王勤. 基于最小代价和生成树的算法研究[J]. 微计算机信息, 2010, 0(12) |
| |
| 作者姓名： | 吴龙树 王勤 |
| |
| 作者单位： | 中国计量学院理学院; |
| |
| 基金项目： | 国家自然科学基金(No.10601051); 浙江省自然科学基金项目资助(No.Y6090472) |
| |
| 摘 要： | 最小生成树问题是一类经典的组合优化问题,已有许多快速有效的算法。但是在实际中更多存在这样的网络,除边有权值外,结点也有权值,并且结点的权值有多种情况,这就产生了基于代价和最小的生成树问题。根据结点权值的取值情况,对几种最小代价和生成树问题进行分类和求解,得到了一些有价值的性质和算法,有一定的实际应用背景。
|
| 关 键 词： | 生成树 组合优化 多项式时间算法 |
Research on Algorithms for Minimum Cost Spanning Trees |
| |
| WU Long-shu WANG Qin. Research on Algorithms for Minimum Cost Spanning Trees[J]. Control & Automation, 2010, 0(12) |
| |
| Authors: | WU Long-shu WANG Qin |
| |
| Affiliation: | WU Long-shu WANG Qin(College of Science,China Jiliang University,Hangzhou 310018,China) |
| |
| Abstract: | The minimum spanning tree problem is a classic combinatorial optimization problem and there exist many efficient algorithms to solve it.But in real network,the vertices as well as the edges may have costs,and there are many cases of the vertex weights.The minimum cost spanning tree problem with practical application background is studied in this paper.And some valuable properties and methods are presented for several kinds of minimum cost spanning tree problem based on different values of the vertex weights... |
| |
| Keywords: | Spanning tree Combinatorial optimization Polynomial time algorithm |
| 本文献已被 CNKI 等数据库收录！ |
|
