求解多目标最小生成树问题的改进算法

被引：8

作者：

陈国龙 ^{[1
]}

郭文忠 ^{[2
]}

涂雪珠 ^{[2
]}

陈火旺 ^{[1
]}

机构：

[1] 国防科学技术大学计算机学院

[2] 福州大学数学与计算机科学学院

来源：

软件学报 | 2006年 / 03期

关键词：

最小生成树; 非劣最优解;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

多目标最小生成树问题是典型的NP问题,Zhou和Gen提出了一种用于计数多目标最小生成树问题的所有非劣最优最小生成树的算法,但该算法无法保证能够找到所有非劣最优最小生成树.针对此问题,提出一种改进的计数算法,并定性说明改进算法能够找到问题的所有非劣最优最小生成树.改进算法在进行子树剔除时增加了一些条件.模拟实验结果表明,改进后的计数算法能够找到所有的非劣最优解.这也说明该算法具有应用的潜力.

引用

页码：364 / 370

页数：7