求解ＴＳＰ的插隊算法中初始回路的選擇
2008-12-31 00:00:00郭燕史麗萍陳紅王正達
計算機時代 2008年11期
摘要：插隊算法是求解旅行商問題(TSP)的一種較好的近似算法。插隊算法中初始回路的選擇對算法的性能具有至關重要的影響。文章在考慮了城市分布特點的基礎上，選用能大致模擬密集城市分布的三角形作為初始回路，以包羅同一方向上更多的城市，然后按照子回路增加路徑最短規則依次將其余城市加入到路徑中，形成旅行商問題較優的近似解。與其他啟發式算法比較，該方法不需迭代，且解的質量更好。TSP測試文件berlin52.tsp仿真結果證明了該方法的優越性。
關鍵詞：旅行商；插隊算法；初始回路；城市分布
