文档介绍：*动态规划(dynamicprogramming)是运筹学的一个分支,是求解多阶段决策过程的最优化数学分支。动态规划的“动态性”主要体现在研究对象的时序性上。所谓多阶段决策问题是指这样一类活动过程:它可以分解为若干个相互联系的阶段,在每一阶段分别对应着一组可供选取的决策集合,即构成过程的每个阶段都需要进行一次决策的决策问题。*动态规划求解思路将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段决策问题,从而简化计算过程。*2347596810285121310710131128658854图8-21第1阶段第2阶段第3阶段第4阶段阶段:例如最短路问题:*动态规划问题具有以下基本特征:。阶段可以按时间划分,也可以按空间划分。“状态”与之对应。,选择不同的决策将会导致下一阶段不同的状态,同时,不同的决策将会导致这一阶段不同的目标函数值。,各子问题与原问题具有完全相同的结构。能否构造这样的递推归结,是解决动态规划问题的关键。这种递推归结的过程,称为“不变嵌入”。*,此阶段以后过程的发展不受此阶段以前各阶段状态的影响。*动态规划基本原理是将一个问题的最优解转化为求子问题的最优解,研究的对象是决策过程的最优化,其变量是流动的时间或变动的状态,最后到达整个系统最优。基本原理一方面说明原问题的最优解中包含了子问题的最优解,另一方面给出了一种求解问题的思路,将一个难以直接解决的大问题,分割成一些规模较小的相同子问题,每一个子问题只解一次,并将结果保存起来以后直接引用,避免每次碰到时都要重复计算,以便各个击破,分而治之,即分治法,是一种解决最优化问题的算法策略。动态规划求解可分为三个步骤:分解、求解与合并。*动态规划问题的求解有两种基本方法。逆序解法:从问题的最后一个阶段开始,逆多阶段决策的实际过程反向寻优。顺序解法:从问题的最初阶段开始,同多阶段决策的实际过程顺序寻优。B1B2B3C1C2D2C3D1E2533576155136334404743【例1】最短路径问题图8-1表示从起点A到终点E之间各点的距离。求A到E的最短路径。图8-1A第1阶段第2阶段第3阶段第4阶段阶段:6117811234Min{1+3,4+4}=4