| 约束最小权生成树的近似算法和分枝定界算法 |
| |
| 引用本文： | 李国君,高随祥.约束最小权生成树的近似算法和分枝定界算法[J].鲁东大学学报,1992(3). |
| |
| 作者姓名： | 李国君 高随祥 |
| |
| 作者单位： | 烟台师范学院数学系，延安大学 陕西 |
| |
| 摘 要： | 给定一个网络G,欲求一个所有通路的边数不超过给定的正整数k且权最小的生成树.在此给出的近似算法是从一个可行树出发,经过改进的程序,求出其近似解——局部最优解可行树,并具体给出了一个分枝定界算法.
|
| 关 键 词： | 生成树 约束极小树 近似算法 分枝定界算法 责任值 |
HEURISTIC AND EXACT ALGORITHMS FOR THE CONSTRAINT MINIMUM WIGHT SPANNING TREE PROBLEM |
| |
| Li Guojun Gao suixiang.HEURISTIC AND EXACT ALGORITHMS FOR THE CONSTRAINT MINIMUM WIGHT SPANNING TREE PROBLEM[J].Ludong University Journal (Natural Science Edition),1992(3). |
| |
| Authors: | Li Guojun Gao suixiang |
| |
| Abstract: | The constraint minimum wight spanning tree problem is studied. The heuristic algorithm which sets out from a feasible tree is proposed to seek for a tree,in which the number of links in each path is no more than a positive integer k given proviously, so that it's wight is as small as possible. A branch-bound algorithm is designed to obtain a exact solution. |
| |
| Keywords: | spanning tree constraint minimal tree heuristic algorithm branch-bound algorithm incombent |
| 本文献已被 CNKI 等数据库收录！ |
