动态规划多阶段决策问题的求解方法

1、动态规划_多阶段决策问题的求解方法1构造状态网络；：一:解决多阶段决策最优化的过程为动态规划方法在程序设计中， 有一类活动的过程，由于它的特殊性，可将过程2.根据状态转移尖系和状态转移方程 建立最优值的分成若干个互相联系的阶段，在它的每一阶段都需要做出决策，从而3. 按阶段的先后次序计算每个状态的最优值。使整个过程达到最好 的活动效果。因此各个 阶段决策的选取不能任逆向思维法是指从问题目标状态出发倒推回初始意确定，它依赖 于当前面临的状态，又影响以后的发展。当各个阶段 态的思维方法。动态规划的逆向思 维法的要点可归纳为以决策确定后，就组成一个决策序列，因而也就确定了整个过程的 一条1.分析最优

2、值的结构,刻画其结构特征；活动路线。这种把一个问题看作是一个 前后尖联具有链状结构的多2 递归地定义最优值；阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。3按自 底向上或自顶向下记忆化的方式计算最优在多阶段决策问题中，各个阶段采取的决策， 一般来说是与时间有尖的，决策依赖于当前状态，又随即引起状态的转移，一个决策序 列如果原问题可 以分解成几个本质相同、规模较小的就是在变化的状态中产生出来的，故有”动态”的含 义，我们称这种就会联想到从逆向思维的角度寻求问题的解决。一般解决多阶段决策最 优化的过程为动态规划方法。策问题多采用动态规划逆向思维方 法解决。二、举:二： 动态规划最优化原

3、理pascal语例说明本文以信息学奥赛用语言一一最优化原理是动态 规划的基础。任何一个问题，如果失去了这言为编程个最优化原理的支持，就不可能用 动态规划方法计算。这个“最优化说明，其他编程语言编写方法相同，语句类似。原 理”如果用数学化一点的语言来描述的话，就是:假设为了解决某：一：问题描述一优 化问题，需要依次作出n个决策D1，D2, , Dn,如若这个决策设有N个不相同的整数组成的数列，记为：序列是最优的，对于任何一个整数k，1 v k v n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即 ()且？ ？ al a2 an aiajij以后的决策Dk+1，D

4、k+2 Dn也是最优的。作为整个过程的 最优 例如 3，18，7，14，10，12, 23, 41，16, 24策略具有这样的性质：即无论过去的状态 和决策如何，对以前的决策 若存在i1<i2 <ie且有ai1<ai2 <aie则 称为长度序列。如上例中3,18,23,24就是一个长度为4的不下也有3，7，10，12，16, 24长度为6的不下降序列。程序>»»»»若an-1<an则存在长度为2的不下降序列an-1 , an。begink:=j;l:=aj,2; (2)若an-1>an则存在长度为1的不下降序列a

5、n-1或anend; 3( 一般若从ai开始，此时最长不下降序列应该按下列方法求出：ifl>0 then在ai+1 , ai+2 , an中，找出一个比ai大的且最长的不下降序begin >作为它的后继。4(为算法上的需要，定义一个数组:ai,2:=l+1;a:array1.3of in teger; ai,3:=k; ai,1表不 a*e nc* 同丘表不从i位置到达n的最长不下降序列长度end; ai,3表示从i位置开始最长不下降序列的 下一个位置amax:=a1,2;初始化:for i:=1 to n do l:=1; ()begin readai,1 ;ai,2:=1 ;a

6、i,3=0for j:=2 to n-1 doend; if ai,2>amax the n下面给出求最长不下降序列的算法:beginfor i:=n-1 dow nto 1 do amax:=ai,2;beg in l:=i; end;I:=1 ;k:=0; ()writelnamax:3; for j:=i+1 to n do while loO do if aj,1>ai,1and aj,2>l then begin k:=j;l:=aj,2end; beginif l>0 then ()write al,1:3;begin l:=al,3; ai,2:=l+1;

7、 end;ai,3:=k; end.end : 23:运行结果end; 6下面找出最长不下降序列，并排序列:3 7 10 12 23 41多阶段决策问题典型 题目很多，篇幅限制，在amax:=a1,2;l:=1;此不一一举例。三、动态规划解题的好 处及注意事项：一:动态规划解题的好处for j:=2 to do动态规划的最大优势在于它具有极高的效率5而且动态规划还if ai,2>amax thenbegin有其他的优势，例如：动态规划可以得出一系列解，算法清晰简便，程amax:=ai,2;序易编、易调，等等。动态规划是研究一类最优化问题的方法，在经l：=i；济、工程技术、企业管理、工农业

8、生产及军事等领域中都有广泛 的应(end;用。近年来，在ACM/ICPC中，使用动态规划或部分应用动态规划)最长不下降序列长度为amax,2)思维求解的题不仅常见，而且形式也多种多 样。而在与此相近的各类信息学竞赛中，应用动态规划解题已经成为一种趋势，这和动态规序列whileloO dobegin划的优势不无尖系。() write al,1:3;:二:动态规划解题的注意事项1 (动态规划它只适于解决一定条件的最优策略问题，利用动态l：=al,3;规划解题，阶段的划分是尖键，必须依 据题意分析，寻求合理的划分end;()阶段子问题方法。而每个子问题是 个比原问题简单得多的优化：三：参考程序问题。

9、而且每个子问题的求解中，均利用它的一个后部子问题的最 （）program buxiajia ngin put,output;优化结果，直到最后一个子问题所得最优解，它就是原问题的最优解。const n=10; 2 （应指出，动态规划是考察求解多阶段决策问题的途径和方法，vara:array1. n,1 .3of in teger;但它不像线性规划那样，具有一个标准的数学表达式和明确定义的一组规划。因此我们在学习时，除了要对基本概念和方法正确理解 i,k,l,j,amax:i nteger; 夕卜，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创begin造性的技巧去求解。for i=1 to n do 3.动态规划是运筹学 的一个分 支。许多隐式图上的算法，例如求begin单源最短路径的Dijkstra算法、广度优先搜索 算法，都渗透着动态规（）readai,1;划的思想。还有许多数学问题，表面上看起来与动态规划风马牛不ai,2:=1;相及，但是其求解思想与动态规划是完全一致的。ai,3:=0;end;for i:=n-1 dow nto 1 dob