章动态规划课件

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