科技经济市场
科技經濟市場
과기경제시장
KEJI JINGJI SHICHANG
2006年
8期
5-6
,共2页
最小生成树遗传算法%进化计算%度约束
最小生成樹遺傳算法%進化計算%度約束
최소생성수유전산법%진화계산%도약속
求最小生成树(简称MST)是一个经典的图论问题,已存在许多近似线性时间复杂度的快速求解算法可以解决.然而,度约束的最小生成树的求解则被证明是一个NP-完全问题,目前仍无法找到多项式时间复杂度的求解算法.本文用遗传算法进行求解,算例表明,该算法具有较好的性能.
求最小生成樹(簡稱MST)是一箇經典的圖論問題,已存在許多近似線性時間複雜度的快速求解算法可以解決.然而,度約束的最小生成樹的求解則被證明是一箇NP-完全問題,目前仍無法找到多項式時間複雜度的求解算法.本文用遺傳算法進行求解,算例錶明,該算法具有較好的性能.
구최소생성수(간칭MST)시일개경전적도론문제,이존재허다근사선성시간복잡도적쾌속구해산법가이해결.연이,도약속적최소생성수적구해칙피증명시일개NP-완전문제,목전잉무법조도다항식시간복잡도적구해산법.본문용유전산법진행구해,산례표명,해산법구유교호적성능.
