动态规划求最短旅行路线

《动态规划求最短旅行路线》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、动态规划求最短旅行路线摘要：在我们日常生活和旅行中经常遇到求最短路径的问题，将动态规划思想运用到求解旅行问题最短路径屮，将过程划分为几个阶段，在每阶段屮选取最优策略，最后将找到整个过程的总体优化目标即最短路径。给出了动态规划方法的基本原理，尽力了动态规划数学模型，通过一个实际应用例子具体说明动态规划求解旅行问题最短路径过程，并总结出动态规划在此类问题中的优越性。关键词：动态规划，最短路径，多阶段决策，Matlab一、预备知识1.基本理论1.1动态规划基本思想动态规划［11是一种强有力的算法设计技术，它被广

2、泛用于求解组合最优化问题。这种方法是采用自底向上的方式递推求值，将待求解的问题分解成若干个子问题，先求解子问题，并把子问题的解存储起来以便以后用来计算所需要求的解。总言之，动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。动态规划基本步骤：(1)找出最优解的性质，并刻划其结构特征；(2)递归的定义最优值；(3)以自底向上的方式计算出最优值；(4)根据计算最优值时的信息，构造最优解。1.2多阶段决策过程分析多阶段决策m问题是根据问题本身的特点，将其求解的过程划分为若干个相互独立又相

3、互联系的阶段，在每一个阶段都需要做出决策，并且在一个阶段的决策确定以后再转移到下一个近阶段，在每一阶段选取其最优决策，从而实现整个过程总体决策最优的目的。适合用动态规划方法求解的问题是一类特殊的多阶段决策问题，具有“无后效性”的多阶段决策问题，一般具有以下特点：(1)可以划分成若干个阶段，问题的求解过程是对若干个阶段的一系列决策过程。(2)每个阶段有若干个可能状态。(3)一个决策将你从一个阶段的一种状态带到下一阶段的某钟状态。(4)在任一阶段，最佳的决策序列和该阶段以前的决策无关。(5)各阶段状态之间的转

4、换有明确定义的费用，而且在选择最佳决策时有递推关系(即状态转移方程)。二、动态规划求最短旅行路线2.1问题重述设某旅行者要从A点出发到终点B，他事先得到一张路线图如图1所示，各阶段距离如图上所标数值，旅行者沿着箭尖方向行走总能到达B点。试求出A到B点两点间的最短旅行路线及距离。2H3543342图1:旅游路线图1.2问题模型建立（两种方法）2.2.1逆序递推法模型首先根据网络图建立数学模型，我们可以将旅行过程划分成六个阶段。阶段便两用k表示；状态变量s。表示k阶段初可能的位置；决策~表示k阶段初可能选择的

5、路线；状态转移方程阶段指标表示k阶段与所选择的路段相应的路长；1表示第k阶段点~到终点层的旅行费用；递推公式乂=min{h+,」，k=6,5,4,3,2,1；•^表示最优决策；边界条件k=7时，。2.2.2Dijkstra算法模型求A到B点最短路，对于每个顶点，定义两个标记队44吻，其中：:表从起点A到v的一条路的权。z（v）:v的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终Mv）为从顶点A到B的最短的权。S：具有永久标号的顶点集输入：带权邻接矩阵W~，V）。2.3模型求解(两

6、种解法)2.3.1逆序递推法逆序递推方程为：k=6,5,4,3,2,1；A(^)=mm{d(sk,wa.)+A+1(+1)}/7Cv7)=0整个计算过程分六个阶段，从最后一个阶段开始直到第一阶段结束，利用Matlabf41最后求得最短路径⑵。最后求得：/l(^)=min{^(^C)+/2(C)^(^Z))+/2(D)}=min{l6J=16于是从A到B的最短路线为：A-〉C-〉F-〉J-〉M-〉O-〉B,其长度为16。matlab代码如下:a=[043infinfinfinfinfinfinfinfin

7、finfinfinfinf;...Inf0inf54infinfinfinfinfinfinfinfinfinfinf;...Infinf0inf73infinfinfinfinfinfinfinfinfinf;...Tnfinfinf0infinf21infinfinfinfinfinfinfinf;...Infinfinfinf0infinf12infinfinfinfinfinfinf;...infinfinfinfinf0infinf74infinfinfinfinfinf;...Infinfin

8、finfinfinf0infinfinf3infinfinfinfinf;...Infinfinfinfinfinfinf0infinf34infinfinfinf;...Tnfinfinfinfinfinfinfinf0infinf25infinfinf;...Infinfinfinfinfinfinfinfinf0infinf2infinfinf;...infinfinfinfinfinfinfinfinfinf0infi