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

1、1動態(tài)規(guī)劃求解動態(tài)規(guī)劃求解TSP問題問題2貨郎擔問題貨郎擔問題(Traveling Salesman Problem) n設有設有n個城市個城市, 其中每兩個城市之間都有道路其中每兩個城市之間都有道路相連相連, 城市城市i和城市和城市j之間的距離為之間的距離為Cij。從某城。從某城市出發(fā)周游所有城市市出發(fā)周游所有城市, 經過每個城市一次且僅經過每個城市一次且僅一次一次, 最后回到出發(fā)地最后回到出發(fā)地, 求總行程最短的周游路求總行程最短的周游路線。對于一般的情況可以假設兩城市之間往返線。對于一般的情況可以假設兩城市之間往返距離不相等。在此例中距離不相等。在此例中, 為了簡化問題為了簡化問題, 設

2、往返設往返距離相等距離相等, 即即Cij=Cji。3n這就是所謂的貨郎擔問題（這就是所謂的貨郎擔問題（TSP）。這個問題）。這個問題與最短路徑問題不同與最短路徑問題不同, 最短路徑問題以當前所最短路徑問題以當前所在的位置作為狀態(tài)變量在的位置作為狀態(tài)變量, 而在貨郎擔問題中而在貨郎擔問題中, 狀狀態(tài)變量除了態(tài)變量除了要指明當前所在位置外要指明當前所在位置外, 還要指明還要指明已經經過哪幾個城市已經經過哪幾個城市。n由于貨郎擔問題經過的路線是一條經過所有城由于貨郎擔問題經過的路線是一條經過所有城市的閉合回路市的閉合回路, 因此從哪一點出發(fā)是無所謂的因此從哪一點出發(fā)是無所謂的, 因此不妨設從城市因此

3、不妨設從城市1出發(fā)。出發(fā)。4動態(tài)規(guī)劃模型構造動態(tài)規(guī)劃模型構造 n階段階段k：已經歷過的城市個數(shù)：已經歷過的城市個數(shù), 包括當前所在的包括當前所在的城市。城市。k=1, 2, , n, n+1, k=1表示出發(fā)時表示出發(fā)時位于起點位于起點, k=n+1表示結束時回到終點。表示結束時回到終點。n狀態(tài)變量狀態(tài)變量：xk=(i, Sk), 其中其中i表示當前所在的城表示當前所在的城市市, Sk表示尚未訪問過的城市的集合。很明顯表示尚未訪問過的城市的集合。很明顯nS1=2, 3, , n, , Sn=Sn+1= q其中其中 表示空集。并且有表示空集。并且有qxn=(i, ), i=2, 3, , n,

4、xn+1=(1, )5動態(tài)規(guī)劃模型構造動態(tài)規(guī)劃模型構造 n決策變量決策變量：dk=(i, j), 其中其中i為當前所在的城市為當前所在的城市, j為下一站將要到達的城市。為下一站將要到達的城市。n狀態(tài)轉移方程狀態(tài)轉移方程：若當前的狀態(tài)為：若當前的狀態(tài)為nxk=(i, Sk)n采取的決策為采取的決策為ndk=(i, j)n則下一步到達的狀態(tài)為則下一步到達的狀態(tài)為nxk+1=T(xk, dk)=(j , Skj) 6動態(tài)規(guī)劃模型構造動態(tài)規(guī)劃模型構造 n階段指標階段指標：vk(xk, dk)=Cijn最優(yōu)指標函數(shù)最優(yōu)指標函數(shù)：fk(xk)=fk(i, Sk) 表示從城市表示從城市i出出發(fā)發(fā), 經過經

5、過Sk中每個城市一次且僅一次中每個城市一次且僅一次, 最后返最后返回城市回城市1的最短距離。的最短距離。n終端條件終端條件：fn+1(xn+1)=fn+1(1, )=07實例實例五個城市的貨郎擔問題五個城市的貨郎擔問題 n求解步驟如下：求解步驟如下：n對于對于k=5, 有有qf5(i, )=minCij+f6(1, )=Ci1, d5 (i, 1), i=2, 3, 4, 5qf5(i, )的值列表如下：的值列表如下：435215233416257 if5(i, )223742558n對于對于k=4, 有有qf4(i, S4)=minCij+f5(j, S5), j S4, f4(i, S4)

6、的值列表如下：的值列表如下：(i, S4)JCijS5Cij+f5(j, S5)f4(i, S4)j*(2, 3)33 3+f5(3, )=3+7=10103(2, 4)45 5+f5(4, )=5+2=774(2, 5)51 1+f5(5, )=1+5=665(3, 2)23 3+f5(2, )=3+2=552(3, 4)44 4+f5(4, )=4+2=664(3, 5)56 6+f5(5, )=6+5=11115(4, 2)25 5+f5(2, )=5+2=772(4, 3)34 4+f5(3, )=4+7=11113(4, 5)53 3+f5(5, )=3+5=885(5, 2)21

7、1+f5(2, )=1+2=332(5, 3)36 6+f5(3, )=6+7=13133(5, 4)43 3+f5(4, )=3+2=5549n對于對于k=3, 有有qf3(i, S3)=minCij+f4(j, S4), j S3, f3(i, S3)的值的值列表如下：列表如下： 10(i, S3)JCijS4Cij+f4(j, S4)f3(i, S3)j*(2, 3, 4)3435433+f4(3, 4)=3+6=9*5+f4(4, 3)=5+11=1693(2, 3, 5)3531533+f4(3, 5)=3+11=14*1+f4(5, 3)=1+13=14*143, 5(2, 4,

8、5)4551545+f4(4, 5)=5+8=131+f4(5, 4)=1+5=6*65(3, 2, 4)2434423+f4(2, 4)=3+7=10*4+f4(4, 2)=4+7=11102(3, 2, 5)2536523+f4(2, 5)=3+6=9*6+f4(5, 2)=6+3=9*92, 5(3, 4, 5)4546544+f4(4, 5)=4+8=126+f4(5, 4)=6+5=11*115(4, 2, 3)2354325+f4(2, 3)=5+10=154+f4(3, 2)=4+5=9*93(4, 2, 5)2553525+f4(2, 5)=5+6=113+f4(5, 2)=3

9、+3=6*65(4, 3, 5)3543534+f4(3, 5)=4+11=15*3+f4(5, 3)=3+13=16153(5, 2, 3)2316321+f4(2, 3)=1+10=11*6+f4(3, 2)=6+5=11*112, 3(5, 2, 4)2413421+f4(2, 4)=1+7=8*3+f4(4, 2)=3+7=1082(5, 3, 4)3463436+f4(3, 4)=6+6=12*3+f4(4, 3)=3+11=1412311n對于對于k=2, 有有qf2(i, S2)=minCij+f3(j, S3), j S2, f2(i, S2)的值列表如下：的值列表如下： (i

10、, S2)JCijS3Cij+f3(j, S3)f2(i, S2)j*(2, 3, 4, 5)3453514, 53, 53, 43+f3(3, 4, 5)=3+11=145+f3(4, 3, 5)=5+15=201+f3(5, 3, 4)=1+12=13*135(3, 2, 4, 5)2453464, 53, 52, 43+f3(2, 4, 5)=3+6=9*4+f3(4, 2, 5)=4+6=106+f3(5, 2, 4)=6+8=1492(4, 2, 3, 5)2355433, 52, 52, 35+f3(2, 3, 5)=5+14=194+f3(3, 2, 5)=4+9=13*3+f3

11、(5, 2, 3)=3+11=14133(5, 2, 3, 4)2341633, 42, 42, 31+f3(2, 3, 4)=1+9=10*6+f3(3, 2, 4)=6+10=163+f3(4, 2, 3)=3+9=1210212n對于對于k=1, 有有qf1(i, S1)=minCij+f2(j, S2), j S1, f1(i, S1)的值列表如下：的值列表如下： (1, S1)JCijS2Cij+f2(j, S2)f1(1, S1)j*(1, 2, 3, 4, 5)234527253, 4, 52, 4, 52, 3, 52, 3, 42+f2(2, 3, 4, 5)=2+13=15

12、*7+f2(3, 2, 4, 5)=7+9=162+f2(4, 2, 3, 5)=2+13=15*5+f2(5, 2, 3, 4)=5+10=15*152, 4, 513n由狀態(tài)由狀態(tài)x1=(1, 2, 3, 4, 5)開始回朔開始回朔, 得到得到 (1, 2, 3, 4, 5)j*=2j*=5j*=4(2, 3, 4, 5)(5, 2, 3, 4)(42, 3, 5)j*=5j*=2j*=3(5, 3, 4)(2, 3, 4)(3, 2, 5)j*=3j*=3j*=2j*=5(3, 4)(3, 4)(2, 5)(5, 2)j*=4j*=4j*=4j*=2(4, )(4, )(5, )(2,

13、)14n即得到以下四條回路：即得到以下四條回路：qqqqn其中其中(1)和和(4)是同一條回路是同一條回路, (2)和和(3)是同一條回路是同一條回路, 這兩條這兩條回路的圖示如下：回路的圖示如下：15n容易驗證容易驗證, 兩條回路的長度都是兩條回路的長度都是15。4352124162435215341216算法分析算法分析n0: f1(v1, S1=V)n1: f2(vi1, v-vi1)n2: f3(vi2, v-vi1, vi2)nnk: fk(vik, v-vi1, vi2, , vik)q從從V中選出中選出vi1, vi2, , vik, C(n-1, k)有種方案有種方案, 再從再從中選出中選出vik, 有有k種方案種方案, 共有