带有度约束的最小耗费生成树的分支限界算法 |
| |
引用本文: | 顾立尧.带有度约束的最小耗费生成树的分支限界算法[J].计算机应用与软件,1989,6(6):49-54. |
| |
作者姓名: | 顾立尧 |
| |
作者单位: | 上海机械学院 |
| |
摘 要: | 最小耗费生成树算法已很成熟,如Dijkstra's 算法,Prim’s 算法等。但在实际应用中我们常会碰到一类问题,对最小耗费生成树中每个结点的度数有所限制。这便是带有度约束bi(i=1,2,…,n)的最小耗费生成树(DCMCST)问题,在管道系统、通信、计算机网络中均会遇到这样的问题。本文提出一种分枝界限算法来产生DCMCST。
|
关 键 词: | 生成树 分支限界法 最小耗费 |
本文献已被 CNKI 维普 等数据库收录! |
|