動態(tài)規(guī)劃解TSP問題.docx

用動態(tài)規(guī)劃方法編程求解下面的問題：某推銷員要從城市v1 出發(fā)，訪問其它城市v2，v3，v6 各一次且僅一次，最后返回v1。D為各城市間的距離矩陣。問：該推銷員應(yīng)如何選擇路線，才能使總的行程最短？1、變量設(shè)定階段k：已遍歷過k個結(jié)點，k=1,26,7。 K=1表示剛從V1出發(fā)，k=7表示已回到起點V1狀態(tài)變量Xk=(i，Sk)：已遍歷k個結(jié)點，當(dāng)前位于i結(jié)點，還未遍歷的結(jié)點集合為Sk。則X1=(1，2,3,4,5,6)，X6=(i，)，X7=(1，)決策變量Uk=(i，j)：已遍歷k個結(jié)點，當(dāng)前位于i結(jié)點，下一個結(jié)點選擇j。狀態(tài)轉(zhuǎn)移方程：Xk+1 = T(Xk，Uk) = (j，Sk-j)第k階段的指標(biāo)函數(shù)Vk = Di,j。最優(yōu)指標(biāo)函數(shù)Fk(Xk) = Fk(i，Sk)：已遍歷k個結(jié)點，當(dāng)前從i結(jié)點出發(fā)，訪問Sk中的結(jié)點一次且僅一次，最后返回起點V1的最短距離。則Fk(i，Sk) = min Di,j + Fk+1(j，Sk-j) 1k6 F7(X7) = F7(1，) = 02、分析：（1）k=6時，F(xiàn)6(i，) = minDi,1 + F7(X7) = Di,1 i=2,3,4,5,6X6=(i，)U6=(i，j)X7=(1，)V6=Di,jF7(1，)V6 + F7(X7)(2，)(2，1)(1，)12012=F6(2,)(3，)(3，1)(1，)23023=F6(3,)(4，)(4，1)(1，)34034=F6(4,)(5，)(5，1)(1，)45045=F6(5,)(6，)(6，1)(1，)56056=F6(6,)即k=6時，對于每一種狀態(tài)X6，都有唯一的決策U6。（2）k=5時，F(xiàn)5(i，S5) = minDi,j + F6(j，) i=2,3,4,5,6X5=(i,S5)U5=(i,j)X6=(j, )V5=Di,jF6(j,)V5 + F6(X6)(2,6(2,6)(6，)215677=F5(2,6)(2,5(2,5)(5，)254570=F5(2,5)(2,4(2,4)(4，)303464=F5(2,4)(2,3(2,3)(3，)182341=F5(2,3)(3,6)(3,6)(6，)155671=F5(3,6)(3,5)(3,5)(5，)104555=F5(3,5)(3,4)(3,4)(4，)53439=F5(3,4)(3,2)(3,2)(2，)191231=F5(3,2)(4,6)(4,6)(6，)165672=F5(4,6)(4,5)(4,5)(5，)84553=F5(4,5)(4,3)(4,3)(3，)42327=F5(4,3)(4,2)(4,2)(2，)321244=F5(4,2)(5,6)(5,6)(6，)185674=F5(5,6)(5,4)(5,4)(4，)103444=F5(5,4)(5,3)(5,3)(3，)112334=F5(5,3)(5,2)(5,2)(2，)271239=F5(5,2)(6,5)(6,5)(5，)124557=F5(6,5)(6,4)(6,4)(4，)203454=F5(6,4)(6,3)(6,3)(3，)162339=F5(6,3)(6,2)(6,2)(2，)221234=F5(6,2)即k=時，對于每一種狀態(tài)X5，都有唯一決策U5。（3）k=4時，F(xiàn)4(i,S4) = min(Di,j + F5(j,S5) ) i=2,3,4,5,6X4=(i,S4)U4=(i,j)X5=(j,S5)V4=Di,jF5(j,S5)V4 + F5(j,S5)(2,3,4)(2,3)(3,4)183957=F4(2,3,4)(2,4)(4,3)302757=F4(2,3,4)(2,4,5)(2,4)(4,5)305383(2,5)(5,4)254469=F4(2,4,5)(2,5,6)(2,5)(5,6)257499(2,6)(6,5)215778=F4(2,5,6)(2,3,5)(2,3)(3,5)185573(2,5)(5,3)253459=F4(2,3,5)(2,3,6)(2,3)(3,6)187189(2,6)(6,3)213960=F4(2,3,6)(2,4,6)(2,4)(4,6)3072102(2,6)(6,4)215475=F4(2,4,6)(3,2,4)(3,2)(2,4)196483(3,4)(4,2)54449=F4(3,2,4)(3,2,5)(3,2)(2,5)197089(3,5)(5,2)103949=F4(3,2,5)(3,2,6)(3,2)(2,6)197796(3,6)(6,2)153449=F4(3,2,6)(3,4,5)(3,4)(4,5)55358(3,5)(5,4)104454=F4(3,4,5)(3,4,6)(3,4)(4,6)57277(3,6)(6,4)155469=F4(3,4,6)(3,5,6)(3,5)(5,6)107484(3,6)(6,5)155772=F4(3,5,6)(4,2,3)(4,2)(2,3)324173(4,3)(3,2)43134=F4(4,2,3)(4,2,5)(4,2)(2,5)3270102(4,5)(5,2)83947=F4(4,2,5)(4,2,6)(4,2)(2,6)3277109(4,6)(6,2)163450=F4(4,2,6)(4,3,5)(4,3)(3,5)45559(4,5)(5,3)83442=F4(4,3,5)(4,3,6)(4,3)(3,6)47175(4,6)(6,3)163955=F4(4,3,6)(4,5,6)(4,5)(5,6)87482(4,6)(6,5)165773=F4(4,5,6)(5,2,3)(5,2)(2,3)274168(5,3)(3,2)113142=F4(5,2,3)(5,2,4)(5,2)(2,4)276491(5,4)(4,2)104454=F4(5,2,4)(5,2,6)(5,2)(2,6)2777104(5,6)(6,2)183452=F4(5,2,6)(5,3,4)(5,3)(3,4)113950(5,4)(4,3)102737=F4(5,3,4)(5,3,6)(5,3)(3,6)117182(5,6)(6,3)183957=F4(5,3,6)(5,4,6)(5,4)(4,6)107282(5,6)(6,4)185472=F4(5,4,6)(6,2,3)(6,2)(2,3)224163(6,3)(3,2)163147=F4(6,2,3)(6,2,4)(6,2)(2,4)226486(6,4)(4,2)204464=F4(6,2,4)(6,2,5)(6,2)(2,5)227092(6,5)(5,2)123951=F4(6,2,5)(6,3,4)(6,3)(3,4)163955(6,4)(4,3)202747=F4(6,3,4)(6,3,5)(6,3)(3,5)165571(6,5)(5,3)123446=F4(6,3,5)(6,4,5)(6,4)(4,5)205373(6,5)(5,4)124456=F4(6,4,5)（4）k=3時，F(xiàn)3(i,S3) = minDi,j + F4(j,S4) i=2,3,4,5,6X3=(i,S3)U3=(i,j)X4=(j,S4)V3=Di,jF4(j,S4)V3 + F4(j,S4)(2,3,4,5)(2,3)(3,4,5)185472(2,4)(4,3,5)304272(2,5)(5,3,4)253762=F3(2,3,4,5)(2,3,4,6)(2,3)(3,4,6)186987(2,4)(4,3,6)305585(2,6)(6,3,4)214768=F3(2,3,4,6)(2,3,5,6)(2,3)(3,5,6)187290(2,5)(5,3,6)255782(2,6)(6,3,5)214667=F3(2,3,5,6)(2,4,5,6)(2,4)(4,5,6)3073103(2,5)(5,4,6)257297(2,6)(6,4,5)215677=F3(2,4,5,6)(3,2,4,5)(3,2)(2,4,5)196988(3,4)(4,2,5)54752=F3(3,2,4,5)(3,5)(5,2,4)105464(3,2,4,6)(3,2)(2,4,6)197594(3,4)(4,2,6)55055=F3(3,2,4,6)(3,6)(6,2,4)156479(3,2,5,6)(3,2)(2,5,6)197897(3,5)(5,2,6)105262=F3(3,2,5,6)(3,6)(6,2,5)155166(3,4,5,6)(3,4)(4,5,6)57378(3,5)(5,4,6)107282(3,6)(6,4,5)155671=F3(3,4,5,6)(4,2,3,5)(4,2)(2,3,5)325991(4,3)(3,2,5)44953(4,5)(5,2,3)84250=F3(4,2,3,5)(4,2,3,6)(4,2)(2,3,6)326092(4,3)(3,2,6)44953=F3(4,2,3,6)(4,6)(6,2,3)164763(4,2,5,6)(4,2)(2,5,6)3278110(4,5)(5,2,6)85260=F3(4,2,5,6)(4,6)(6,2,5)165167(4,3,5,6)(4,3)(3,5,6)47276(4,5)(5,3,6)85765(4,6)(6,3,5)164662=F3(4,3,5,6)(5,2,3,4)(5,2)(2,3,4)275784(5,3)(3,2,4)114960(5,4)(4,2,3)103444=F3(5,2,3,4)(5,2,3,6)(5,2)(2,3,6)276087(5,3)(3,2,6)114960=F3(5,2,3,6)(5,6)(6,2,3)184765(5,2,4,6)(5,2)(2,4,6)2775102(5,4)(4,2,6)105060=F3(5,2,4,6)(5,6)(6,2,4)186482(5,3,4,6)(5,3)(3,4,6)116980(5,4)(4,3,6)105565=F3(5,3,4,6)(5,6)(6,3,4)184765=F3(5,3,4,6)(6,2,3,4)(6,2)(2,3,4)225779(6,3)(3,2,4)164965(6,4)(4,2,3)203454=F3(6,2,3,4)(6,2,3,5)(6,2)(2,3,5)225981(6,3)(3,2,5)164965(6,5)(5,2,3)124254=F3(6,2,3,5)(6,2,4,5)(6,2)(2,4,5)226991(6,4)(4,2,5)204767(6,5)(5,2,4)125466=F3(6,2,4,5)(6,3,4,5)(6,3)(3,4,5)165470(6,4)(4,3,5)204262(6,5)(5,3,4)123749=F3(6,3,4,5)（5）k=2時，F(xiàn)2(i,S2) = minDi,j + F3(j,S3) i=2,3,4,5,6X2=(i,S2)U2=(i,j)X3=(j,S3)V2=Di,jF3(j,S3)V2 + F3(j,S3)(2,3,4,5,6)(2,3)(3,4,5,6)187189(2,4)(4,3,5,6)306292(2,5)(5,3,4,6)256590(2,6)(6,3,4,5)214970=F2(2,3,4,5,6)(3,2,4,5,6)(3,2)(2,4,5,6)197796(3,4)(4,2,5,6)56065=F2(3,2,4,5,6)(3,5)(5,2,4,6)106070(3,6)(6,2,4,5)156681(4,2,3,5,6)(4,2)(2,3,5,6)326799(4,3)(3,2,5,6)46266=F2(4,2,3,5,6)(4,5)(5,2,3,6)86068(4,6)(6,2,3,5)165470(5,2,3,4,6)(5,2)(2,3,4,6)276895(5,3)(3,2,4,6)115566(5,4)(4,2,3,6)105363=F2(5,2,3,4,6)(5,6)(6,2,3,4)185472(6,2,3,4,5)(6,2)(2,3,4,5)226284(6,3)(3,2,4,5)165268(6,4)(4,2,3,5)205070(6,5)(5,2,3,4)124456=F2(6,2,3,4,5)（6）k=1時，F(xiàn)1(1,S1) = minD1,j + F2(j,S2)X1=(1,S1)U1=(1,j)X2=(j,S2)V1=D1,jF2(j,S2)V1 + F2(j,S2)(1,2,3,4,5,6)(1,2)(2,3,4,5,6)107080=F1(1,2,3,4,5,6)(1,3)(3,2,4,5,6)206585(1,4)(4,2,3,5,6)306696(1,5)(5,2,3,4,6)4063103(1,6)(6,2,3,4,5)50561063、偽代碼和時間復(fù)雜度為方便計算，結(jié)點編號改為0到5.(1)用一張二維表格F表示F(i,Sk)，行數(shù)是n，列數(shù)是2n-1。(2)行號表示當(dāng)前所在的結(jié)點i。列號對應(yīng)的五位二進(jìn)制表示表示V5,V4,V3,V2,V1的一個子集，1表示在集合中，0表示不在集合中。例如：00110表示的集合為V3,V2，00000表示空集(3)再用一張n*2n-1的表格M存儲對應(yīng)每個狀態(tài)(i，Sk)所做的最優(yōu)決策，以便回溯找最短路線。偽代碼：TSP(int D，int n)/輸入n個頂點的有向圖，矩陣D是有