TSP问题的动态规划解法

1、TSP问题的动态规划解法第十七组：3103038028郑少斌3103038029 王瑞锋3103038035 江飞鸿3103038043 韩鑫3103055004 唐万强1. TSP问题简介旅行商问题（Traveling Salesman Problem简称TSP,亦称为 货单郎问题）可以描述为：对于N个城市，它们之间的距离 已知，有一旅行商要从某一城市走遍所有的城市，且每一城市只能经过一次，最后回到出发的城市，问如何选择路线可使他 走过的路径最短。这是一个典型的组合优化问题。 它有很强的 现实意义，可以应用于交通运输，物资调配，旅游线路设置。 对于了解某个国家地理分布也有一定的现实意义。这个

2、问题的解法有很多种，在这里我们尝试使用最优控制中的动态规划的 相关知识来进行求解。2. TSP问题分析对于这个问题，我们首先想到的是应用穷举法进行解答，但是这个方法时间和空间的复杂度很高。从表面上看， TSP 问题很简单，其实则不然。对于 N个城市的TSP存在的可 能路径为（N-1） !/2条，当N较大时，其数量是惊人的。计算每条路经都需求出N个距离之和，这样各种路径及其距离之和的计算量正比与N!/2.用搜索法要求就规模大的TSP是不现实的。例如使用IGFLOPs次的计算机搜索TSP所需的时间如下表所不城市数7152050100200加法量32.5x106.5 X10111.2X10181.5

3、x1064l “1575x10- -37410搜索时间2.5父101.8h350y5M 1048y4 c14210 y4 c35810 y由上可知，对于这个问题采用穷举法进行解答是不现实的，这 就要求我们采用其他的方法进行解答。3. 其他求解TSP问题的方法*贪心法a.所谓贪心法，就是在组合算法中，将每一步都取局部最优的求解方法。b.下表表示用贪心法求解TSP的过程。先将各城市间的距离用行列式形式表示，主对角线上用b表示。我们可以从城市C1出发，依次在每一行或列中选取元素最小的路径， 且每个城市只能访问一次。麻ClC2C3Clw14nc:14叩4C3174aiC4584C5ID1770)?36

4、C721210吸C5c605108281?3217610«3J03m16U916®E8117c.按贪心法从C1出发所挑选的路径为C1 > C7 > C6 > C2 > C3 > C4 > C5 > C1L = 2 + 7+3+4 + 4 + 3+ 10= 33不难看出，这种从局部最优原则出发的方法所得的结果的好坏，与城市间的距离的具体情况和从那个城市开始有关。例如，从C7出发时，用贪心法所得的结果为C7 > C1 > C4 > C5 > C3 > C2 > C6 > C7其路线长度减为L =

5、 2+5 + 3 + 7 + 4+3 + 7 = 31*Hopfield神经元网络法a.全互连型神经网络求解 TSP问题：设有N个城市：C= C1C2Cn C中任意两个城市的距离D( gCj尸dij现在要找到一个城市的排列七(1)孰(2).Cn(N”使得闭合路径Z dlcn(i) Cn(i+1)modn】为最小我们用换位矩阵来表征一条路径。对于 N个城市来说， 换位矩阵有N*N个元素，需要用N*N个神经元来表征。ABCDEA00001B10000C00100D01000E000102 .换位矩阵每列只能有一个一;3 .换位矩阵中元素一之和应为根据下面四方面的要求，即：1.换位矩阵每行只能有一个

6、一;N; 4.所构造的函数的极小值对应于最短路径。我们构造出与TSP相对应的计算能量函数为2 N N N、vVxi - N 二，工“ dxyVxi(V2 xi yT i 1y,i 1 vy,i _1 )a N NN b N NN cE、VxiVxj 、工 ' VxiVyi -2 xd i j =t 12yxWyd12式中前三项与条件的1, 2, 3的要求对应，上式的第四项为目标项，它的最小值就对应于最短路径长度。上式中v的数值为0或者1, 是由表正换位矩阵中神经元的输出来表示的。4. TSP问题的动态规划解法主要特点：将一个问题分为若干个相互联系的阶段，每个阶 段进行决策优化。在这种多

7、阶段决策优化过程中，无论其初始状 态和初始决策如何，以后的最优策略只取决于由最初策略所形成 的当前策略。我们应用动态规划的解法来求解五个城市的 TSP问题。我们采用一个矩阵A表示城市之间的距离0丸ai3朝ai5ai6ai7ai8ai9aii0队0a23a24a25a26a27a28a29a2i0ai3a230a34a35a36a37a38a39a3i0而a24a340a45a46a47a48a49a4i0ai5a25a35a450a56a57a58a59a5i0A =ai6a26a36a46a560a67a68a69a6i0ai7a27a37a47a57a670a78a79a7i0ai8a28

8、a38a48a58a68a780a89a8i0ai9a29a39a49a59a69a79a890a9i0aiioa2i0a3i0a4i0a5i0a6i0a7i0a8i0a9i00 1其中，aij,i= 0,i2 .9i0j =Q2 .9i0 表示第i个城市和第j个城市之间的距离O这是个对称阵,而且对角线的元素均为0假定我们已经找到一个最短的路径， 设它是先从G到之， 则从&出发沿着这条路径回到g的路，必定是经过C-GcJ 中每个城市一次，最后回到g的路径中的最短的一条，也就 是符合最优原理。设f（G,S）表示从城市G出发，通过S集合中所有城市一次 且仅一次，最后回到出发城市G的最短路径

9、的长度。由f的 定义知，所求最短路径长度可表示为f （c1,C -七）。根据最优原理，应有f Ci,C - '6 = min dik f Ck,C - 'jCk一用殳的有:f （c ,s）= min Ou + f （cj,c -七）1。根据以上分析，应用 Matlab编程如下: clear clcD =0146.13356.43286.99349.83;140.95228.38456.76201.68;431.53198.65;364.21233.23287.89471.96418.44222.73;340.68191.78213.68232.220;n=4;c1=1;c2=n

10、*nchoosek(n-1,n-1);c3=n*nchoosek(n-1,n-2);c4=n*nchoosek(n-1,n-3);c5=n*nchoosek(n-1,n-4);layer1=zeros(1,c1);layer2=zeros(1,c2);layer3=zeros(1,c3);layer4=zeros(1,c4);layer5=zeros(1,c5);path1=0;path2=zeros(1,c2);path3=zeros(1,c3);path4=zero s(1,c4);path5=zeros(1,c5);n/ ，白YZn fT TT TT 7TTTTT / I Jfor i=

11、1:1:c5+1layer5(1,i)=D(i,1);end%# 冏 层layer4(1,1)=D(3,2)+layer5(1,2); %3-2-1layer4(1,2)=D(2,3)+layer5(1,3); %2-3-1layer4(1,3)=D(4,2)+layer5(1,2); %4-2-1layer4(1,4)=D(2,4)+layer5(1,3); %2-4-1layer4(1,5)=D(5,2)+layer5(1,2); %5-2-1layer4(1,6)=D(2,5)+layer5(1,5); %2-5-1layer4(1,7)=D(4,3)+layer5(1,3); %4-3

12、-1layer4(1,8)=D(3,4)+layer5(1,4); %3-4-1layer4(1,9)=D(5,3)+layer5(1,3); %5-3-1layer4(1,10)=D(3,5)+layer5(1,5);%3-5-1layer4(1,11)=D(5,4)+layer5(1,4);%5-4-1layer4(1,12)=D(4,5)+layer5(1,5);%4-5-1n / " TnTTTTnTTnTTnT “TTTnT “ “ TT “ “ TT ” “ “ " “ TTTTTT " ”/Uff ii ii ii ii ii ii ii ii ii

13、 ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii#第三层dxy,p=min(D(4,3)+layer4(1,1)D(4,2)+layer4(1,2);%4-(2 3)-1layer3(1,1)=dxy; path3(1,1)=p;dxy,p=min(D(5,3)+layer4(1,1)D(5,2)+layer4(1,2);%5-(2 3)-1layer3(1,2)=dxy; path3(1,2)=p;dxy,p=min(D(3,4)+

14、layer4(1,3)D(3,2)+layer4(1,4);%3-(2 4)-1layer3(1,3)=dxy; path3(1,3)=p;dxy,p=min(D(5,4)+layer4(1,3)D(5,2)+layer4(1,4);%5-(2 4)-1layer3(1,4)=dxy; path3(1,4)=p;dxy,p=min(D(3,5)+layer4(1,5)D(3,2)+layer4(1,6);%3-(2 5)-1layer3(1,5)=dxy; path3(1,5)=p;dxy,p=min(D(4,5)+layer4(1,5)D(4,2)+layer4(1,6);%4-(2 5)-

15、1layer3(1,6)=dxy; path3(1,6)=p;dxy,p=min(D(2,4)+layer4(1,7)D(2,3)+layer4(1,8);%2-(3 4)-1layer3(1,7)=dxy; path3(1,7)=p;dxy,p=min(D(5,4)+layer4(1,7)D(5,3)+layer4(1,8);%5-(3 4)-1layer3(1,8)=dxy; path3(1,8)=p;dxy,p=min(D(2,5)+layer4(1D(2,3)+layer4(1,10); %2-(3 5)-1layer3(1,9)=dxy; path3(1,9)=p;dxy,p=min

16、(D(4,5)+layer4(1,9)D(4,3)+layer4(1,10); %4-(3 5)-1layer3(1,10)=dxy; path3(1,10)=p;dxy,p=min(D(2,5)+layer4(1,11)D(2,4)+layer4(1,12); %2-(4 5)-1layer3(1,11)=dxy; path3(1,11)=p;dxy,p=min(D(3,5)+layer4(1,11)D(3,4)+layer4(1,12); %3-(4 5)-1layer3(1,12)=dxy; path3(1,12)=p;n / " TnTTTTnTTnTTnT “TTTnT “

17、 “ TT “ “ TT ” “ “ " “ TTTTTT " ”/Uff ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii iiif if if if if if if if if if if if if if if if if if if if if if if if if if if、口ii ii ii ii ii ii ii ii ii ii ii ii ii

18、ii ii ii ii ii ii ii ii ii ii ii ii ii ii ii ljr J*. / /、dxy,p=min(D(2,3)+layer3(1,12)D(2,4)+layer3(1,10)D(2,5)+layer3(1,8); %2-(3 4 5)-1layer2(1,1)=dxy;path2(1,1)=p;dxy,p=min(D(3,2)+layer3(1,11)D(3,4)+layer3(1,6)D(3,5)+layer3(1,4); %3-(2 4 5)-1layer2(1,2)=dxy;path2(1,2)=p;dxy,p=min(D(4,2)+layer3(1,

19、9)D(4,3)+layer3(1,5)D(4,5)+layer3(1,2); %4-(2 3 5)-1layer2(1,3)=dxy;path2(1,3)=p;dxy,p=min(D(5,2)+layer3(1,7)D(5,3)+layer3(1,3)D(5,4)+layer3(1,1); %5-(2 3 4)-1layer2(1,4)=dxy;path2(1,4)=p;n / " TnTTTTnTTnTTnT “ “TT“ “TT" “ TTTnT “ “ TT “ “ TT ” “ “ " “ TTTTTT " ”/Uli II II II II

20、II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II II .TTTTTTTTTT“ “ TT “ “ TT " “ TTTnTTTTnT “ “ TT " “ TTTnTTTTnTTT " “ TT “ “ TT “ " " “ TTTTTT " H-L 1111 11 1111 11 f| j层dxy,p=min(D(1,2)+layer2(1,1)D(

21、1,3)+layer2(1,2)D(1,4)+layer2(1,3) D(1,5)+layer2(1,4); %1-(2 3 4 5)-1layer1(1,1)=dxypath1=p;path2=path2;path3=path3;optimal_path=1 2 3 5 4 1运行结果：layer1 = 1.0933e+003optimal_path = 1235416. 附录附贪心法及神经网络法的程序及相应的运行结果(均为用Matlab 编写)贪心法程序：clearclcD=zeros(10,10);L_min=zeros(1,10);Path=zeros(1,10);Dmin=0;Min

22、_D=zeros(1,10);optimal=0;for i=1:1:10for j=1:1:10D(i,j)=unidrnd(1000);endendfor i=1:1:10for j=1:1:10if i=jD(i,j)=1001;elseD(i,j)=D(j,i);endendend for n=1:1:10Path(1,1)=n;for i=1:1:9L_min(1,i)=min(D(Path(1,i),:);for y=1:1:10if D(Path(1,i),y)=L_min(1,i)Path(1,i+1)=y;break;endendfor j=1:1:10D(Path(1,i)

23、,j)=1001;D(j,Path(1,i)=1001;endD;endfor k=1:1:9Dmin=Dmin+L_min(1,k);endPathDminMin_D(1,n)=Dmin;Dmin=0;endoptimal=min(Min_D)神经网络解法程序：% 人工 神 经 网 络 求 解 TSP 2004- 5 9clear clcn=10;k1=500;k2=500;k3=500;k4=500;u0=0.02;k=0;%初始参数dxy=0;const=0;u_xi=0;du_xi=0;T=0.01;Dmin=0;flag=0;count=0; row=0;column=0;row_s

24、=0;column_s=0; % 初始化变量 U=zeros(n,n);V=zeros(n,n);D=zeros(n,n);Utemp=zeros(n,n);Vtemp=zeros(n,n);%初始化数组Uini=zeros(n,n);Vini=zeros(n,n);City_Path=zeros(1,n);%初始化数组for x=1:1:nfor y=1:1:nD(x,y)=unifrnd(0.01,1);endendfor x=1:1:nfor y=1:1:nif x=yD(x,y)=0;endD(x,y)=D(y,x);endendN=n*n;uoo=-0.5*u0*log(n-1);

25、%计算初值 u00while flag=0for i=1:1:nfor j=1:1:nr=unifrnd(-0.1*u0, 0.1*u0);U(i,j)= uoo + r;%按均匀分布随机产生人工神经网络每个神经元初始输入ui, i=1,2.100V(i,j)=0.5 * (1+tanh( U(i,j)/u0 ) ); % 把 ui 代入 S 函数得到每个神经元的初始输出vi, i=1,2.100endendUini=U;%保存初态uiVini=V;%保存初态vifor k=0:1:200%迭代次数for x=1:1:n%城市循环for i=1:1:n%路径按步循环for y=1:1:n %求

26、微分方程中的最后一个和式：Edxy*(V(y,i-1)+V(y,i+1),x,y from 1 to n. if i=1 dxy=dxy + D(x,y) *(0+V(y,i+1);%当i=1时,不存在左顺联，所以V(y,i-1)=0. elseif i=n dxy=dxy + D(x,y) * (V(y,i-1) +0);%当i=n时，不存在顺联，所以V(y,i+1) =0.else dxy=dxy + D(x,y) * (V(y,i-1) +V(y,i+1); %当1<i<n时用原公式.endendconst=-k1*(sum(V(x,:)-V(x,i)-k2*(sum(V(:

27、,i)-V(x,i) - k3*(sum(sum(V)-n) - k4*dxy;% 求 微分方程的常数项du_xi=-U(x,i)+const;%求ui对时间t%把u(t+T)存入%把V(t+T)存入%u_xi清零%dxy清零%用t+T时刻dui/dtu_xi=U(x,i)+du_xi*T;%用 Eula 法求u(t+T)=u(t)+du/dt * Tv_xi=0.5*(1+tanh(u_xi/u0); %把 u(t+T)代入 S函数求t+T时刻的V(t+T)Utemp(x,i)=u_xi;转移数组UtempVtemp(x,i)=v_xi;转移数组Vtempu_xi=0;dxy=0;endendU=Utemp;的ui替换t时刻的uiV=Vtemp;的Vi替换t时刻的Vi%用t+T时刻endV;flag=1；for i=1:1:nfor j=1:1:nif V(i,j)<0.1V(i,j)=0;elseif V(i,j)