算法分析与设计[动态规划].pptVIP

西南科技大学计算机学院软件教研室 第四章 动态规划 第四章 动态规划 什么是动态规划 多段图 最优二分检索树 0/1背包问题 可靠性设计 货郎担问题 在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶段后的行为都依赖于i 阶段的过程状态，而与i 阶段之前的过程是如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。 根据这类问题的多阶段决策的特性，提出了解决这类问题的“最优性原理”，从而创建了最优化问题的一种新的算法设计方法——动态规划。 什么是动态规划 在多阶段决策过程的每一个阶段，都可能有多种选择的决策，但必须从中选取一种决策。一旦各种阶段的决策选定之后，就构成了解决这一问题的一个决策序列。决策序列不同，导致的问题结果也不同。 动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。 最优性原理 最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提 1) 证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题 2) 获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。 多段图问题 多段图问题 多段图问题 多段图G＝(V, E)是—个有向图。它具有如下特性： 图中的结点被划分成k≥ 2个不相交的集合Vi ,1≤i≤k,其中V1和Vk分别只有一个结点s (源点) 和 t ( 汇点)。 图中所有的边u,v均具有如下性质：若u∈Vi ，则v ∈Vi+1 ,1≤i≤k,且每条边u, v均附有成本c(u, v)。 从s到t的一条路径成本是这条路径上边的成本和。 多段图问题(multistage graph problem)是求由s到t的最小成本路径。 多段图问题 最优性原理对多段图成立 假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径 再假设从源点s开始，已作出了到结点V2的决策，因此V2就是初始决策所产生的状态 如果把V2看成是原问题的一个子问题的初始状态，解决这个子问题就是找出一条由V2到t的最短路径 这条最短路径显然是v2,v3,…,vk-1,t 如果不是，设v2,q3,…,qk-1,t由V2到t的更短路径，则这条路径肯定比v2,v3,…,vk-1,t路径短，这与假设矛盾，因此最优性原理成立 0/1背包问题 背包问题中的xj限定只能取0或1值，用KNAP(1,j,X)来表示这个问题 最优化决策序列的表示 设S0是问题的初始状态。假定要作n次决策xi,1≤i≤n X1={r1,1,r1,2,…,r1,pj}是x1的可能决策值的集合，而S1,1是在选取决策值r1,j1以后所产生的状态， 1≤j1≤p1 又设F1,j1是相应于状态S1,j1的最优决策序列 则相应于S0的最优决策序列就是{r1,j1 F1,j1 | 1≤j1≤p1}中最优的序列，记作 最优化决策序列的表示 又设Xk={{rk,1,rk,2,…,rk,pk}是xk的可能值的集合。 Sk,jk是选取rk,jk决策之后所产生的状态, 1≤jk≤pk Fk,jk 是相应于Sk,jk的最优决策序列。 因此，相应于Sk-1的最优决策序列是 向前处理法(forward approach) 从最后阶段开始，以逐步向前递推的方式列出求前一阶段决策值的递推关系式，即根据xi+1,…,xn的那些最优决策序列来列出求取xi决策值的关系式，这就是动态规划的向前处理法 向后处理方法(backward approach)就是根据x1,…,xi-1的那些最优决策序列列出求xi的递推关系式。 多段图的向前处理和向后处理 0/1背包问题的向前处理和向后处理 4.2 多段图 多段图向前处理的算法 设P(i, j)是一条从Vi中的节点j 到汇点t 的最小成本路径，COST(i, j)表示这条路径的成本，根据向前处理方法有公式4.5： 因为，若j, t ∈E成立,有COST(k-1,j)=c(j,t),若j, t ∈E不成立，则有COST(k-1,j)=∞，所以可以通过如下步骤解式公式（4.5），并求出COST(1,s)。 首先对于所有j∈Vk-2，计算COST(k-2, j)，然后对所有的j∈Vk-3，计算计算COST(k-3, j)等等，最后计算出计算COST(1, s) 例子中5段图的 实现计算步骤： COST(4,9)=4 COST(4,10)=2 COS