利用改進匈牙利算法求解旅行商問題

摘要： 針對傳統(tǒng)的匈牙利算法在求解旅行商問題(travelling salesman problem, TSP)時會導致多回路閉合的問題，提出了破環(huán)機制，設計了破環(huán)匈牙利算法。通過采用分配問題的描述方法對旅行商問題進行建模，并建立二者之間的轉換關系，論證了TSP可行解的充分必要條件是對應分配問題的可行解與輔助邊結合后僅包含一個環(huán)路，對6個標準旅行商進行測試和對比分析，驗證算法的有效性。... （共8頁）