动态规划及其在求最短路径问题中的应用技巧.doc

计算机算法设计与分析 论文名：动态规划及其在求最短路径问题中的应用 班级：12医软一班 学号 姓名：张健 日期：2015年6月 动态规划及其在求最短路径问题中的应用 摘要：在概述动态规划原理的基础上，提出了动态规划数学模型建模主要步骤，并运用动态规划思想对最短路径进行求解，最后总结出动态规划在此类问题中的优越性。 关键字：动态规划；最短路径；多阶段决策。 在实践中有许多决策问题与时间有关系，决策过程分成若干阶段，各阶段的决策相互关联，共同决定最终的目标，这样的问题称之为多阶段决策问题。动态规划方法是解决多阶段决策过程最优化的一种方法。这一方法最初是由美国数学家R.Bellman等人在20世纪50年代提出的，实践证明许多问题用动态规划建模求解比用线性规划或非线性规划更加有效，特别是对离散性问题，运用解析数学无法解决，而动态规划就成为得力的工具。动态规划方法把一个比较复杂的问题分析为一系列同一类型的更容易求解的子问题先按照整体最优思想逆序求出各个可能状态的最优策略，然后顺序求出整个问题的最优策略和最优路径。由于将动态规划思想应用到求解运输问题的最短路径中，计算过程单一化便于应用于计算机，求解结果清晰明了，在实践应用中获得显著效果。 1 动态规划原理概述 动态规划最优化原理可以这样阐述：一个最优化策略不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸多策略必须构成最优策略，即其子策略总是最优的。任何思想方法都有一定的局限性，动态规划也有其适应的条件。如果某阶段的状态给定后，则在这阶段以后过程的发展不受这阶段以前各段状态的影响，这个性质称为无后效性，适用动态规划的问题必须满足这个性质；其次还须满足上述最优化原理。动态规划基本思想一是正确的写出基本的递推关系式和恰当的边界条件；二是在多阶段决策过程中，动态规划方法是即把当前一段和后来各阶段分开，又把当前效益和未来效益结合起来考虑的一种多阶段决策的最优化方法，每阶段决策和选取是从全局来考虑，与该段的最优选择的答案一般是不同的；三是在求整个问题的最优策略时，由于初始状态是已知的，儿每阶段的决策又都是该阶段状态的函数，因而最优策略所经过的各阶段状态便可逐次变换得到，从而确定最优路线。简而言之动态规划的基本思想就是把全局的问题化为局部的问题，为了全局最优必须局部最优。 2 动态规划建模主要步骤 用动态规划求解实际问题，首先要建立动态规划模型，需要进行以下的基本步骤： 第一步：正确划分阶段，确定阶段变量，将多阶段决策问题的实际过程，恰当的划分为若干个相互独立又相互联系的是需要做出一个决策的子问题。阶段通常是按决策进行的时间或空间上的先后顺序划分的，阶段变量用K表示。 第二步：确定状态，正确选择状态变量，在多阶段决策过程中，状态是描述研究问题过程的状况，表示每个阶段开始时所处的自然状况或客观条件。一个阶段有若干个状态， 用一个或一组变量来描述，状态变量必须满足两个条件：一是能描述过程的演变；二是满足无后效性，用表示第k个阶段的状态变量。 第三步：正确选择决策变量及允许的决策集合。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态做出的选择，而在实际问题中，决策变量的取值往往限制在某一范围内，此范围称之为允许决策集合。决策变量用表示；允许的决策集合是决策变量的取值范围用表示。 第四步：写出状态转换方程。状态转换方程的一般形式为=，这里的函数关系T因问题的不同而不同，如果给定第k个阶段的状态变量，则该阶段的决策变量一经确定第k+1阶段的状态变量的值也就可以确定。 第五步：列出指标函数。根据题意写出指标函数，指标函数常用表示。即 =,k=1,2，...，n。 它满足以下三个性质： a.它是定义在全过程及所有后部子过程上的数量函数； b.具有可分离性，切满足递推关系，即 =； c.函数关于变量要严格单调。 第六步：写出动态规划函数基本方程，用表示k-n阶段的最优策略函数： 3 应用举例 最短路径问题就是从某地出发，途径若干中间点最后到达目的地，要求找出路程或费用最小的路线。这类问题最容易想到的就是穷举法，即将所有的路线都找出来再作比较，对于中间点较少的最短路径问题是可行的，但随着中间点的增加，计算量也大大