




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、xxxxxxxx大学结课论文项目 动态规划算法解决旅行售货商问题课程名称: xxxxxxxxxxxxxx 院 系: xxxxxxxxxxxxxx 学生姓名: xxxxxx 学 号: xxxxxxxxx 指导教师: xxxxxx 2015年6月15日摘要:旅行商问题(TSP问题)时是指旅行家要旅行n个城市然后回到出发城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题,是图问题中最广为人知的问题。 动态规划 ( dynamic programming )算法 是解决 多阶段决策过程最优化问题 的一种常用方法,难度比较大,技巧性也很强。利用动态规
2、划算法,可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。本次课程设计运用动态规划解决旅行售货员问题,动态规划的基本思想是:把求解的问题分成许多若干阶段或许多子问题,然后按顺序求解各子问题。前一子问题的解,为后一子问题的求解提供了有用的信息,在求解任一子问题时列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。通过图的关系矩阵来表示个城市之间的关系,二维数组表示顶点之间的距离关系,对子问题进行求解比较,最后得出所求结果。关键字:旅行商问题 动态规划法 图 矩阵目录第一章 绪论1.1算法介绍1.2算法应用第二章
3、动态规划理论知识2.1动态规划的基本思想2.2动态规划设计步骤第三章 旅行售货员问题 3.1问题描述:旅行售货员问题3.2算法设计内容3.3算法分析3.4流程图第四章 物流配送网络第五章 结论第一章 绪论1.1算法介绍动态规划( dynamic programming )是解决多阶段决策过程最优化问题的一种数学方法。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-
8、1中。设数组dn2n-1存放迭代结果,其中dij表示从顶点i经过子集Vj中的顶点一次且仅一次,最后回到出发点0的最短路径长度。3.3算法分析假设从顶点i出发,令d(i,V)表示从顶点i出发经过V中各个顶点一次且仅一次,最后回到出发点i的最短路径的长度,开始时,V=V-i,于是,旅行商问题的动态规划函数为: d(i,V) = mincik + d(k,V-k) (kV) 1)d(k,) = cki (k i) 2)简单来说,就是用递归表达:从出发点0到1号点,假设1是第一个,则剩下的路程就是从1经过剩下的点最后回到0点的最短路径. 所以当V为空的时候, d(k,) = cki (k i), 找的
9、是最后一个点到0点的距离.递归求解1之后,再继续求V之中剩下的点,最后找出min.如果按照这个思想直接做,对于每一个i都要递归剩下的V中所有的点,所以这样的时间复杂度就近似于N!,其中有很多重复的工作.可以从小的集合到大的集合算,并存入一个二维数组,这样当加入一个节点时,就可以用到之前的结果,如四个点的情况:邻接矩阵:node01230 53215 79237 1232912 动态填表:表中元素代表第i个节点经过V集合中的点最后到0点的最短值.如果有多个值,取其中最小的一个.iVj01231,2(取min)1,3(取min)2,3(取min)1,2,3(
10、取min)0 c0i+div=2115 1011 c12+d23=21,c13+d32=24 2312 14 c21+d13=18,c23+d31=26 321415 c31+d12=19,c32+d21=24 这样一共循环(2(N-1)-1)*(N-1)次,就把时间复杂度缩小到O(N*2N )的级别.核心伪代码如下:for (i =1;i<n;i+) di0=ci0;for( j
11、=1;j<2(N-1)-1;j+) for(i=1 ; i<n ;i+)if(子集Vj中不包含i)对Vj中的每个元素k,计算diVj = mincik + dkVj-k | 每一个kVj;对V2(n-1)-1中的每个元素k,计算:d02(n-1)-1 = minc0k + dk2(n-1)-2;输出最短路径:d02(n-1)-1;具体代码如下:/ TravRoadD.cpp : Defines the entry point for the console application./#include "stdafx.h"#include "window
12、s.h"#include "math.h"#include <stdio.h>#include <ctime>#include <algorithm>using namespace std;int N;int matr2020; int d2040000=0;int getmin(int *sum)int i = 0;int min = -1,k;for(;i<N;i+)if(min < 0 && sumi>0) | (sumi>0 && sumi<min)min =
13、 sumi;k = i;return min;void getJ(int jlist, int c, int n)int i = n-1,j;int tmp = 1 , result = 0;while(!jlisti)i-; j = i-1;while(jlistj)j-;if(!jlistn-1)jlisti=0;jlisti+1=1;else if(n-1-j=c)for(i=0;i<n;i+)jlisti=0;for(i=0;i<c+1;i+)jlisti=1;else int k;k=n-1-j;while(!jlistj)j-;for(i=0;j+i<n;i+)j
14、listj+i=0;for(i=0;i<=k;i+)jlistj+i+1=1;int getnextj( int j )int nextj = 0;int c=0;int jlist20=0; int i=0;int tmp = 1;while(j)if(j%2)c+;jlisti+=1;elsejlisti+=0;j/=2;getJ(jlist,c,N-1);for(i=0;i<N-1;i+) if(jlisti)nextj += tmp;tmp *= 2;return nextj;int main(int argc, char* argv)freopen("d:tes
15、t_20.txt","r",stdin);int i,j;int min;scanf("%d",&N); for(i = 0; i < N; i+) for(j = 0;j < N; j+)scanf("%d",&matrij);int V20=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=1; i<N ;i
16、+)if(!(j & ( 1<<(i-1) )int jlist20=0; int tmpres20=0;int c=0,k=j,l;while(k)if(k%2)jlistc+=1;elsejlistc+=0;k/=2;c=0;for(l=0;l<N;l+)if(jlistl)tmpresc+=matril+1 + dl+1j-(1<<l);dij = getmin(tmpres);int tmpres20=0;j = pow(2,N-1)-1;for(i=1;i<N;i+)tmpresi=matr0i + di j - (1<<(i-
17、1) );min = getmin(tmpres);d02(n-1)-1 = minmatr0k + dk2(n-1)-2;d02(n-1)-1;printf("%dn",min);getchar();return 0;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)求得路径最小值。 J<n Y N 输出结果 结束3.5运行结果截图如下图4-1图
18、4-1第四章 物流配送网络为进一步说明该方法的有效性和实用性,先将该方法运用于某物流配送网络中:设某物流配送网络图由9个配送点组成,点为配送中心,为终点,试求自到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离首先根据网络图以及上面的建模方法我们可以将运输过程划分成三个阶段,分别为:第一阶段,第二阶段,第三阶段,显然两点之间直线路径小于折线路径阶段变量用k表示;状态变量表示k阶段初可能的位置;决策表示k阶段初可能选择的路线;由后向前逐步推移计算最优路径:当k=3时,由到只有一条路线,故=16,=8,=4,=14当k=2时,出发点有三个,若从出发,只有一个选择,至,所以=27从出发,有两个选择,至,所以从出发,有两个选择,至,所以从出发,有两个选择,至,所以最短路线是当k=1时,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 风光结合制氢项目前景分析报告
- 城区市政燃气管道升级改造初步设计方案
- 纺织工程师证书考试内容与试题及答案讲解
- 仪器 测试 合同协议书
- 精装合同协议书
- 护工中介合同协议书
- 工程项目经理合同协议书
- 后勤劳务外包合同协议书
- 排烟合同协议书
- 签了合同协议书
- 超星尔雅学习通《带您走进西藏》章节测试答案
- 施工监理投标报价单
- 阳江海上风电项目建议书
- 大学本科毕业设计毕业论文-网上药店管理系统的设计与实现
- DBJ∕T 13-264-2017 福建省石砌体结构加固技术规程
- ISO22000和ISO9001食品质量安全管理体系文件管理手册及程序文件合集(2020年版)
- T∕CGMA 081001-2018 整体式高速齿轮传动装置通用技术规范
- 湘少版级英语单词表吐血整理
- 配电房值班电工技能考核(答案)
- DR无损检测工艺规程
- SG30A伺服说明书
评论
0/150
提交评论