第3章 动态规划2

1、13.2 动态规划算法的基本要素动态规划算法的基本要素 Elements of Dynamic Programming 1 最优子结构性质最优子结构性质 Optimal Substructure 2 重叠子问题性质重叠子问题性质 Overlapping Subproblems 21. 最优子结构最优子结构 Optimal Substructure 当问题的最优解包含了其子问题的最优解当问题的最优解包含了其子问题的最优解时，称该问题具有时，称该问题具有最优子结构性质最优子结构性质。 分析最优子结构性质时，一般假设由问题分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后的最优

2、解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。比原问题更优解更好的解，从而导出矛盾。3.2动态规划算法的基本要素动态规划算法的基本要素32.重叠子问题重叠子问题 Overlapping Subproblems 在用递归算法自顶向下解此问题时，每次在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问产生的子问题并不总是新问题，有些子问题被反复计算多次。题被反复计算多次。 动态规划算法对每个问题只解一次，而后动态规划算法对每个问题只解一次，而后将其解保存在一个表格中，当再次需要解将其解

3、保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。此问题时，用常数时间查看一下结果。 因此，用动态规划算法通常只需要多项式因此，用动态规划算法通常只需要多项式时间。时间。动态规划算法的基本要素动态规划算法的基本要素3.2动态规划算法的基本要素动态规划算法的基本要素43.备忘录方法备忘录方法Memoization 用一个表格来保存已解决的子问题的答案，用的用一个表格来保存已解决的子问题的答案，用的时候查表即可。时候查表即可。 采用的递归方式是采用的递归方式是自顶向下自顶向下，动态规划是，动态规划是自底向自底向上。上。 初始化为每个子问题的记录存入一个特殊的值，初始化为每个子问题的记

4、录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问果是特殊值，表示未求解，否则只要取出该子问题的解答即可。题的解答即可。动态规划算法的基本要素动态规划算法的基本要素3.2动态规划算法的基本要素动态规划算法的基本要素5备忘录方法解矩阵乘备忘录方法解矩阵乘int MemoizedMatrixChain(int n,int *m,int *s) for(int i=1;i=n;i+) for(int j=i;j0) return mij; if(i=j) return 0; int u=LookupCha

5、in(i,i)+LookupChain(i+1,j) +pi-1*pk*pj; sij=i; for(int k=i+1;kj;k+) int t=LookupChain(i,k) +LookupChain(k+1,j) +pi-1*pk*pj; if(tT( S, b(1) )，设设 是作业集是作业集S在机器在机器M2等待时等待时间间b(1)时的一个最优调度，则时的一个最优调度，则(1),(2), (n)是是N的一个调度。的一个调度。 该调度所需的时间为该调度所需的时间为a(1) + T( S, b(1) ) ai等待时间等待时间t= t ai + biM1M2t ai流水作业调度流水作业调

6、度t=aiaiajtbibjtbibjttbibibjbj3.3流水作业调度流水作业调度19 如果调换如果调换i，j的加工顺序，则得到另一调度，它的加工顺序，则得到另一调度，它的加工时间变为的加工时间变为jit流水作业调度流水作业调度考虑对于相同的考虑对于相同的 ai, aj, bi, bj，不同的加工顺序导致，不同的加工顺序导致剩余任务的等待时间剩余任务的等待时间tij与与tji的大小关系。的大小关系。3.3流水作业调度流水作业调度20 称作业i和j满足Johnson不等式，如果作业i和j不满足Johnson不等式，则交换作业i和作业j的加工顺序后，他们满足Johnson不等式。 交换作业的

7、加工顺序后，它需要的加工时间为：),/(),(jijitjiSTaatsT如果作业如果作业i和和j满足满足 ,maxjjjiijijjiabaataabbt流水作业调度流水作业调度3.3流水作业调度流水作业调度21如果作业如果作业i和和j满足满足Johnson不等式不等式流水作业调度流水作业调度则则3.3流水作业调度流水作业调度22Johnson法则的调度法则的调度 对于流水作业调度问题，必存在一个最优对于流水作业调度问题，必存在一个最优调度调度，使得，使得(i)和和(i+1)满足满足Johnson不等不等式式 minb (i) ,a (i+1)minb (i+1) ,a(i) minb (i

8、) ,a (j)minb (j) ,a(i) ij 流水作业调度流水作业调度3.3流水作业调度流水作业调度23Johnson算法算法流水作业调度流水作业调度考虑这样构成的调考虑这样构成的调度一定满足度一定满足Johnson法则吗？法则吗？3.3流水作业调度流水作业调度24算法描述算法描述流水作业调度流水作业调度int FlowShop( int n, int* a, int* b, int* c) class Jobtype public: int operator = ( Jobtype a) const return ( key = a.key ); int key; int index;

9、 bool job; ; Jobtype *d = new Jobtype n; for ( int i= 0; i b i ? bi: ai; d i .job = a i = bi; d i .index = I; sort(d, n);int j = 0, k = n - 1;for( int i = 0 ; in; i+) if( di.job) c j+ = di.index; else c k- - = di.index; j = ac0;k = j + bc0;for (int i =1; in ; i+) j+ = aci; k = j k? k+ bci: j + bci;

10、delete d;return k;3.3流水作业调度流水作业调度255.计算复杂性分析 算法的主要计算时间是排序，因此，最坏情况下算法所需的时间复杂度为 O（nlogn）流水作业调度流水作业调度3.3流水作业调度流水作业调度26最优化原理最优化原理 多阶段过程的最优决策序列应当具有性质：多阶段过程的最优决策序列应当具有性质： 无论过程的初始状态和初始决策是什么，其无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。态构成一个最优决策序列。流水作业调度流水作业调度3.3流水作业调度流水作业调度27 最优决策是

11、否存在依赖于该问题是否最优决策是否存在依赖于该问题是否 有最优子结构性质：有最优子结构性质：原问题的最优解包含了其子问题的最优解。原问题的最优解包含了其子问题的最优解。流水作业调度流水作业调度3.3流水作业调度流水作业调度28设计步骤设计步骤 找出最优解的性质，并刻画其结构特征。找出最优解的性质，并刻画其结构特征。 递归地定义最优值。递归地定义最优值。 以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造一个根据计算最优值时得到的信息，构造一个最优解。最优解。流水作业调度流水作业调度3.3流水作业调度流水作业调度29Exercises Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: enumerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer. 30E