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

作者：陈国龙; 郭文忠; 涂雪珠; 陈火旺

来源：软件学报, 2006, (03): 364-370.

• 最小生成树
• 非劣最优解 minimum spanning tree
• Pareto optimal

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

• 单位
  福州大学; 中国人民解放军国防科学技术大学