动态规划：旅行售货员问题

1、xxxxxxxx大学结课论文项目动态规划算法解决旅行售货商问题xxxxxxxxxxxxxxxxxxxxxxxxxxxx课程名称:院系:学生姓名:学号:指导教师:xxxxxxxxxxxxxxxxxxxxx2015年6月15日摘要:旅行商问题(TSP问题)时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。动态规划(dynamicprogramming)算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或

2、分治算法不能解决的问题。本次课程设计运用动态规划解决旅行售货员问题，动态规划的基本思想是：把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。通过图的关系矩阵来表示个城市之间的关系，二维数组表示顶点之间的距离关系，对子问题进行求解比较，最后得出所求结果。关键字:旅行商问题动态规划法图矩阵目录第一章绪论1.1算法介绍1.2算法应用第二章动态规划理论知识2.1动态规划的基本思想2.2动态规

3、划设计步骤第三章旅行售货员问题3.1问题描述：旅行售货员问题3.2算法设计内容3.3算法分析3.4流程图第四章物流配送网络第五章结论第一章绪论1.1算法介绍动态规划(dynamicprogramming)是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman(贝尔曼)等人根据一类多阶段决策问题的特性，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法动态规划。解决多阶段决策过程最优化问题，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。动态规划算法的基本思想是：将待求解的问题

4、分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。1.2算法应用动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用，而且由于动态规划方法有其独特之处，在解决某些实际问题时，显得更加方便有效

5、。由于决策过程的时间参数有离散的和连续的情况，故决策过程分为离散决策过程和连续决策过程。这种技术采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。第二章动态规划理论知识2.1动态规划的基本思想把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题

6、就是初始问题的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。2.2动态规划设计步骤1）划分阶段：按照问题的时间或空间特征，把问题分为若干阶段。这若干阶段一定要是有序的或可排序的（无后向性）。2）选择状态:将问题发展到各个阶段时所出现的各种客观情况用不同的状态来表示出来。状态的选择要有无后向性。3）确定决策并写出状态转移方程:状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。第三章旅行售货员问题3.1问题描述：旅行售货员问题某售货员要到若干城市去推销商品，已知各城市之间的路程。他要选定一条从驻地出发,经过每一个城市一遍，最后回到驻地的路线，使总的路

7、程最小，并求出最小路程。3.2算法设计内容不同城市的路线和距离都不一样。运用动态规划算法来设计本次课程设计，考虑到对问题进行阶段划分和状态的选择。使用Left函数实现V'-k的下标检索。根据遍历城市的各个阶段时所出现的情况并用不同的状态表示出来。当然这时的状态必须要满足无后向性。设计第一阶段则是各顶点为空，然后给赋值。依次遍历各城市，在TSP函数中得以实现。假设4个顶点分别用0、1、2、3的数字编号，顶点之间的权值放在数组c44中。首先按个数为1,2,3的顺序生成1,2,3个元素的子集存放在数组V2n-1中。设数组dn2n-1存放迭代结果，其中dij表示从顶点i经过子集Vj中的顶点一次

8、且仅一次，最后回到出发点0的最短路径长度。3.3算法分析假设从顶点i出发，令d(i,V')表示从顶点i出发经过V'中各个顶点一次且仅一次，最后回到出发点i的最短路径的长度，开始时，V'=V_i,于是，旅行商问题的动态规划函数为：d(i,V')=mincik+d(k,V'-k)(kuV')1)d(k,)=cki(k工i)2)简单来说,就是用递归表达:从出发点0到1号点，假设1是第一个,则剩下的路程就是从1经过剩下的点最后回到0点的最短路径.所以当V'为空的时候，d(k,)=cki(k工i)找的是最后一个点到0点的距离递归求解1之后，再继续求

9、V之中剩下的点，最后找出min.如果按照这个思想直接做，对于每一个i都要递归剩下的V中所有的点，所以这样的时间复杂度就近似于N!，其中有很多重复的工作.可以从小的集合到大的集合算,并存入一个二维数组，这样当加入一个节点时，就可以用到之前的结果，如四个点的情况：邻接矩阵：node0123053215792371232912动态填表：表中元素代表第i个节点经过V集合中的点最后到0点的最短值.如果有多个值，取其中最小的一个.iVj01231,2（取min）1,3（取min）2,3（取min）1,2,3（取min）0c0i+div'=21151011c12+d23=21,c13+d32=242

10、31214c21+d13=18,c23+d31=26321415c31+d12=19,c32+d21=24这样一共循环（2,N-1）-1）*（N-1）次,就把时间复杂度缩小到0（N*2N）的级别.核心伪代码如下：for(i=1;in;i+)di0=ci0;for(j=1;j2,N-1)-1;j+)for(i=1;i<n;i+)if(子集Vj中不包含i)对Vj中的每个元素k，计算diVj=mincik+dkVj-k|每一个keVj;对V2"(nT)T中的每个元素k,计算：d02"(n-1)-1=minc0k+dk2"(n-1)-2;输出最短路径:d02&quo

11、t;(n-1)T;具体代码如下：/TravRoadD.cpp:Definestheentrypointfortheconsoleapplication/#include"stdafx.h"#include"windows.h"#include"math.h"#includestdio.h>#includectime#includealgorithm>usingnamespacestd;intN;intmatr2020;intd2040000=0;intgetmin(int*sum)inti二0;intmin二T,k;for

12、(;iN;i+)if(min0&&sumi0)|(sumi0&&sumimin)min=sumi;k=i;returnmin;voidgetJ(intjlist,intc,intn)inti=n-1,j;inttmp=1,result二0;while(!jlisti)i-;j=i-1;while(jlistj)j-;if(!jlistn-l)jlisti=0;jlisti+l=l;elseif(n-1-j=c)for(i=0;i<n;i+)jlisti=0;for(i=0;i<c+1;i+)jlisti=1;elseintk;k=n-1-j;whil

13、e(!jlistj)j;for(i=0;j+i<n;i+)jlistj+i=0;for(i=0;i<=k;i+)jlistj+i+1=1;intgetnextj(intj)intnextj二0;intc=0;intjlist20=0;inti=0;inttmp=1;while(j)if(j%2)C+；jlisti+=l;elsejlisti+=O;j/=2;getJ(jlist,c,NT);for(i=0;iNT;i+)if(jlisti)nextj+=tmp;tmp*=2;returnnextj;intmain(intargc,char*argv)freopen("d:

14、test_20.txt","r",stdin);inti,j;intmin;scanf("%d",&N);for(i=0;i<N;i+)for(j=0;j<N;j+)scanf("%d"，&matrij);intV20=0;for(i=0;i<N;i+)Vi=1;V0=0;for(i=1;i<N;i+)di0=matri0;for(j=1;j<pow(2,N-1)-1;j=getnextj(j)for(i=l;iN;i+)if(!(j&(1(i-1)intjlist20=

15、0;inttmpres20=0;intc=O,k=j,l;while(k)if(k%2)jlistc+=1;elsejlistc+=O;k/=2;c=0;for(l=0;l<N;l+)if(jlistl)tmpresc+=matril+1+dl+1j-(1<<l);dij=getmin(tmpres);inttmpres20=0;j=pow(2,N-1)-1;for(i=1;i<N;i+)tmpresi=matrOi+dij-(1<<(iT);min=getmin(tmpres);d02"(n-1)-1=minmatrOk+dk2“(nT)-2;d

16、02"(n-1)-1;printf("%dn",min);getchar();return0;3.4流程图3.5运行结果截图如下图4-1第四章物流配送网络为进一步说明该方法的有效性和实用性，先将该方法运用于某物流配送网络中：设某物流配送网络图由9个配送点组成，点A0为配送中心，A9为终点，试求自A9到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离70!912一阶段A0，第二阶段A1,A3,A5,A7，第三阶段A2,A4,A6,A8，显然两点之间直线路径小于折线路径阶段变量用k表示；状态变量Ak表示k阶段初可能的位置；决策f（Ak）表示k阶段初可能选

17、择的路线；由后向前逐步推移计算最优路径：当k=3时，由A2,A4,A6,A8到A9只有一条路线，故f3（A2）=16，f3A4=8,f381=4，f4）=14当k=2时，出发点有A1,A3,A5,A7三个，若从A1出发，只有一个选择，至A2，所以f2（A1）=27从A3出发，有两个选择，至A2,A4，所以f(A)=min<23d(A,A)+f(A)f5+1612C32、3/2、=min<=18d(A,A)+f(A)|10+8I23434丿从A5出发，有两个选择，至A4,A6，所以f(A5)=min<d(A,A)+f(A)2/54、3/4、,=min<d(A,A)+f(A

18、)I25636丿16*8=1915+4|从£出发，有两个选择，至A，A68，所以11 +4=1512 +14Id(A,A)+f(A)f(A)=min<272/76、3/6、,=min<d(A,A)+f(A)I27838丿最短路线是A7TA6TA9当k=l时，出发点有Ao一个，若从A。出发，至A1，所以f1(A0)=31若从A0出发，至A3，所以f1(A0)=25若从A0出发，至A5，所以f1(A0)=27若从A0出发，至A7，所以f1(A0)=24由上面计算得到最优路径f1(A0)=24，最优路径为A0TA7TA6TA9由本实例我们可以总结出动态规划的优越性所在：(1) 求解过程，结果清晰明了；(2) 能得到一组解，有利于分析结果；(3) 易于确定全局最优解；第五章结论本次课程设计不仅让我巩固了动态规划解决问题的思想以及方法,同时还让我学到算法中的知识得以很好地运用，很好地实现了学以致用。在这次课程设计中我学会了不少知识,这次动态规划来解决旅行售货员问题，这样很大程度上考验了学生对所学知识的扎实，深刻的理解以及需要很好地灵活运用动态规划是比较难理解但同时也是