下载文档原格式
第三章：动态规划3.1 动态规划的基本概念一、动态决策问题：决策过程具有阶段性和时序性(与时间有关)的决策问题。
即决策过程可划分为明显的阶段。
二、什么叫动态规划(D.P.–Dynamic Program)：多阶段决策问题最优化的一种方法。
广泛应用于工业技术、生产管理、企业管理、经济、军事等领域。
三、动态规划(D.P.)的起源：1951年,(美)数学家R.Bellman等提出最优化原理，从而建立动态规划，名著《动态规划》于1957年出版。
四、动态决策问题分类：1、按数据给出的形式分为：•离散型动态决策问题。
•连续型动态决策问题。
2、按决策过程演变的性质分为：•确定型动态决策问题。
•随机型动态决策问题。
五1、阶段(stage)n ：作出决策的若干轮次。
n = 1、2、3、4、5。
2、状态(state)S n ：每一阶段的出发位置。
构成状态集，记为S nS 1={A}，S 2={B 1,B 2,B 3}，S 3={C 1,C 2,C 3}，S 4={D 1,D 2,D 3}，S 5={E 1,E 2}。
阶段的起点。
3、决策(decision)X n ：从一个阶段某状态演变到下一个阶段某状态的选择。
构成决策集，记为D n (S n )。
阶段的终点。
D 1(S 1)={X 1(A)}={B 1,B 2,B 3}= S 2，D 2(S 2)={X 2(B 1),X 2(B 2),X 2(B 3)}={C 1,C 2,C 3}=S 3，D 3(S 3)={X 3(C 1),X 3(C 2),X 3(C 3)}={D 1,D 2,D 3}=S 4，D 4(S 4)={X 4(D 1),X 4(D 2),X 4(D 3)}={E 1,E 2}=S 5D 5(S 5)={X 5(E 1),X 5(E 2)}={F;F}={F}。
4、策略(policy)：全过程中各个阶段的决策Xn 组成的有序总体{Xn }。
如 A àB2àC1àD1àE2àF5、子策略(sub-policy)：剩下的n个阶段构成n子过程，相应的决策系列叫n子策略。
动态规划入门1(2008-09-20 21:40:51)第一节动态规划基本概念一，动态规划三要素：阶段，状态，决策。
他们的概念到处都是，我就不多说了，我只说说我对他们的理解：如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。
显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。
每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。
下面举个例子：要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。
每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。
一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。
经过这个例子相信大家对动态规划有所了解了吧。
下面在说说我对动态规划的另外一个理解：用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。
这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。
对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。
这样对图求最优路径就是动态规划问题的求解。
二，动态规划的适用范围动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：最优子结构（最优化原理）无后效性最优化原理在下面的最短路径问题中有详细的解答；什么是无后效性呢？就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。
动态规划（生产和存储问题）一、动态规划法的发展及其研究内容动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。
20世纪50年代初美国数学家R.E.BELLMAN等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，把多阶段问题转化为一系列的单阶段问题，逐个求解创立了解决这类过程优化问题的新方法——动态规划。
1957年出版的他的名著《Dynamic Proggramming》，这是该领域的第一本著作。
动态规划问世以来，在经济管理·生产调度·工程技术和最优控制等方面得到了广泛的应用。
例如最短路线·库存管理·资源分配·设备更新·组合·排序·装载等问题，采用动态规划法求解比用其他方法更为简便。
二、动态规划法基本概念一个多阶段决策过程最优化问题的动态规划模型通常包括以下几个要素：1．阶段阶段（stage）是对整个过程的自然划分。
通常根据时间顺序或是空间特征来划分阶段，对于与时间，空间无关的“静态”优化问题，可以根据其自然特征，人为的赋予“时段”概念，将静态问题动态化，以便按阶段的顺序解优化问题。
阶段变量一般用k=1.2….n.表示。
1.状态状态(state)是我们所研究的问题（也叫系统）在过个阶段的初始状态或客观条件。
它应能描述过程的特征并且具有无后效性，即当某阶段的状态给定时，这个阶段以后的过程的演变与该阶段以前各阶段的状态无关。
通常还要求状态是可以直接或者是间接可以观测的。
描述状态的变量称为状态变量（State Virable）用s 表示，状态变量的取值集合称为状态集合，用S表示。
变量允许取值的范围称为允许状态集合(set of admissble states).用x(k)表示第k阶段的状态变量，它可以是一个数或者是一个向量。
用X(k)表示第k阶段的允许状态集合。
n 个阶段的决策过程有n+1个状态变量，x(n+1)是x(n)的演变的结果。
动态规划算法一、基本概念动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。
一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
二、基本思想与策略基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。
在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。
依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
三、适用的情况能采用动态规划求解的问题的一般要具有3个性质：(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。
也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。
（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）四、求解的基本步骤动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。
这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。
如图所示。
动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态图1 动态规划决策过程示意图(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。
一个旅行者准备随身携带一个背包. 可以放入背包的物品有n 种, 每种物品的重量和价值分别为w j , v j .如果背包的最大重量限制是b , 怎样选择放入背包的物品以使得背包的价值最大?N,max11∈≤∑∑==j nj j j nj jjx b x w x v约束条件目标函数线性规划问题由线性条件约束的线性函数取最大或最小的问题整数规划问题线性规划问题的变量x j 都是非负整数3.3.2背包问题(Knapsack Problem)F k (y )：装前k 种物品,总重不超过y, 背包的最大价值i (k ,y )：装前k 种物品,总重不超过y, 背包达最大价值时装入物品的最大标号递推方程、边界条件、标记函数)()(0,0)0(,0,0)(})(),(max{)(11101<−∞=⎥⎦⎥⎢⎣⎢=≤≤=≤≤=+−=−y y F v w y y F n k F b y y F v w y F y F y F k k k k k k k 子问题划分、优化函数、标记函数⎩⎨⎧+−≤+−>=−−−k k k k kk k k k k V W y F y F kV W y F y F y i y i )()()()()()(111实例计算v1= 1, v2= 3, v3= 5, v4= 9,w1= 2, w2= 3, w3= 4, w4= 7,b= 10F k(y) 的计算表如下:k y12345678910 10112233445 20133466799 30135568101011 40135569101012在上例中, 求得i4(10)=4 ⇒x4≥1i4(10－w4)=i4(3)=2 ⇒x2≥1，x4=1, x3=0 i2(3－w2)=i2(0)=0 ⇒x2= 1，x1=0解x1=0, x2=1, x3=0, x4=1k y12345678910 10111111111 20122222222 30123333333 40123334344追踪问题的解算法TrackSolution输入：i k (y )表，其中k =1,2,…,n ，y =1,2,…,b 输出：x 1, x 2, … , x n ，n 种物品的装入量1. for j ←1 to n do 2. x j ←03. y ←b, j ←n 4. j ←i j (y )，5. x j ←16. y ←y −w j7. while i j (y )=j do 8. y ←y −w j 9. x j ←x j +110. if i j (y ) ≠0 goto 4追踪解x j 的算法X 的子序列Z ：设序列X , Z ,若存在X 的元素构成的严格递增序列使得，则称Z 是X 的子序列X 与Y 的公共子序列Z ：Z 是X 和Y 的子序列子序列的长度：子序列的元素个数>=<>=<k m z z z Z x x x X ,...,,,...,,2121><k i i i x x x ,...,,21k j x z j i j ,...,2,1,==相关概念3.3.3最长公共子序列LCS给定序列X =<x 1, x 2, … , x m >, Y =<y 1, y 2, … , y n >求X 和Y 的最长公共子序列实例蛮力算法：检查X 的每个子序列在Y 中出现每个子序列O (n ) 时间，X 有2m 个子序列，最坏情况下时间复杂度：O (n 2m )问题描述X : A B C B D A BY :BD C AB A最长公共子序列: B C B A子问题划分及依赖关系子问题边界：X和Y 起始位置为1，X的终止位置是i，Y 的终止位置是j，记作X i=<x1,x2,…,x i>，Y j=<y1,y2,…,y j>依赖关系：X=<x1,x2,…,x m>, Y=<y1,y2,…,y n>, Z=<z1,z2,…,z k>，Z 为X 和Y 的LCS，那么(1) 若x m=y n⇒z k=x m=y n,且Z k−1是X m−1与Y n−1的LCS；(2) 若x m≠y n, z k≠x m⇒Z是X m−1与Y 的LCS；(3) 若x m≠y n, z k≠y n⇒Z是X与Y n−1的LCS.满足优化原则和子问题重叠性令X 与Y 的子序列X i = <x 1, x 2, … , x i >，Y j = <y 1, y 2, … , y j > C [i ,j ]：X i 与Y j 的LCS 的长度递推方程标记函数：B [i, j ], 其值为字符↖、←、↑，分别表示C [i,j ]取得最大值时的三种情况⎪⎩⎪⎨⎧≠>−−=>+−−===j i ji yx j i j i C j i C y x j i j i C j i j i C ,0,]},1[],1,[max{,0,1]1,1[000],[若若或若递推方程、标记函数动态规划算法算法3.4LCS(X,Y,m,n)1. for i←1 to m do//行1-4边界情况2. C[i,0]←03. for i←1 to n do4. C[0,i]←05. for i←1 to m do6．for j←1 to n do7. if X[i]=Y[j]8. then C[i,j]←C[i−1,j−1]+19. B[i,j]←’É’10. else if C[i−1,j] ≥C[i,j−1]11. then C[i,j]←C[i−1,j]12. B[i,j]←’↑’13. else C[i,j]←C[i,j−1]14. B[i,j]←’←’利用标记函数构造解算法Structure Sequence(B, i, j)输入：B[i,j]输出：X与Y的最长公共子序列1. if i=0 or j=0 then return //一个序列为空2. if B[i,j] =“↖”3. then 输出X[i]4. Structure Sequence(B, i－1, j－1)5. else if B[i,j]=“↑”then Structure Sequence (B, i－1, j)6. else Structure Sequence (B, i, j－1)算法的计算复杂度计算优化函数和标记函数：时间为O(mn)构造解：每一步至少缩小X 或Y 的长度，时间Θ(m+n）空间：Θ(mn)实例输入：X=<A,B,C,B,D,A,B>, Y=<B,D,C,A,B,A>，标记函数：1234561B[1,1]= ↑B[1,2]= ↑B[1,3]= ↑B[1,4]=↖B[1,5]= ←B[1,6]=↖2B[2,1]=↖B[2,2]= ←B[2,3]= ←B[2,4]= ↑B[2,5]=↖B[2,6]= ←3B[3,1]= ↑B[3,2]= ↑B[3,3]=↖B[3,4]= ←B[3,5]= ↑B[3,6]= ↑4B[4,1]= ↑B[4,2]= ↑B[4,3]= ↑B[4,4]= ↑B[4,5]=↖B[4,6]= ←5B[5,1]= ↑B[5,2]= ↑B[5,3]= ↑B[5,4]= ↑B[5,5]= ↑B[5,6]= ↑6B[6,1]= ↑B[6,2]= ↑B[6,3]= ↑B[6,4]=↖B[6,5]= ↑B[6,6]=↖7B[7,1]= ↑B[7,2]= ↑B[7,3]= ↑B[7,4]= ↑B[7,5]= ↑B[7,6]= ↑解：X[2],X[3], X[4], X[6], 即B, C, B, A像素点灰度值:0∼255，表示为8位二进制数像素点灰度值序列: { p 1, p 2,…, p n }，p i 为第i 个像素点灰度值变位压缩存储格式: 将{ p 1, p 2,…, p n }分割m 段S 1, S 2, … ,S m i 段有l [i ]个像素，每个像素b [i ]位, h i 为该段最大像素的位数⎥⎤⎢⎡+=≤≤∈)1max log(,8][k Sp i i p h i b h ik约束条件：每段像素个数l [i ] ≤256段头11位：b [i ]的二进制表示(3 位) + l [i ]的二进制表示(8位)i 段占用空间：b [i ]×l [i ] + 11问题：给定像素序列{ p 1, p 2, …, p n }，确定最优分段，即3.3.4图像压缩为分段},...,,{)},11][][({min 211j ji TS S S T i l i b =+×∑=实例灰度值序列P={10,12,15,255,1,2,1,1,2,2,1,1}={10,12,15}，S2={255}, S3={1,2,1,1,2,2,1,1}分法1：S1={10,12,15,255,1,2,1,1,2,2,1,1}分法2：S1分法3：分成12组，每组一个数存储空间分法1：11×3+4×3+8×1+2×8=69分法2：11×1+8×12=107分法3：11×12+4×3+8×1+1×5+2×3=163结论：分法1是其中最优的分法递推方程设s [i ]是像素序列{p 1, p 2, … , p i }的最优分段所需存储位数⎥⎥⎤⎢⎢⎡+=++−+−=≤≤≤≤)1}{max log(),max(11)},1max(*][{min ][}256,min{1k j k i i k p j i b i k i b k k i s i s k*b max(i -k +1,i )位P 1P 2… P i-k P i-k +1 … P iS [i-k ]位k 个灰度算法设计算法Compress (P,n)//计算最小位数S[n]1.Lmax←256; header←11; S[0]←0//最大段长Lmax, 头header2. for i←1 to n do3. b[i]←length(P[i]) //b[i]是第i个灰度P[i]的二进制位数4. bmax←b[i] //3-6行分法的最后一段只有P[i]自己5. S[i]←S[i−1]+bmax6. l[i]←17. for j←2 to min{i,Lmax} do//最后段含j 个像素8. if bmax<b[i−j+1] //统一段内表示像素的二进制位数9. then bmax←b[i−j+1]10. if S[i]>S[i−j]+j*bmax11. then S[i]←S[i−j]+j*bmax12. l[i]←j13. S[i]←S[i]+header 时间复杂度T(n)=O(n)实例P = <10, 12, 15, 255, 1, 2>.S[1]=15, S[2]=19, S[3]=23, S[4]=42, S[5]=50l[1]=1, l[2]=2, l[3]=3,l[4]=1, l[5]=2 10121525512S[5]=50 1×2＋11 10121525512S[4]=42 2×2＋11 10121525512 S[3]=23 3×8＋11 10121525512 S[2]=19 4×8＋1110121525512S[1]=15 5×8＋11101215255126×8＋11追踪解算法Traceback(n,l)输入：数组l输出：数组C// C[j]是从后向前追踪的第j段的长度1. j←1 // j为正在追踪的段数2. while n≠0 do3. C[j]←l[n]4. n←n－l[n]5. j←j+1时间复杂度：O(n)。
