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