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