《动态规划及其在求最短路径问题中的应用》由会员分享，可在线阅读，更多相关《动态规划及其在求最短路径问题中的应用（11页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析论文名：动态规划及其在求最短路径问题 中的应用班级：12 医软一班学号：姓名： 日期：2015年6月动态规划及其在求最短路径问题中的应用摘要：在概述动态规划原理的基础上，提出了动态规划数 学模型建模主要步骤，并运用动态规划思想对最短路径进行 求解，最后总结出动态规划在此类问题中的优越性。关键字：动态规划；最短路径；多阶段决策。在实践中有许多决策问题与时间有关系，决策过程分成若 干阶段，各阶段的决策相互关联，共同决定最终的目标，这 样的问题称之为多阶段决策问题。动态规划方法是解决多阶 段决策过程最优化的一种方法。这一方法最初是由美国数学 家 R.Bellman 等人在 20
2、世纪 50 年代提出的，实践证明许多 问题用动态规划建模求解比用线性规划或非线性规划更加 有效，特别是对离散性问题，运用解析数学无法解决，而动 态规划就成为得力的工具。动态规划方法把一个比较复杂的 问题分析为一系列同一类型的更容易求解的子问题先按照 整体最优思想逆序求出各个可能状态的最优策略，然后顺序 求出整个问题的最优策略和最优路径。由于将动态规划思想 应用到求解运输问题的最短路径中，计算过程单一化便于应 用于计算机，求解结果清晰明了，在实践应用中获得显著效 果。1 动态规划原理概述动态规划最优化原理可以这样阐述：一个最优化策略不论 过去状态和决策如何，对前面的决策所形成的状态而言，余 下的
3、诸多策略必须构成最优策略，即其子策略总是最优的。任何思想方法都有一定的局限性，动态规划也有其适应的条 件。如果某阶段的状态给定后，则在这阶段以后过程的发展 不受这阶段以前各段状态的影响，这个性质称为无后效性， 适用动态规划的问题必须满足这个性质；其次还须满足上述 最优化原理。动态规划基本思想一是正确的写出基本的递推 关系式和恰当的边界条件；二是在多阶段决策过程中，动态 规划方法是即把当前一段和后来各阶段分开，又把当前效益 和未来效益结合起来考虑的一种多阶段决策的最优化方法， 每阶段决策和选取是从全局来考虑，与该段的最优选择的答 案一般是不同的；三是在求整个问题的最优策略时，由于初 始状态是已知
4、的，儿每阶段的决策又都是该阶段状态的函 数，因而最优策略所经过的各阶段状态便可逐次变换得到， 从而确定最优路线。简而言之动态规划的基本思想就是把全 局的问题化为局部的问题，为了全局最优必须局部最优。2 动态规划建模主要步骤用动态规划求解实际问题，首先要建立动态规划模型，需要进行以下的基本步骤：第一步：正确划分阶段，确定阶段变量，将多阶段决策问 题的实际过程，恰当的划分为若干个相互独立又相互联系的 是需要做出一个决策的子问题。阶段通常是按决 策进行的时间或空间上的先后顺序划分的，阶段变量用 K 表 示。第二步：确定状态，正确选择状态变量，在多阶段决策过 程中，状态是描述研究问题过程的状况，表示每
5、个阶段开始 时所处的自然状况或客观条件。一个阶段有若干个状态， 用一个或一组变量来描述，状态变量必须满足两个条件：一 是能描述过程的演变；二是满足无后效性，用s表示第k个 k 阶段的状态变量。第三步：正确选择决策变量及允许的决策集合。决策的实 质是关于状态的选择，是决策者从给定阶段状态出发对下一 阶段状态做出的选择，而在实际问题中，决策变量的取值往 往限制在某一范围内，此范围称之为允许决策集合。决策变 量用 u 表示；允许的决策集合是决策变量的取值范围用 kD G )表示。kk第四步：写出状态转换方程。状态转换方程的一般形式为 s =T (s ,u )，这里的函数关系T因问题的不同而不同，如果
6、 k+1k k k给定第k个阶段的状态变量s，则该阶段的决策变量u一经 kk 确定第k+1阶段的状态变量s的值也就可以确定。第五步：列出指标函数。根据题意写出指标函数，指标函 数常用V表示。即k，nV =V G ,u ,s，,s ),k=l,2,，n。k, nk, n k k k +1n+1它满足以下三个性质：a. 它是定义在全过程及所有后部子过程上的数量函数；b. 具有可分离性，切满足递推关系，即v= 0 C , u ,V);k，n k k k k +1,nC.函数0 C ,u ,V 戾于变量V要严格单调。k k k k +1,nk +1,n第六步：写出动态规划函数基本方程，用f Q )表示
7、k-n k n +1阶段的最优策略函数：3 应用举例最短路径问题就是从某地出发，途径若干中间点最后到达 目的地，要求找出路程或费用最小的路线。这类问题最容易 想到的就是穷举法，即将所有的路线都找出来再作比较，对 于中间点较少的最短路径问题是可行的，但随着中间点的增 加，计算量也大大的增加了。例 1 某工厂需将一笔物资从 A 地发送到 F 地， A 地到 F 地之间的路线可以抽象成如下的线路图，其中节点A表示发 货地，节点 F 表示目的地，中间节点表示中转站，边线表示 可能路径，边线上的数值表示节点间的距离，问该工厂应该如何运送才能使路线最短?1卜匸 II”界2Ph；i| 七I图1 A地到F地的
8、网状路径图分析：首先根据网络图以及上节提到的建模方法，我们可 以将运输过程划分为五个阶段，即阶段变量k=l,2,3,4,5;设状 态变量s表示k阶段的起点；决策变量u表示k阶段的终点;kk状态转换方程为u = s ;阶段指标函数V表示k阶段与所k k +1k ,n选择的路段相应的路长；f（S）表示第k阶段点s到终点Fk kk的运输总距离；递推关系式为 f C I。f G Iminv +f ,k =5,4,3,2,1.k kk k+1下面利用表格进行计算，从最后一阶段开始向前递推：表1 k=5时计算过程表A (5)=V (is tFasfir11F22FXu：,EiE,4+1 = 52+2 =
9、44Di6+179+2-117卄1 = 85+2=77EtK=3时：利用第4阶段的数据推出本阶段（第3阶段）的结 果如下表。表3 k=3时计算过程表Vi Cui)=(*! tUa)+y(iu)ti3DDiGl + i = 55 + 812i5dCt4+7-116 + 7-1311DiG4 + 184 + 7=112 + 7=98K=2时：利用第3阶段的数据推出本阶段（第2阶段）的结 果如下表。表4 k=2时计算过程表XCiQCj仇3*El9+5 = 14 5+11-1614G民4 + 5 = 9 3+ll14 5 + 5 = 139G4+7=11 2+7=912CtA到F的最短路线为：A f
10、B f c f D f E f F ;2 112A到F的最短距离为：f (u )= 14。i i通过对上述实例运用动态规划的思想进行计算，我们发现 得到的不仅仅是由A点到F点的最短路线，而且还得到了从 所有各中间点出发到F点的最短路线，这就是说求出的不仅 是一个最优策略，而且是一族的最优策略，这对于许多实际 问题来讲是很有用的。在上述实例中只考虑了一个发货中心的应用实例，在实际 中有可能存在多个发货中心的情况，因此我们可以考虑假设 发货中心不是A点，而是B， B， B分别到F三条最短路123线，这样图1中的A点就是一个虚构点。对于这样的问题我 们可以这样考虑，我们将A点看成一个假想的“发货中心
11、” 如下图所示图2虚构A点后的网状路径图那么从A到B , A到B , A到B的距离就都是0,这样123我们仍然可以按照上例的计算过程进行计算，但只需计算到 k=2时就可以了，同样我们可以得到问题的结论：从B到F的最短路线为：B f C f D f E f F，最短距1 1112离为：14；从B到F的最短路线为：B f C f D f E f F，最短2 2 112距离为：9；从B到F的最短路线为：B f C f D f E f F，最短33221距离为：12。由本实例我们可以总结出动态优化思想的几点优越性：（1）计算过程单一化便于应用于计算机，求解结果清晰明了；（2）能得到一族解，有利于分析结果，进行推广应用；（3）易于确定全局最优解，并能利用经验提高求解效率。参考文献【1】钱颂迪，运筹学【M】北京：清华大学出版社，2002.【2】孙晓燕，李自良，彭雄凤等.利用动态规划求解运输问 题的最短路径【J】机械设计与制造，2010（2）： 223-224.【3】廖慧芳，邵小兵.动态规划算法的原理及应用【 J 】 .中 国科技信息，2005（21）：42.
