算法分析与设计第六章1（动态规划）.ppt

第六章 动态规划;§6.1 一般方法;1）枚举法 穷举可能的决策序列，从中选取可以获得最优解的决策序列 2）动态规划 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法——动态规划。 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。; 过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的???态构成一个最优决策序列。;动态规划求解问题前提; 多段图问题的多阶段决策过程：生成从s到t的最小成本路径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1(1≤i≤k-2)中的哪个结点在从s到t的最短路径上。 ★ 最优性原理对多段图问题成立 假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径。 ● 初始状态：s ● 初始决策：(s,v2)， v2∈V2 ● 初始决策产生的状态：v2 则，其余的决策：v3,...,vk-1相对于v2将构成一个最优决策序列——最优性原理成立。 反证：若不然，设v2,q3,…,qk-1,t是一条由v2到t的更短的路径，则s, v2,q3,…,qk-1,t将是比s,v2,v3,…,vk-1,t更短的从s到t的路径。与假设矛盾。 故，最优性原理成立;例6.1.2 [0/1背包问题] KNAP(1,j,X) 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M) ;★ 最优性原理对0/1背包问题成立： 设y1,y2,…,yn是x1,x2,…,xn的0/1值最优序列。 ●初始状态： KNAP(1,n,M) ●初始决策：决定y1等于1还是等于0 ★ 若y1＝0, KNAP(2,n,M)是初始决策产生的状态。则y2,…,yn相对于KNAP(2,n,M)将构成一个最优序列。否则，y1,y2,…,yn将不是KNAP(1,n,M)的最优解 ★若y1＝1, KNAP(2,n,M-w1)是初始决策产生的状态。则y2,…,yn相对于KNAP(2,n,M－w1)将构成一个最优序列。 如若不然，设存在另一0/1序列z2,z3,…,zn,使得 且 则序列y1,z2,…,zn将是一个对于KNAP(1,n,M)具有更大效益值得序列。与假设矛盾。 故，最优性原理成立; 设 ● S0：问题的初始状态 ● n次决策：问题需要做n次决策 ● xi：i阶段的决策值，1≤i≤n。 设X1={r1,1,r1,2,…,r1,p1}是x1可选决策值的集合，S1,j1是在选择决策值r1,j1之后所产生的状态——“初始决策”所产生的状态。 设Γ1,j1是相应于状态S1,j1的最优决策序列。 则，相应于S0的最优决策序列就是{r1,j1Γ1,j1|1≤j1≤p1}中最优的序列，记为 ;s0; 若已经做了k-1次决策，1≤k-1＜n，设x1,x2,…,xk-1的最优决策值是r1,r2,…,rk-1，所产生的状态依次为S1,S2,…,Sk-1。 设Xk={rk,1,rk,2,…,rk,pk}是xk可能的决策值的集合，Sk,jk是在选择决策值rk,jk之后所产生的状态, 1≤jk≤pk。 Γk,jk是相应于状态Sk,jk的最优决策序列。 则，相应于Sk-1的最优决策序列是 相应于S0的最优决策序列为r1…rk-1rkΓk;sk-1;递推策略——向前处理法; 例6.1.3 利用向前处理法求解k段图问题 设 ∈V2，1≤j2≤p2,|V2|=p2; 是由 到t的最短路径，则s到t的最短路径是