資源描述：
《求解tsp問題算法綜述》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、CN4321258/TP計(jì)算機(jī)工程與科學(xué)2008年第30卷第2期ISSN10072130XCOMPUTERENGINEERING&SCIENCEVol130,No12,2008文章編號(hào):10072130X(2008)02200722033求解TSP問題算法綜述ASurveyofSolvingtheTravelingSalesmanProblem王劍文,戴光明,謝柏橋,張全元WANGJian2wen,DAIGuang2ming,XIEBai2qiao,ZHANGQuan2yuan(中國(guó)地質(zhì)大學(xué)(武漢)計(jì)算機(jī)學(xué)院,湖北武漢430
2、074)(SchoolofComputerScience,ChinaUniversityofGeosciences,Wuhan430073,China)摘要:TSP問題(旅行商問題)是一個(gè)典型的組合優(yōu)化問題,具有重要實(shí)際應(yīng)用價(jià)值。對(duì)于大規(guī)模TSP問題,至今尚未找到非常有效的求解方法。為此,本文討論了傳統(tǒng)的確定性算法和流行的智能算法,并指出各種方法的優(yōu)缺點(diǎn),提出了未來(lái)求解TSP問題的發(fā)展趨勢(shì)。Abstract:Thetravelingsalesmanproblem(TSP)isatypicalcombinationoptimi
3、zationproblem,andpossessesapracticalapplicationvalue.However,thereisnoeffectivecorrespondingsolutiontoittoday.So,inthispaper,thetraditionallyaf2firmativemethodsandpopularmeta2heuristicmethodsarediscussed.Theadvantagesanddisadvantagesofeachmethodarediscussed.Thefutu
4、reresearchdirectionoftheTSPproblemisalsogiven.關(guān)鍵詞:旅行商問題;動(dòng)態(tài)規(guī)劃法;分枝限界法;遺傳算法;郭濤算法Keywords:travelingsalesmanproblem;dynamicprogram;brandandbound;geneticalgorithm;GouTaoalgorithm中圖分類號(hào):TP301.6文獻(xiàn)標(biāo)識(shí)碼:A1引言2TSP問題的數(shù)學(xué)模型及其分類[2]旅行商問題(TravelingSalesmanProblem,簡(jiǎn)稱TSP)TSP問題的數(shù)學(xué)模型如下:是一
5、個(gè)易于描述但難于解決的著名難題之一。TSP問題對(duì)于城市V={v1,v2,?,vn}的一個(gè)訪問順序?yàn)門=可描述為:已知n個(gè)城市各城市間的距離,某一旅行商從某(t1,t2,?,tn),其中ti=V(i=1,?,n),而且tn+1=t1,則問個(gè)城市出發(fā)訪問每個(gè)城市一次且僅一次,最后回到出發(fā)城n題為求min∑dtt,其中Ω為這n個(gè)城市不重復(fù)排列的所ii+1T∈Ωi=1市,怎樣安排才使其所走路線最短。有可能的回路?，F(xiàn)實(shí)生活中有很多問題可以歸結(jié)為旅行商問題,比如通常,TSP問題可以按照其距離矩陣分為兩大類,即對(duì)郵路問題、裝配線上的螺帽問
6、題和產(chǎn)品的生產(chǎn)安排問題[1]稱性TSP問題和非對(duì)稱性TSP問題。非對(duì)稱性TSP問題等。TSP問題在電路板鉆孔進(jìn)度的安排、基因測(cè)序和機(jī)難于求解,本文主要針對(duì)常見的對(duì)稱性TSP問題進(jìn)行闡述。器人控制等方面有著重要的應(yīng)用。因此,TSP問題的求解具有重要的理論意義和實(shí)際意義。3求解TSP問題的常用算法幾十年前就已找到的一些指數(shù)級(jí)算法雖然能精確地求解TSP問題,但隨著問題規(guī)模的變大,這些算法完全失效3.1傳統(tǒng)的確定性算法(組合爆炸)。近似算法或啟發(fā)式算法盡管不能精確求解,但能夠把誤差控制在可以容忍的范圍內(nèi)并且能夠快速地得3.1.1動(dòng)態(tài)
7、規(guī)劃法到答案。本文將介紹一些傳統(tǒng)的和現(xiàn)代流行的智能求解動(dòng)態(tài)規(guī)劃法DM(DynamicProgramming,簡(jiǎn)稱DM)是TSP問題的方法。美國(guó)數(shù)學(xué)家BellmanRE等人在20世紀(jì)50年代初在研究3收稿日期:2007208201;修訂日期:2007209219基金項(xiàng)目:湖北省自然科學(xué)基金資助項(xiàng)目(2003ABA045)作者簡(jiǎn)介:王劍文(19802),男,湖南衡南人,碩士生,研究方向?yàn)樗惴ㄔO(shè)計(jì)和多目標(biāo)優(yōu)化;戴光明,博士,教授,研究方向?yàn)樗惴◣缀?、科學(xué)計(jì)算和可視化;謝柏橋,碩士生,研究方向?yàn)樗惴ㄔO(shè)計(jì)和多目標(biāo)優(yōu)化;張全元,碩士生,
8、研究方向?yàn)樗惴ㄔO(shè)計(jì)和圖像處理。通訊地址:430074湖北省武漢市中國(guó)地質(zhì)大學(xué)(武漢)計(jì)算機(jī)學(xué)院2006級(jí)碩研10班;Tel:(027)65079584;E2mail:wangjian2wen8016@126.comAddress:Class10,Graduate2006,SchoolofC
