蟻群算法求解直徑約束最小生成樹問題

石 磊，馮祖針，楊建強

（紅河學院 數學學院，云南 蒙自661100）

蟻群算法求解直徑約束最小生成樹問題

石 磊，馮祖針，楊建強

（紅河學院 數學學院，云南 蒙自661100）

給定無向賦權圖G和直徑約束值D，直徑約束最小生成樹問題是查找一個直徑不超過D最小權重的生成樹.當時，其是NP-hard問題.用蟻群算法對其進行求解，設計了一種新的當前節點選擇規則.分析和實驗表明，基于新的節點選擇規則的蟻群算法對直徑約束最小生成樹問題有較好的求解效果.

蟻群算法；直徑約束最小生成樹；直徑約束

0 引言

直徑約束最小生成(Bounded Diameter Minimum Spanning Tree，簡記BDMST)問題是一個經典網絡優化問題，在現實生活中有著廣泛的應用，如路由優化、數據分發、分布式系統等[1,2].

BDMST問題描述為[3]：給定無向網絡，任意節點，且；任意邊且；任意邊對應一個非負權值，稱為長度或代價，.給定正整數D.設是一棵樹，中節點的離心率定義為從到樹中其它節點的最大距離.這里的距離是兩個節點間邊的數目.樹的直徑定義為節點的最大離心率.因此BDMST模型為：

文獻[3]證明了直徑約束值時的BDMST問題為NP-完全問題，因此BDMST問題不存在多項式時間算法，只能用啟發式算法或人工智能算法求解.文獻[4]提出一次性構造生成樹算法(OTTC)，OTTC算法是基于Prim算法基礎上的貪婪啟發式算法，在不違背直徑約束的條件每次選擇距離最近的節點加入當前樹中，直到當前樹含有網絡的所有節點，但其性能較差.Raidl和Julstrom[5-6]提出了隨機貪婪啟發算法(RGH)和基于邊集編碼的遺……