动态规划算法的应用
课程名称： | **************** |
院 系： ************************** |
2013年12月27日
1 第1页共16页
动态规划的应用
摘要：
旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。动态规划 （ dynamicprogramming ）算法是解决 多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。
本次课程设计运用动态规划解决旅行售货员问题，动态规划的基本思想是：把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问题。前一
各种可能的局部解，通过决策保留那些有可能达到最优的局部解， 丢弃其他局部子问题的解，为后一子问题的求解提供了有用的信息，在求解任一子问题时列出 |
解比较，最后得出所求结果。
关键字:旅行商问题动态规划法 图 矩阵
目录
第一章绪论...........................................................................................................11.算法介绍...............................................................................................................12.算法应用...............................................................................................................1第二章动态规划理论知识................................................................................2 2.1动态规划的基本思想..............................................................................2 2.2动态规划设计步骤..................................................................................2第三章旅行售货员问题.....................................................................................3
3.1 问题描述：旅行售货员问题................................................................3 |
第五章结论...........................................................................................................7参考文献..................................................................................................................8附件...........................................................................................................................9
第一章绪论
1.算法介绍
动态规划（dynamicprogramming）是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman（贝尔曼）等人根据一类多阶段决策问题的特性，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法——动态规划。
解决多阶段决策过程最优化问题，难度比较大，技巧性也很强。利用动态
规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。动 |
的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。
2.算法应用
动态规划在工程技术、管理、经济、工业生产、军事及现代控制工程等方面都有广泛的应用，而且由于动态规划方法有其独特之处，时，显得更加方便有效。由于决策过程的时间参数有离散的和连续的情况，故决 0
策过程分为离散决策过程和连续决策过程。这种技术采用自底向上的方式递推求
值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储
起来以便以后用来计算所需要求的解。简言之，动态规划的基本思想就是把全局
的问题化为局部的问题，为了全局最优必须局部最优。
第二章动态规划理论知识
2.1动态规划的基本思想
把求解的问题分成许多若干阶段或许多子问题，然后按顺序求解各子问 |
解。简言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了
全局最优必须局部最优。
2.2动态规划设计步骤
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干阶段。
这若干阶段一定要是有序的或可排序的（无后向性）。
（2）选择状态：将问题发展到各个阶段时所出现的各种客观情况用不
同的状态来表示出来。状态的选择要有无后向性。
1
（3）确定决策并写出状态转移方程：状态转移就是根据上一阶段的状 态和决策来导出本阶段的状态。
第三章旅行售货员问题
3.1 问题描述：旅行售货员问题 |
求出最小路程。
3.2算法设计内容
（1）不同城市的路线和距离都不一样。运用动态规划算法来设计本次课程设计，考虑到对问题进行阶段划分和状态的选择。使用Left函数实现V'-{k}的下标检索。
（2）根据遍历城市的各个阶段时所出现的情况并用不同的状态表示出来。当然这时的状态必须要满足无后向性。设计第一阶段则是各顶点为空，然后给赋值。 2
依次遍历各城市，在TSP函数中得以实现。
（3）假设4个顶点分别用0、1、2、3的数字编号，顶点之间的权值放在数组c[4][4]
中。首先按个数为1,2,3的顺序生成1,2,3个元素的子集存放在数组V[2n-1]中。设
数组d[n][2n-1]存放迭代结果，其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次
且仅一次，最后回到出发点0的最短路径长度。
3.3算法分析
在无向完全图中，对于任意两个顶点vj和vk，我们可以在多项式时间内找到vj
和vk这两个顶点之间的所有路径，选择其中路程最短的一条，令c[j,k]表示vj和
vk这两个顶点之间最短距离的那条路径。搜索路径c[j,k]，找到vj到达的在c[j,k]
上的第一个顶点，记该顶点为vi，递归查找vj到vi 和vi
3.4 流程图
开始
函数IsIncluded(intx,int array[3])判
断x是否包含在数组中。
函数Left(intk,int array[3],int
V[8][3])来实现V'-{k}的下标检索。
函数TSP(int d[4][8],int c[4][4],int V[8][3],int n)求得路径最小值。
3
J<n | Y | |
N |
| |
输出结果
结束
3.5运行结果截图如下图4-1
第四章物流配送网络
为进一步说明该方法的有效性和实用性，先将该方法运用于某物流配送网络中：
设某物流配送网络图由9个配送点组成,点 | A 0 | 为配送中心, | A 9 | 为终点,试求自 | A 9 |
到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离??
4
首先根据网络图以及上面的建模方法我们可以将运输过程划分成三个阶段，分别
为：第一阶段 | A 0 | ，第二阶段 | A A A A 1 3 5 7 | ，第三阶段 | A A A A 2 4 6 8 | ，显然两点之间直线 | |||||||||||||||||||||||||||||||||
路径小于折线路径阶段变量用k表示； | | ||||||||||||||||||||||||||||||||||||||
决策状态变量 | |||||||||||||||||||||||||||||||||||||||
当k=3时，由 | A A A A 2 4 6 8 | 到 | A 9 | 只有一条路线，故 | f | 3 | ? | A 2 | ? | =16， | f | 3 | ? | A 4 | ? | =8， | f | 3 | ? | A 8 | ? | =4， | |||||||||||||||||
f | 3 | ? | A 6 | ? | =14 | ||||||||||||||||||||||||||||||||||
当k=2时，出发点有 | A A A A 1 3 5 7 | 三个，若从 | A 1 | 出发，只有一个选择，至 | A 2 | ，所以 | f | 2 | ? | A 1 | ? | ||||||||||||||||||||||||||||
=27
从 | ? | A 3 | ? | A 3 | 出 | ?? ? ?? | d | 发 | ， | f | 3 | 有 | ? | ?? ? ?? | 两 | 个 | ????? | 选 | 择 | ， | 至 | A A 2 4 | ， | 所 | 以 | ||||||||
2 | ? | A A 3 2 | ? | ? | ? | A 2 | |||||||||||||||||||||||||||
?5 16 ? ?10?8 | |||||||||||||||||||||||||||||||||
f | 2 | ? | min | ? | min | ? | 18 | ||||||||||||||||||||||||||
d | 2 | ? | A A 3 4 | ? | ? | f | 3 | ? | A 4 | ? | 择 | ， | 至 | 以 | |||||||||||||||||||
从 | A 5 | 出 | 两 | 选 | |||||||||||||||||||||||||||||
发 | ， | 有 | 个 | ||||||||||||||||||||||||||||||
5
f | 2 | ? | A 5 | ? | ? | min | ?? ? ?? | d | 2 | ? | A A 5 | 4? | ? | f | 3 | ? | A 4 | ? | ?? ? ?? | ? | min | ?16 ? ?15 | ??? ?4? ?? | ? | 19 | ||||||||||||||||||||||
d | ? | A A 5 | 6? | ? | f | ? | A 6 | ? | |||||||||||||||||||||||||||||||||||||||
2 | 3 | ||||||||||||||||||||||||||||||||||||||||||||||
从 | A 7 | 出 | 发 | ， | 有 | 两 | 个 | 选 | 择 | ， | 至 | A A 6 8 | ， | 所 | 以 | ||||||||||||||||||||||||||||||||
f | 2 | ? | A 7 | ? | ? | min | ?? ? ?? | d | 2 | ? | A A 7 | 6? | ? | f | 3 | ? | A 6 | ? | ?? ? ?? | ? | min | ?11?4 ? ?12 14 | ????? | ? | 15 | ||||||||||||||||||||||
d | ? | 8? | ? | f | ? | ? | |||||||||||||||||||||||||||||||||||||||||
A A 7 | A 8 | ||||||||||||||||||||||||||||||||||||||||||||||
2 | 3 | ||||||||||||||||||||||||||||||||||||||||||||||
最短路线是 | A 7 | ? | A 6 | ? | A 9 | ||||||||||||||||||||||||||||||||||||||||||
当k=1时，出发点有 | A 0 | 一个，若从 | A 0 | 出发，至 | A 1 | ，所以 | f 1 | ? | A 0 | ? | =31 | ||||||||||||||||||||||||||||||||||||
若从 | A 0 | 出发，至 | A 3 | ，所以 | f 1 | ? | A 0 | ? | =25 | ||||||||||||||||||||||||||||||||||||||
若从 | A 0 | 出发，至 | A 5 | ，所以 | f 1 | ? | A 0 | ? | =27 | ||||||||||||||||||||||||||||||||||||||
若从 | A 0 | 出发，至 | A 7 | ，所以 | f 1 | ? | A 0 | ? | =24 | ||||||||||||||||||||||||||||||||||||||
由上面计算得到最优路径f 1?A 0?=24，最优路径为A 0?A 7?A 6 | ? | A 9 | |||||||||||||||||||||||||||||||||||||||||||||
(3)易于确定全局最优解； | |||||||||||||||||||||||||||||||||||||||||||||||
第五章结论
本次课程设计不仅让我巩固了动态规划解决问题的思想以及方法，同时还让
我学到算法中的知识得以很好地运用，很好地实现了学以致用。在这次课程设计 |
6
却要动态规划来解决旅行售货员问题，这样很大程度上考验了学生对所学知识的扎实，深刻的理解以及需要很好地灵活运用
动态规划应该在本册书中是比较难理解但同时也是很重要的一种算法思想。“分阶段逐步求优”是其核心思想，在设计算法时，不同城市之间路径有多种，每种路径的距离都不相同，这就需要对城市进行遍历，以便求得最佳路径。在这次课程设计中也遇到不少问题，比如在算法设计中怎样去记录所求得的路径，还有在程序调试中for循环中的大括号范围问题，但这些问题最后都一一解决了，很好地完成了本次课程设计。
7
参考文献
[1]算法设计与分析（第二版）吕国英 主编 清华大学出版社
[2]算法设计与分析 王红梅 胡明 编著 清华大学出版社2006
[3]算法基础 GillesBrassard，PaulBratley 著.邱仲潘，等译清华大学出版社， 2010
[4]算法之道邹恒明 机械工业出版社 2010
8
附件
程序实现代码
#include<stdio.h>
intIsIncluded(int x,int array[3])//x 是否包含在数组中
{
if((array[0]!= x) && (array[1] != x) && (array[2] != x))
return0;
return1;
}
intLeft(int k,int array[3],int V[8][3])//实现V'-{k}的下标检索
{
inti = 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; |
{
if(temp[i]== 0)
array_0_count++;
elseif(temp[i] == 1)
array_1_count++;
elseif(temp[i] == 2)
array_2_count++;
else
array_3_count++;
}
for(index= 0; index < 8; index++)
{
for(i=0;i < 3; i++)
{
if(V[index][i] == 0) |
|
9
V_1_count++;
elseif(V[index][i] == 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)) returnindex;
V_0_count= 0;
V_1_count= 0;
V_2_count= 0;
V_3_count= 0;
}
return0;
}
voidTSP(int d[4][8],int c[4][4],int V[8][3],int n)
{
inti = 0,j = 0,k = 0;
for(i = 1; i < n; i++)//V'为空时，给赋值， |
for(k= 0; k < 3; k++)//分别试探集合中的每一点，取最小值 {
if((V[j][k]!= 0) && ((c[i][V[j][k]] + d[V[j][k]][Left(V[j][k],V[j],V)])< d[i][j])) d[i][j]= c[i][V[j][k]] + d[V[j][k]][Left(V[j][k],V[j],V)];
}
}
}
}
for(k= 0; k < 3; k++)//分别试探下一步为集合中的任何一点，取最小值
{
if((V[7][k]!= 0) && (c[0][V[7][k]] + d[V[7][k]][Left(V[7][k],V[7],V)]) <d[0][7]) d[0][7]= c[0][V[7][k]] + d[V[7][k]][Left(V[7][k],V[7],V)];
printf("%d->",V[j][k]);
} | } | |
printf("0\n"); | ||
|
10
voidmain()
{
intV[8][3]=
{
0,0,0,
0,0,1,
0,0,2,
0,0,3,
0,1,2,
0,1,3,
0,2,3,
1,2,3
};
intc[4][4]=
{
0,3,7,5,
4,0,2,4,
5,4,0,2,
3,5,6,0
}; |
printf("所求的最小路程是:%d\n",d[0][7]);
}
11
指导教师评语：
1、文档：
a、内容： | 不完整□ | 完整 | □ | 详细 | □ | ||
b、方案设计： 较差 □ | 合理 | □ | 非常合理□ | ||||
c、实现： | 未实现□ | 部分实现□ | 全部实现□ | ||||
d、文档格式： 不规范□ | 基本规范□ | 规范 | □ | ||||
2、答辩：
a、未能完全理解题目，答辩情况较差 □
b、部分理解题目，部分问题回答正确 □ | ||
答辩成绩： | ，占总成绩比例： | 60% |
总成 绩：
指导教师签字：
年 | 月 | 日 |
12