第四章动态规划第四章动态规划在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段，而且在任一阶段后的行为都依赖于i阶段的过程状态，而与i阶段之前的过程是如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。根据这类问题的多阶段决策的特性，提出了解决这类问题的“最优性原理”，从而创建了最优化问题的一种新的算法设计方法——动态规划。在多阶段决策过程的每一个阶段，都可能有多种选择的决策，但必须从中选取一种决策。一旦各种阶段的决策选定之后，就构成了解决这一问题的一个决策序列。决策序列不同，导致的问题结果也不同。动态规划的目标就是要在所有容许选择的决策序列中选取一个会获得问题最优解的决策序列，即最优决策序列。最优性原理多段图问题多段图问题多段图问题0/1背包问题最优化决策序列的表示最优化决策序列的表示向前处理法(forwardapproach)4.2多段图因为，若<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)=4COST(4,10)=2COST(4,11)=5COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=9COST(2,4)=18COST(2,5)=15COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16例子中5段图的实现计算步骤：在计算每一个COST(i,j)的同时，记下每个状态(结点j)所做出的决策，设为D(i,j)，则可容易地求出这条最小成本路径。D(3,6)=10D(3,7)=10D(3,8)=10D(2,2)=7D(2,3)=6D(2,4)=8D(2,5)=8D(1,1)=2设这条最小成本路径是s＝l,v2,v3,…,vk-1,t=12。则可得知：v2＝D(1,1)＝2，v3=D(2,D(1,1))=7和v4＝D(3,D(2,D(1,1)))＝D(3,7)＝10多段图的向前处理算法多段图的向后处理算法多段图的向后处理算法因为，若<1,j>∈E成立,BCOST(2,j)=c(1,j),若<1,j>∈E不成立，则有BCOST(2,j)=∞，所以可以通过如下步骤解式公式（4.6），首先对i＝3计算BCOST，然后对i＝4计算BCOST等，最后计算出BCOST(k，t)。BCOST(2，2)=9；BCOST(2，3)=7；BCOST(2，4)=3；BCOST(2，5)=2；111多段图的向后处理算法对于实例中的最小成本路径如下所示：D(3,6)=3;D(3,7)=2;D(3,8)=2;D(4,9)=6;D(4,10)=6;D(4,11)=8;D(5,12)=10多段图的向后处理算法4.3每对结点之间的最短路径4.4最优二分检索树二分检索树二分检索树最优二分检索树问题二分检索树二分检索树的预期成本二分检索树的预期成本最优二分检索树最优二分检索树最优二分检索树多阶段决策过程定义定义定义用动态归划求最优二分检索树用动态归划求最优二分检索树用动态归划求最优二分检索树用动态归划求最优二分检索树算法描述计算时间4.50/1背包问题0/1背包问题最优化原理证明0/1背包问题最优化原理证明0/1背包问题--解决方法0/1背包问题—解决方法0/1背包问题实例0/1背包问题实例0/1背包问题实例0/1背包问题实例0/1背包问题算法0/1背包问题实例0/1背包问题实例—图解法i=2:f1(X-3)+2i=3:f2(x-4)+50/1背包问题实例—图解法0/1背包问题实例0/1背包问题实例Si的推导过程Si的推导过程最优解序列的确定最优解序列的确定0/1背包问题DKP算法4.6可靠性设计可靠性设计(1)可靠性设计(2)可靠性设计(3)可靠性设计(4)4.7货郎担问题货郎担问题实例是否能用动态规划解决动态规划的解决方法货郎担问题实例货郎担问题实例货郎担问题实例货郎担问题实例4.8流水线调度问题两种可能的调度最优完成时间OFT调度最优调度排列具有的性质递推