小型微型计算机系统
小型微型計算機繫統
소형미형계산궤계통
MINI-MICRO SYSTEMS
2010年
4期
752-755
,共4页
Steiner树问题%NP-complete问题%蚁群优化算法%生长森林
Steiner樹問題%NP-complete問題%蟻群優化算法%生長森林
Steiner수문제%NP-complete문제%의군우화산법%생장삼림
Steiner树问题是一个经典的优化问题.已被证明是NP-complete问题.对于此问题已经有了很多经典的求解方法,然而在这些方法中一些算法的时间复杂度太高,另一些算法则得不到较好的解.因此,本文提出一种生长森林的蚁群优化算法求解Steiner树问题.在此算法中,蚂蚁行动过程中形成的是森林,每只蚂蚁走出的每一步都只是使当前的森林进一步生长,蚂蚁行动的目标就是使森林中的所有的树连接成一棵树且这棵树包含了所有的目标节点.仿真实验结果表明,算法在寻优能力、收敛速度方面都有良好的表现.
Steiner樹問題是一箇經典的優化問題.已被證明是NP-complete問題.對于此問題已經有瞭很多經典的求解方法,然而在這些方法中一些算法的時間複雜度太高,另一些算法則得不到較好的解.因此,本文提齣一種生長森林的蟻群優化算法求解Steiner樹問題.在此算法中,螞蟻行動過程中形成的是森林,每隻螞蟻走齣的每一步都隻是使噹前的森林進一步生長,螞蟻行動的目標就是使森林中的所有的樹連接成一棵樹且這棵樹包含瞭所有的目標節點.倣真實驗結果錶明,算法在尋優能力、收斂速度方麵都有良好的錶現.
Steiner수문제시일개경전적우화문제.이피증명시NP-complete문제.대우차문제이경유료흔다경전적구해방법,연이재저사방법중일사산법적시간복잡도태고,령일사산법칙득불도교호적해.인차,본문제출일충생장삼림적의군우화산법구해Steiner수문제.재차산법중,마의행동과정중형성적시삼림,매지마의주출적매일보도지시사당전적삼림진일보생장,마의행동적목표취시사삼림중적소유적수련접성일과수차저과수포함료소유적목표절점.방진실험결과표명,산법재심우능력、수렴속도방면도유량호적표현.
