1、3.2 动态规划算法的基本要素动态规划算法的基本要素1 最优子结构性质最优子结构性质2 重叠子问题性质重叠子问题性质1.最优子结构最优子结构 当问题的最优解包含了其子问题的最优解当问题的最优解包含了其子问题的最优解时，称该问题具有时，称该问题具有最优子结构性质最优子结构性质。分析最优子结构性质时，一般假设由问题分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后的最优解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。比原问题更优解更好的解，从而导出矛盾。动态规划算法的基本要素动态规划算
2、法的基本要素2.重叠子问题重叠子问题 在用递归算法自顶向下解此问题时，每次在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法对每个题被反复计算多次。动态规划算法对每个问题只解一次，而后将其解保存在一个表问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，用常数时格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法间查看一下结果。因此，用动态规划算法通常只需要多项式时间。通常只需要多项式时间。动态规划算法的基本要素动态规划算法的基本要素3.备忘录方法备忘录方法 用一个表格来保存
3、已解决的子问题的答案，用的用一个表格来保存已解决的子问题的答案，用的时候查表即可。时候查表即可。采用的递归方式是采用的递归方式是自顶向下自顶向下，动态规划是，动态规划是自低向自低向上上 初始化为每个子问题的记录存入一个特殊的值，初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问果是特殊值，表示未求解，否则只要取出该子问题的解答即可。题的解答即可。动态规划算法的基本要素动态规划算法的基本要素备忘录方法解矩阵乘备忘录方法解矩阵乘int MemoizedMatrixChain(int
4、 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=LookupChain(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的一个调度。的一个调度。该
5、调度所需的时间为该调度所需的时间为a(1)+T(S,b(1)ai等待时间等待时间t=t ai+biM1M2t ai流水作业调度流水作业调度t=aiaiajtbibjtbibjttbibibjbjt ai+bi ajtij=t ai+bi-aj+bjbiajtij=bi ai+bjbj+maxbi+(t-ai)-aj,0bj+maxbi-aj,0 如果调换如果调换i，j的加工顺序，则得到另一调度，它的加工顺序，则得到另一调度，它的加工时间变为的加工时间变为jit流水作业调度流水作业调度考虑对于相同的考虑对于相同的 ai,aj,bi,bj，不同的加工顺序，不同的加工顺序导致剩余任务的等待时间导致剩
6、余任务的等待时间tij与与tji的大小关系的大小关系 称作业称作业i和和j满足满足Johnson不等式，如果作业不等式，如果作业i和和j不满足不满足Johnson不等式，则交换作业不等式，则交换作业i和作业和作业j的加工顺序后，他们满足的加工顺序后，他们满足Johnson不等式不等式 交换作业的加工顺序后，它需要的加工时间为交换作业的加工顺序后，它需要的加工时间为),/(),(jijitjiSTaatsT如果作业如果作业i和和j满足满足 ,maxjjjiijijjiabaataabbt流水作业调度流水作业调度如果作业如果作业i和和j满足满足Johnson不等式不等式流水作业调度流水作业调度则则
7、Johnson法则的调度法则的调度 对于流水作业调度问题，必存在一个最优对于流水作业调度问题，必存在一个最优调度调度，使得，使得(i)和和(i+1)满足满足Johnson不等不等式式 minb(i),a(i+1)minb(i+1),a(i)minb(i),a(j)minb(j),a(i)ij 流水作业调度流水作业调度Johnson算法算法流水作业调度流水作业调度考虑这样构成的考虑这样构成的调度一定满足调度一定满足Johnson法则法则吗吗算法描述算法描述流水作业调度流水作业调度int FlowShop(int n,int a,int b,int c)class Jobtype public:i
8、nt operator=(Jobtype a)const return(key=a.key);int key;int index;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;delete d
9、;return k;保存最后的调用顺序保存最后的调用顺序ai和和bi中较小者中较小者该任务的下标该任务的下标若若ai=bi,则则job为为true5.计算复杂性分析 算法的主要计算时间是排序，因此，最坏情况下算法所需的时间复杂度为 O（nlogn）流水作业调度流水作业调度最优化原理最优化原理 多阶段过程的最优决策序列应当具有性质：多阶段过程的最优决策序列应当具有性质：无论过程的初始状态和初始决策是什么，其无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。态构成一个最优决策序列。流水作业调度流水作业调度 最优决策是否存在依赖于该问题是否最优决策是否存在依赖于该问题是否 有最优子结构性质：有最优子结构性质：原问题的最优解包原问题的最优解包含了其子问题的最优解。含了其子问题的最优解。流水作业调度流水作业调度设计步骤设计步骤 找出最优解的性质，并刻画其结构特征。找出最优解的性质，并刻画其结构特征。递归地定义最优值递归地定义最优值 以自低向上的方式计算出最优值以自低向上的方式计算出最优值 根据计算最优值时得到的信息，构造一个根据计算最优值时得到的信息，构造一个最优解最优解流水作业调度流水作业调度作业：作业：P82,3-3
