【文章內容簡介】 。輸出輸出 path[i]。i=path[i]。 算法主要由三部分組成：第一部分是初始化部分，其時算法主要由三部分組成：第一部分是初始化部分，其時間性能為間性能為 O(n)；； 第二部分是依次計算各個頂點到終點的最短第二部分是依次計算各個頂點到終點的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行 n1次，內層次，內層循環(huán)對所有出邊進行計算，并且在所有循環(huán)中，每條出邊只循環(huán)對所有出邊進行計算，并且在所有循環(huán)中，每條出邊只計算一次。假定圖的邊數(shù)為計算一次。假定圖的邊數(shù)為 m， 則這部分的時間性能是則這部分的時間性能是 O(m)；； 第三部分是輸出最短路徑經(jīng)過的頂點，其時間性能是第三部分是輸出最短路徑經(jīng)過的頂點，其時間性能是 O(n)。 所以，算法所以，算法 O(n+m)。 返回返回TSP問題問題 TSP問題問題 是指旅行家要旅行是指旅行家要旅行 n個城市，要求各個城市，要求各個城市個城市 經(jīng)歷經(jīng)歷 且且 僅經(jīng)歷僅經(jīng)歷 一次然后回到出一次然后回到出 發(fā)發(fā) 城市，并城市，并要求所走的路程最短。要求所走的路程最短。各個城市各個城市 間間 的距離可以用代價矩的距離可以用代價矩 陣陣 來表示。來表示。C=∞3675∞2364∞2375∞帶權圖的代價矩陣帶權圖的代價矩陣 設設 s,s1,s2,…… ,sp,s是從是從 s出發(fā)的一條路徑長度最短出發(fā)的一條路徑長度最短的簡單回路，假設從的簡單回路，假設從 s到下一個城市到下一個城市 s1已經(jīng)求出，則已經(jīng)求出，則問題轉化為求從問題轉化為求從 s1到到 s的最短路徑，顯然的最短路徑，顯然 s1,s2,…… ,sp,s一定構成一條從一定構成一條從 s1到到 s的最短路徑。的最短路徑。 如若不然，設如若不然，設 s1,r1,r2,…… ,rq,s是一條從是一條從 s1到到 s的的最最 短路徑且經(jīng)過短路徑且經(jīng)過 n1個不同城市，則個不同城市，則 s,s1,r1,r2,…… ,rq,s將是一條從將是一條從 s出發(fā)的路徑長度最短的簡單回路且比出發(fā)的路徑長度最短的簡單回路且比 s,s1,s2,…… ,sp,s要短，從而導致矛盾。所以，要短，從而導致矛盾。所以， TSP問題問題滿足最優(yōu)性原理。滿足最優(yōu)性原理。證明證明 TSP問題滿足最優(yōu)性原理問題滿足最優(yōu)性原理 假設從頂點假設從頂點 i出發(fā)，令出發(fā)，令 d( i, V ’ )表示從頂點表示從頂點 i 出發(fā)出發(fā)經(jīng)過經(jīng)過 V ’ 中各個頂點一次且僅一次，最后回到出發(fā)點中各個頂點一次且僅一次，最后回到出發(fā)點 i 的最短路徑長度，開始時，的最短路徑長度，開始時， V 39。＝＝ V－－ { i }，于是，于是，TSP問題的動態(tài)規(guī)劃函數(shù)為：問題的動態(tài)規(guī)劃函數(shù)為： d( i,V ’)=min{cik+d(k,V－－ {k})}(k∈∈ V‘ ) （式（式 ）） d(k,{ })=cki(k≠i) （式（式 ））這是最后一個階段的決策，而：這是最后一個階段的決策，而： d(1,{2,3})=min{c12+d(2,{3}),c13+ d(3,{2})} d(2,{1,3})=min{c21+d(1,{3}),c23+ d(3,{1})} d(3,{1,2})=min{c31+d(1,{2}),c32+ d(2,{1})}這一階段的決策又依賴于下面的計算結果：這一階段的決策又依賴于下面的計算結果： d(1,{2})= c12+d(2,{})d(2,{3})=c23+d(3,{}) d(3,{2})= c32+d(2,{})d(1,{3})= c13+d(3,{}) d(2,{1})=c21+d(1,{})d(3,{1})=c31+d(1,{})從城市從城市 0出發(fā)經(jīng)城市出發(fā)經(jīng)城市 3然后回到城市然后回到城市 0的最短路徑長度是：的最短路徑長度是：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}而下式可以直接獲得（括號中是該決策引起的狀態(tài)轉移）：而下式可以直接獲得（括號中是該決策引起的狀態(tài)轉移）：d(1,{})=c10=5(1→0)d(2,{})=c 20=6(2→0)d(3,{})=c 30=3(3→0)再向前倒推，有：再向前倒推，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2) d(1,{3})= c13+d(3,{})=3+3=6(1→3)d(2,{3})=c23+d(3,{})=2+3=5(2→3 )d(2,{1})= c21+d(1,{})=4+5=9(2→1)d(3,{1})=c31+d(1,{})=7+5=12(3→1) d(3,{2})= c32+d(2,{})=5+6=11(3→2)再向前倒退，有：再向前倒退，有：d(1,{2,3})=min{c12+d(2,{3}),c13+ d(3,{2})}=min{2+5,3+11}=7(1→2 )d(2,{1,3})=min{c21+d(1,{3}),c23+ d(3,{1})}=min{4+6,2+12}=10(2→1)d(3,{1,2})=min{c31+d(1,{2}),c32+ d(2,{1})}=min{7+8,5+9}=14(3→2)最后有：最后有：d(0,{1,2,3})=min{c01+ d(1,{2,3}),c02+ d(2,{1,3}),c03+ d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1 ) 所以，從頂點所以，從頂點 0出發(fā)的出發(fā)的 TSP問題的最短路徑長度為問題的最短路徑長度為 10，路徑是，路徑是0→1→2→3→0 。 假設假設 n個頂點用個頂點用 0～～ n1的數(shù)字編號，首先生成的數(shù)字編號，首先生成 1～～ n1個元素的個元素的子集存放在數(shù)組子集存放在數(shù)組 V[2n1]中，設數(shù)組中，設數(shù)組 d[n][2n1]存放迭代結果，其存放迭代結果，其中中 d[i][j]表示從頂點表示從頂點 i經(jīng)過子集經(jīng)過子集 V[j]中的頂點中的頂點 一次且僅一次，最一次且僅一次，最后回到出發(fā)點后回到出發(fā)點 0的最短路徑長度。的最短路徑長度。ji {} {1} {2} {3} {1,2} {1,3} {2,3}{1,2,3}0 101 5 8 6 7 2 6 9 5 10 3 3 12 11 14 動態(tài)規(guī)劃法求解動態(tài)規(guī)劃法求解 TSP問題的填表過程問題的填表過程算法算法 ——TSP 問題問題1．． for(i=1。in。i++)//初始化第初始化第 0列列d[i][0]=c[i][0]。2．． for(j=1。j2n11。j++)for(i=1。in。i++)//依次進行第依次進行第 i次迭代次迭代if(子集子集 V[j]中不包含中不包含 i)對對 V[j]中的每個元素中的每個元素 k， 計算計算 d[i][j]=min(c[i][k]+d[k][j1])。3．對．對 V[2n11]中每一個元素中每一個元素 k， 計算計算 d[0][2n11]=min(c[0][k]+d[k][2n12])。4．． 輸出最短路徑長度輸出最短路徑長度 d[0][2n11]。 顯然，算法的時間復雜性為顯然，算法的時間復雜性為 O(2n)。 和蠻力法相比，動和蠻力法相比，動態(tài)規(guī)劃法求解態(tài)規(guī)劃法求解 TSP問題，把原來的時間復雜性是問題，把原來的時間復雜性是 O(n!)的排列的排列問題，轉化為組合問題，從而降低了算法的時間復雜性，但問題，轉化為組合問題，從而降低了算法的時間復雜性，但它仍需要指數(shù)時間。它仍需要指數(shù)時間。 設頂點之間的代價存放在數(shù)組設頂點之間的代價存放在數(shù)組 c[n][n]中，動態(tài)規(guī)劃法中，動態(tài)規(guī)劃法求解求解 TSP問題的算法如下：問題的算法如下： 返回返回 組合問題中的動態(tài)規(guī)劃法組合問題中的動態(tài)規(guī)劃法 0/1背包問題背包問題 最長公共子序列問題最長公共子序列問題返回返回0/1背包問題背包問題 在在 0/1背包問題中，物品背包問題中，物品 i或者被裝入背包，或者不被或者被裝入背包，或者不被裝入背包，設裝入背包，設 xi表示物品表示物品 i裝入背包的情況，則當裝入背包的情況，則當 xi=0時，時，表示物品表示物品 i沒有被裝入背包，沒有被裝入背包， xi=1時，表示物品時，表示物品 i被裝入背被裝入背包。根據(jù)問題的要求，有如下約束條件和目標函數(shù)：包。根據(jù)問題的要求，有如下約束條件和目標函數(shù)： （式（式 ））（式（式 ））于是，問題歸結為尋找一個滿足約束條件式于是，問題歸結為尋找一個滿足約束條件式 ，并使目標，并使目標函數(shù)式函數(shù)式 X=(x1,x2,…, xn)。證明證明 0/1背包問題滿足最優(yōu)性原理。背包問題滿足最優(yōu)性原理。設設 (x1,x2,…, xn)是所給是所給 0/1背包問題的一個最優(yōu)解，則背包問題的一個最優(yōu)解，則 (x2,…, xn)是下面一個子問題的最優(yōu)解：是下面一個子問題的最優(yōu)解：如若不然，設如若不然，設 (y2,…… ,yn)是上述子問題的一個最優(yōu)解，則是上述子問題的一個最優(yōu)解，則 因此，因此， 這說明這說明 (x1,y2,…… ,yn)是所給是所給 0/1背包問題比背包問題比 (x1,x2,…… ,xn)更優(yōu)的更優(yōu)的解，從而導致矛盾。解，從而導致矛盾。 0/1背包問題可以看作是決策一個序列背包問題可以看作是決策一個序列 (x1,x2,…, xn)， 對任對任一變量一變量 xi的決策是決定的決策是決定 xi=1還是還是 xi=0。 在對在對 xi1決策后，已確定了決策后，已確定了(x1,…, xi1)， 在決策在決策 xi時，問題處于下列兩種狀態(tài)之一：時，問題處于下列兩種狀態(tài)之一：（（ 1）背包容量不足以裝入物品）背包容量不足以裝入物品 i，則，則 xi=0， 背包不增加價值；背包不增加價值；（（ 2）背包容量可以裝入物品）背包容量可以裝入物品 i，則，則 xi=1， 背包的價值增加了背包的價值增加了 vi 這兩種情況下背包價值的最大者應該是對這兩種情況下背包價值的最大者應該是對 xi決策后的背包決策后的背包價值。價值。的最優(yōu)值為的最優(yōu)值為 V(i， j)，即，即 V(i， j)是背包容量為是背包容量為 j （（ 1≤j≤C）） ，可選擇物品為可選擇物品為 i， i+1， …… ， n時時 01背包問題的最優(yōu)值。由背包問題的最優(yōu)值。由 01背背包問題的最優(yōu)子結構性質，可以建立計算包問題的最優(yōu)子結構性質，可以建立計算 V(i， j)的遞歸式的遞歸式 （（ 動動態(tài)規(guī)劃函數(shù)）態(tài)規(guī)劃函數(shù)） 如下。如下。 V(i,0)= V(0,j)=0（式（式 ））（式（式 ））設所給設所給 01背包問題的子問題背包問題的子問題 式式 ：把前面表明：把前面 i個物品裝入容量為個物品裝入容量為 0的背包和把的背包和把 0個個物品裝入容量為物品裝入容量為 j的背包，得到的價值均為的背包，得到的價值均為 0。式。式 式子表明：如果第式子表明：如果第 i個物品的重量大于背包的容量，則裝入前個物品的重量大于背包的容量，則裝入前 i個物品得到的最大價值和裝入前個物品得到的最大價值和裝入前 i1個物品得到的最大價值是個物品得到的最大價值是相同的，即物品相同的，即物品 i不能裝入背包；第二個式子表明：如果第不能裝入背包；第二個式子表明：如果第 i個個物品的重量小于背包的容量，則會有以下兩種情況：物品的重量小于背包的容量，則會有以下兩種情況：（（ 1）如果把第）如果把第 i個物品裝入背包，則背包中物品的價值等于個物品裝入背包，則背包中物品的價值等于把前把前 i1個物品裝入容量為個物品裝入容量為 jwi的背包中的價值加上第的背包中的價值加上第 i個物品個物品的價值的價值 vi；；（（ 2）） 如果第如果第 i個物品沒有裝入背包，則背包中物品的價值就個物品沒有裝入背包，則背包中物品的價值就等于把前等于把前 i1個物品裝入容量為個物品裝入容量為 j的背包中所取得的價值。的背包中所取得的價值。顯然，取二者中價值較大者作為把前顯然，取