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

动态规划算法的应用课程名称： * 院 系： * 学生姓名： * 学 号： * 专业班级： *指导教师： * 2013年12月27日第 1 页 共 16 页1动态规划的应用摘要：旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。 动态规划 （ dynamic programming ）算法 是解决 多阶段决策过程最优化问题 的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。本次课程设计运用动态规划解决旅行售货员问题，动态规划的基本思想是：把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。通过图的关系矩阵来表示个城市之间的关系，二维数组表示顶点之间的距离关系，对子问题进行求解比较，最后得出所求结果。关键字:旅行商问题 动态规划法 图 矩阵目录第一章 绪论11.算法介绍12.算法应用1第二章 动态规划理论知识22.1动态规划的基本思想22.2动态规划设计步骤2第三章 旅行售货员问题3 3.1问题描述：旅行售货员问题33.2算法设计内容33.3算法分析33.4流程图4第四章 物流配送网络5第五章 结论7参考文献8附件9第一章 绪论1.算法介绍动态规划（ dynamic programming ）是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman（贝尔曼）等人根据一类多阶段决策问题的特性，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法动态规划。 解决多阶段决策过程最优化问题，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解； 对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解 。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。2.算法应用 动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用，而且由于动态规划方法有其独特之处，在解决某些实际问题时，显得更加方便有效。由于决策过程的时间参数有离散的和连续的情况，故决策过程分为离散决策过程和连续决策过程。这种技术采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。第2章 动态规划理论知识2.1动态规划的基本思想把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。2.2动态规划设计步骤（1） 划分阶段：按照问题的时间或空间特征，把问题分为若干阶段。这若干阶段一定要是有序的或可排序的（无后向性）。（2） 选择状态：将问题发展到各个阶段时所出现的各种客观情况用不同的状态来表示出来。状态的选择要有无后向性。（3） 确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。第三章 旅行售货员问题3.1问题描述：旅行售货员问题某售货员要到若干城市去推销商品，已知各城市之间的路程。他要选定一条从驻地出发，经过每一个城市一遍，最后回到驻地的路线，使总的路程最小，并求出最小路程。3.2算法设计内容（1） 不同城市的路线和距离都不一样。运用动态规划算法来设计本次课程设计，考虑到对问题进行阶段划分和状态的选择。使用Left函数实现V-k 的下标检索。（2） 根据遍历城市的各个阶段时所出现的情况并用不同的状态表示出来。当然这时的状态必须要满足无后向性。设计第一阶段则是各顶点为空，然后给赋值。依次遍历各城市，在TSP函数中得以实现。（3） 假设4个顶点分别用0、1、2、3的数字编号，顶点之间的权值放在数组c44中。首先按个数为1,2,3的顺序生成1,2,3个元素的子集存放在数组V2n-1中。设数组dn2n-1存放迭代结果，其中dij表示从顶点i经过子集Vj中的顶点一次且仅一次，最后回到出发点0的最短路径长度。3.3算法分析在无向完全图中，对于任意两个顶点vj和vk，我们可以在多项式时间内找到vj和vk这两个顶点之间的所有路径，选择其中路程最短的一条，令cj,k表示vj和vk这两个顶点之间最短距离的那条路径。搜索路径cj,k，找到vj到达的在cj,k上的第一个顶点，记该顶点为vi，将其记录在数组中d，递归查找vj到vi和vi到vj的最短路径及其相应权值，最后将数组d中的权值之和输出出来即为所求。3.4流程图 开始函数IsIncluded(int x,int array3)判断x是否包含在数组中。函数Left(int k,int array3,int V83)来实现V-k 的下标检索。函数TSP(int d48,int c44,int V83,int n)求得路径最小值。 Jn Y N 输出结果 结束3.5运行结果截图如下图4-1图4-1第四章 物流配送网络为进一步说明该方法的有效性和实用性，先将该方法运用于某物流配送网络中：设某物流配送网络图由9个配送点组成,点为配送中心,为终点,试求自到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离首先根据网络图以及上面的建模方法我们可以将运输过程划分成三个阶段，分别为：第一阶段，第二阶段，第三阶段，显然两点之间直线路径小于折线路径阶段变量用k表示；状态变量表示k阶段初可能的位置；决策表示k阶段初可能选择的路线；由后向前逐步推移计算最优路径：当k=3时，由到只有一条路线，故=16，=8，=4，=14当k=2时，出发点有三个，若从出发，只有一个选择，至，所以=27从出发，有两个选择，至，所以从出发，有两个选择，至，所以从出发，有两个选择，至，所以最短路线是当k=1时，出发点有一个，若从出发，至，所以=31若从出发，至，所以=25若从出发，至，所以=27若从出发，至，所以=24由上面计算得到最优路径=24，最优路径为由本实例我们可以总结出动态规划的优越性所在：(1)求解过程，结果清晰明了；(2)能得到一组解，有利于分析结果；(3)易于确定全局最优解；第五章 结论本次课程设计不仅让我巩固了动态规划解决问题的思想以及方法，同时还让我学到算法中的知识得以很好地运用，很好地实现了学以致用。在这次课程设计中我学会了不少知识，旅行售货员问题在书上本来是用回溯法来求解的，但这次却要动态规划来解决旅行售货员问题，这样很大程度上考验了学生对所学知识的扎实，深刻的理解以及需要很好地灵活运用动态规划应该在本册书中是比较难理解但同时也是很重要的一种算法思想。“分阶段逐步求优”是其核心思想，在设计算法时，不同城市之间路径有多种，每种路径的距离都不相同，这就需要对城市进行遍历，以便求得最佳路径。在这次课程设计中也遇到不少问题，比如在算法设计中怎样去记录所求得的路径，还有在程序调试中for循环中的大括号范围问题，但这些问题最后都一一解决了，很好地完成了本次课程设计。参考文献1 算法设计与分析（第二版） 吕国英 主编 清华大学出版社2 算法设计与分析 王红梅 胡明 编著 清华大学出版社20063 算法基础 Gilles Brassard，Paul Bratley著.邱仲潘，等译 清华大学出版社，20104 算法之道 邹恒明 机械工业出版社 2010附件程序实现代码#include int IsIncluded(int x,int array3)/x是否包含在数组中 if(array0 != x) & (array1 != x) & (array2 != x) return 0; return 1; int Left(int k,int array3,int V83)/实现V-k 的下标检索 int i = 0,index = 0,array_0_count = 0,array_1_count = 0,array_2_count = 0,array_3_count = 0; int V_0_count = 0,V_1_count = 0,V_2_count = 0,V_3_count = 0; int temp3; for(i = 0; i 3; i+) tempi = arrayi; for(i = 0; i 3; i+) if(tempi = k) tempi = 0; /相当于去掉k这个城市 for(i = 0; i 3; i+) if(tempi = 0) array_0_count+; else if(tempi = 1) array_1_count+; else if(tempi = 2) array_2_count+; else array_3_count+; for(index = 0; index 8; index+) for(i=0; i 3; i+) if(Vindexi = 0) V_0_count+; else if(Vindexi = 1) V_1_count+; else if(Vindexi = 2) V_2_count+; else V_3_count+; if(array_0_count = V_0_count) & (array_1_count = V_1_count) & (array_2_count = V_2_count) & (array_3_count = V_3_count) return index; V_0_count = 0; V_1_count = 0; V_2_count = 0; V_3_count = 0; return 0; void TSP(int d48,int c44,int V83,int n) int i = 0,j = 0,k = 0; for(i = 1; i n; i+)/V为空时，给赋值， di0 = ci0; for(j = 1; j 7; j+)/按列遍历不同集合，1,2,3,1,2,1,3. for(i = 1; i n; i+)/遍历城市1，2，3 if( !IsIncluded(i,Vj) )/i必须不在集合中，否则就属于经过两次，不符合题意 for(k = 0; k 3; k+)/分别试探集合中的每一点，取最小值 if(Vjk != 0) & (ciVjk + dVjkLeft(Vjk,Vj,V) dij) dij = ciVjk + dVjkLeft(Vjk,Vj,V); for(k = 0; k 3; k+)/分别试探下一步为集合中的任何一点，取最小值 if(V7k != 0) & (c0V7k + dV7kLeft(V7k,V7,V) ,Vjk); printf(0n); void main() int V83= 0,0,0, 0,0,1, 0,0,2, 0,0,3, 0,1,2, 0,1,3, 0,2,3, 1,2,3 ; int c44= 0,3,7,5, 4,0,2,4, 5,4,0,2, 3,5,6,0 ; int d48=0,i=0,j=0; printf(所求的最佳路径是：);printf(0-); for(i=0; i4; i+) for(j=0; j8; j+) dij=1000; /假设10