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

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