节点文献
基于进化计算的度约束最小生成树问题求解算法
【摘要】 求最小生成树(简称MST)是一个经典的图论问题,已存在许多近似线性时间复杂度的快速求解算法可以解决。然而,度约束的最小生成树的求解则被证明是一个NP-完全问题,目前仍无法找到多项式时间复杂度的求解算法。本文用遗传算法进行求解,算例表明,该算法具有较好的性能。
- 【文献出处】 科技经济市场 , 编辑部邮箱 ,2006年08期
- 【分类号】Q11
- 【下载频次】130
中国学术期刊网络出版总库
【摘要】 求最小生成树(简称MST)是一个经典的图论问题,已存在许多近似线性时间复杂度的快速求解算法可以解决。然而,度约束的最小生成树的求解则被证明是一个NP-完全问题,目前仍无法找到多项式时间复杂度的求解算法。本文用遗传算法进行求解,算例表明,该算法具有较好的性能。