旅行商問題的求解方法動態(tài)規(guī)劃法和貪心法算法論文-展示頁
2024-08-16 21:26本頁面
【正文】 布比較均勻時，最近鄰點策略可以給出較好的近似解，不過，這個近似解以何種程度近似于最優(yōu)解，卻難以保證。
u=v。 //從頂點u0出發(fā)
3．循環(huán)直到集合P中包含n1條邊
(u, v)并且v屬于集合V；
P=P+{(u, v)}。
2．V=V{u0}。最近鄰點策略：從任意城市出發(fā)，每次在沒有到過的城市中選擇距離已選擇的城市中最近的一個，直到經過了所有的城市，最后回到出發(fā)城市。貪心法求解TSP問題的貪心策略是顯然的，至少有兩種貪心策略是合理的：最近鄰點策略和最短鏈接策略。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。和蠻力法相比，動態(tài)規(guī)劃法求解TSP問題，把原來的時間復雜性是O(n!)的排列問題，轉化為組合問題，從而降低了算法的時間復雜性，但它仍需要指數(shù)時間。d[0][ 1]=min(c[0][k]+d[k][m])。d[i][j]=min(c[i][k]+d[k][m])。 in。 j 1。 i++) //初始化第0列 d[i][0]=c[i][0]。假設從頂點i出發(fā)，令表示從頂點i出發(fā)經過中各個頂點一次且僅一次，最后回到出發(fā)點i的最短路徑長度，開始時，于是，TSP問題的動態(tài)規(guī)劃函數(shù)為：
（1）for (i=1。因此，我們可以知道用蠻力法求解TSP問題，只能解決問題規(guī)模很小的實例。一個20城市的TSP問題有大約有60,000,000,000,000,000個可能解。這是一個非常大的數(shù)，隨著n的增長，TSP問題的可能解也在迅速增長。如對于圖1，我們求解過程如下：（1） 路徑：12341；路徑長度：18；（2） 路徑：12431；路徑長度：11；（3） 路徑：13241；路徑長度：23；（4） 路徑：13421；路徑長度：11；（5） 路徑：14231；路徑長度：18；（6） 路徑：14321；路徑長度：18；從中，我們可以知道，路徑（2）和（4）路徑長度最短。在基本的數(shù)據(jù)結構中，一次處理每個元素的方法是遍歷。2正文蠻力法所依賴的基本技術是掃描技術，即采用一定的策略將待求解問題的所有元素一次處理一次，從而找出問題的解。最優(yōu)解算法雖然可以得到精確解，但計算時間無法忍受，因此就產生了各種近似方法，這些近似算法雖然可以較快地求得接近最優(yōu)解的可行解，但其接近最優(yōu)解的程度不能令人滿意。歸納起來，目前主要算法可分成傳統(tǒng)優(yōu)化算法和現(xiàn)代優(yōu)化算法。研究TSP的求解方法對解決復雜工程優(yōu)化問題具有重要的參考價值。本文主要介紹用蠻力法、動態(tài)規(guī)劃法、貪心法和分支限界法求解TSP問題，其中重點討論動態(tài)規(guī)劃法和貪心法，并給出相應求解程序。旅行商問題的求解方法摘要旅行商問題（TSP問題）時是指旅行家要旅行n個城市然后回到出發(fā)城市，要求各個城市經歷且僅經歷一次，并要求所走的路程最短。該問題又稱為貨郎擔問題、郵遞員問題、售貨員問題，是圖問題中最廣為人知的問題。關鍵字：旅行商問題；動態(tài)規(guī)劃法；貪心法；分支限界法1引言旅行商問題(TSP)是組合優(yōu)化問題中典型的NP完全問題，是許多領域內復雜工程優(yōu)化問題的抽象形式。關于TSP的完全有效的算法目前尚未找到，這促使人們長期以來不斷地探索并積累了大量的算法。在傳統(tǒng)優(yōu)化算法中又可分為：最優(yōu)解算法和近似方法。但限于所學知識和時間限制，本文重點只討論傳統(tǒng)優(yōu)化算法中的動態(tài)規(guī)劃法、貪心法和分支限界法，并對蠻力法做簡單介紹，用以比較。一次處理所有元素的是蠻力法的關鍵，為了避免陷入重復試探，應保證處理過的元素不再被處理。用蠻力法解決TSP問題，可以找出所有可能的旅行路線，從中選取路徑長度最短的簡單回路。我們還應注意到，圖1中，有3對不同的路徑，對每對路徑來說，不同只是路徑的方向，因此，可以將這個數(shù)量減半，則可能的解有（n1）！/2個。如：一個10城市的TSP問題有大約有180,000個可能解。 一個50城市的TSP問題有大約1062個可能解，而一個行星上也只有1021升水。
動態(tài)規(guī)劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應決策過程的一個階段，一般來說，子問題的重疊關系表現(xiàn)在對給定問題求解的遞推關系（也就是動態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復計算。 iN。 （2）for (j=1。 j++) for (i=1。 i++) //依次進行第i次迭代 if (子集V[j]中不包含i) 對V[j]中的每個元素k，計算V[m] == V[j]k。 （3）對V[ 1]中的每一個元素k，計算V[m] == V[ 1]k。 （4）輸出最短路徑長度d[0][ 1]。貪心法在解決問題的策略上目光短淺，只根據(jù)當前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結果，這個選擇都不會改變。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。本文僅重點討論最近鄰點策略及其求解過程。1．P={ }。 u=u0。
V=V{v}。 //從頂點v出發(fā)繼續(xù)求解但需注意，用最近鄰點貪心策略求解TSP問題所得的結果不一定是最優(yōu)解。 假設求解最大化問題，解向量為，其中，的取值范圍為某個有窮集合。對這個孩子結點分別估算可能取得的目標函數(shù)值，其含義是以該孩子結點為根的子樹所可能取得的目標函數(shù)值不大于，也就是部分解應滿足：
本文本欲詳細討論該算法，但無奈在編程問題中，尚有問題有待解決，時間所限，不得已放棄。3結論本文主要重點討論了動態(tài)規(guī)劃法和貪心法求解TSP問題算法，并附錄給出了相應程序。因為后面元素個數(shù)較多的子集與前面比其元素個數(shù)少1的子集間有一定對應關系，所以用遞歸方式，可以簡便很多。另，在計算d[i][j] =min(c[i][k]+d[k][j1])時，
研究報告相關推薦
鄂ICP備17016276號-1