旅行商問題的求解方法動態(tài)規(guī)劃法和貪心法算法論文-wenkub
2022-08-29 21:26:55 本頁面
【正文】 每一個子集用一個字符串表示 int[][] c。4建議當(dāng)城市個數(shù)較少時，用動態(tài)規(guī)劃法求出最優(yōu)解；當(dāng)城市個數(shù)較多并且各邊的代價值分布比較均勻時，貪心法可以給出較好的近似解。而對于貪心法，本文很好地避免了這個問題，一旦城市編號確定，可以從任意城市出發(fā)，這也是本文中貪心法優(yōu)于動態(tài)規(guī)劃法的一點。動態(tài)規(guī)劃法相對貪心法來說雖然要精確些，但代碼相對繁雜很多，對時間和空間要求很多，僅適用于城市數(shù)量較小的情況。另，在計算d[i][j] =min(c[i][k]+d[k][j1])時，獲得d[k][j1]的過程比較困難，運用字符串后，我們就可以首先找到指定字符，然后去掉該字符，返回剩余字符串，在與V[]逐個比較，找到與其相等的V[]中元素對應(yīng)下標(biāo)，此下標(biāo)即為j1；具體求解過程可參考附錄源程序，有詳細(xì)說明。3結(jié)論本文主要重點討論了動態(tài)規(guī)劃法和貪心法求解TSP問題算法，并附錄給出了相應(yīng)程序。 假設(shè)求解最大化問題，解向量為，其中，的取值范圍為某個有窮集合。
V=V{v}。1．P={ }。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。 （4）輸出最短路徑長度d[0][ 1]。 i++) //依次進(jìn)行第i次迭代 if (子集V[j]中不包含i) 對V[j]中的每個元素k，計算V[m] == V[j]k。 （2）for (j=1。
動態(tài)規(guī)劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計算。如：一個10城市的TSP問題有大約有180,000個可能解。用蠻力法解決TSP問題，可以找出所有可能的旅行路線，從中選取路徑長度最短的簡單回路。但限于所學(xué)知識和時間限制，本文重點只討論傳統(tǒng)優(yōu)化算法中的動態(tài)規(guī)劃法、貪心法和分支限界法，并對蠻力法做簡單介紹，用以比較。關(guān)于TSP的完全有效的算法目前尚未找到，這促使人們長期以來不斷地探索并積累了大量的算法。該問題又稱為貨郎擔(dān)問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。本文主要介紹用蠻力法、動態(tài)規(guī)劃法、貪心法和分支限界法求解TSP問題，其中重點討論動態(tài)規(guī)劃法和貪心法，并給出相應(yīng)求解程序。歸納起來，目前主要算法可分成傳統(tǒng)優(yōu)化算法和現(xiàn)代優(yōu)化算法。2正文蠻力法所依賴的基本技術(shù)是掃描技術(shù)，即采用一定的策略將待求解問題的所有元素一次處理一次，從而找出問題的解。如對于圖1，我們求解過程如下：（1） 路徑：12341；路徑長度：18；（2） 路徑：12431；路徑長度：11；（3） 路徑：13241；路徑長度：23；（4） 路徑：13421；路徑長度：11；（5） 路徑：14231；路徑長度：18；（6） 路徑：14321；路徑長度：18；從中，我們可以知道，路徑（2）和（4）路徑長度最短。一個20城市的TSP問題有大約有60,000,000,000,000,000個可能解。假設(shè)從頂點i出發(fā)，令表示從頂點i出發(fā)經(jīng)過中各個頂點一次且僅一次，最后回到出發(fā)點i的最短路徑長度，開始時，于是，TSP問題的動態(tài)規(guī)劃函數(shù)為：
（1）for (i=1。 j 1。d[i][j]=min(c[i][k]+d[k][m])。和蠻力法相比，動態(tài)規(guī)劃法求解TSP問題，把原來的時間復(fù)雜性是O(n!)的排列問題，轉(zhuǎn)化為組合問題，從而降低了算法的時間復(fù)雜性，但它仍需要指數(shù)時間。貪心法求解TSP問題的貪心策略是顯然的，至少有兩種貪心策略是合理的：最近鄰點策略和最短鏈接策略。
2．V=V{u0}。
u=v。在使用分支限界法搜索問題的解空間樹時，首先根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的界[down, up]，然后從根結(jié)點出發(fā)，擴(kuò)展根結(jié)點的個孩子結(jié)點，從而構(gòu)成分量的種可能的取值方式。動態(tài)規(guī)劃法中對于頂點元素生成的子集本文中用字符串形式存儲，然后再用遞歸方法按照子集中元素個數(shù)從小到大開始賦值。在求解最佳路徑所經(jīng)過城市順序時，本文是通過邊查找d[i][j]邊記錄路徑的，這樣可以省掉很多麻煩，另，路徑也是采用字符串形式的數(shù)組，數(shù)組規(guī)模與存儲城市間距離的c[][]數(shù)組相同，由于很多元素均不需賦值，這樣做可能會浪費內(nèi)存空間，但是目前還沒找到更好地求解方法。貪心法雖然比較簡單，實現(xiàn)起來比較容易，但不是很精確，當(dāng)圖中頂點個數(shù)較多并且各邊的代價值分布比較均勻時，貪心法可以給出較好的近似解，不過，這個近似解以何種程度近似于最優(yōu)解，卻難以保證。本文程序優(yōu)點，各個子函數(shù)功能分隔很明顯，沒有大量集中在一個函數(shù)里面，而是分成了幾個不同功能的小函數(shù)，這樣程序可閱讀性提高。5參考文獻(xiàn)（1）《計算機(jī)算法分析與設(shè)計》第二版，王曉東編著，電子工業(yè)出版社（2）Java語言與面向?qū)ο蟪绦蛟O(shè)計（第2版）印旻、王行言編著，清華大學(xué)出版社（3）求解TSP算法，周康、強(qiáng)小利、同小軍、許進(jìn)，計算機(jī)工程與應(yīng)用6附錄package exp2。//頂點間距離 int[][] d。//無窮大距離 表示城市自己到達(dá)自己時，距離無窮大，不作為考慮因素 //構(gòu)造函數(shù) public TSPDynamic(){ initialC()。 N = ()。 c = new int[N][N]。 j N 。 } } //初始化頂點生成的子集的對外調(diào)用函數(shù) public void initialV1(){ V = new String[(int)(2,N1)]。//如果全部頂點已初始化完成，則返回。amp。//用于表示下一個即將加入子集的數(shù)字 if(i == 0)ch = 0。 i ++。 retur
研究報告相關(guān)推薦
鄂ICP備17016276號-1