利用改進(jìn)匈牙利算法求解旅行商問題

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