第3章动态规划2

3.2动态规划算法的基本要素

ElementsofDynamicProgramming

1最优子结构性质 OptimalSubstructure

2重叠子问题性质OverlappingSubproblems

11.最优子结构

OptimalSubstructure

当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。3.2动态规划算法的基本要素22.重叠子问题

OverlappingSubproblems

在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法对每个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。动态规划算法的基本要素3.2动态规划算法的基本要素33.备忘录方法

Memoization

用一个表格来保存已解决的子问题的答案，用的时候查表即可。采用的递归方式是自顶向下，动态规划是自底向上。初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问题的解答即可。动态规划算法的基本要素3.2动态规划算法的基本要素4备忘录方法解矩阵乘intMemoizedMatrixChain(intn,int**m,int**s){for(inti=1;i<=n;i++)for(intj=i;j<=n;j++)m[i][j]=0;returnLookupChain(1,n);}动态规划算法的基本要素3.2动态规划算法的基本要素5intLookupChain(inti,intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[k]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}动态规划算法的基本要素表示该子问题已经求解递归求解断开位置为i时的计算量循环每个可取断开位置求计算量作业：请写出利用备忘录方法计算A[1:4]时都计算了哪些子问题?3.2动态规划算法的基本要素6动态规划算法的基本要素备忘录采用自顶向下的计算，将计算结果存入矩阵后返回，每个子问题仅在第一次被调用时计算。m[i][j]共有O(n2)个备忘记录项，初始化需要O(n2)时间，每个记录项只填入一次，共耗费O(n)时间，所以备忘录方法耗时O(n3)。3.2动态规划算法的基本要素7当一个问题的所有子问题都至少要解一次时，则用动态规划算法比备忘录方法好。当子问题空间中的部分子问题可不必求解时，用备忘录方法则较有利，因为从其控制结构可以看出，该方法只解哪些确实需要求解的子问题。动态规划算法的基本要素3.2动态规划算法的基本要素83.3流水作业调度

SchedulingtoMaximizeProfit

已知n个作业{1,2,...,n}要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi，1≤i≤n。流水作业调度问题要求确定这n个作业的最优加工次序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。问题描述：9aibiajbjM1M2M1M2aiajbjajbibjaibiai+bi+bjaj+ai+bi设有两个任务i和j，它们在M1和M2上执行的时间分别为ai,bi和aj,bj，如下图所示，假设M1和M2都处于空闲状态，考虑按不同顺序执行两个任务的过程。taskitaskj例1：3.3流水作业调度作业积压M2空闲10记N={1,2,...,n}，S为N的子集合。一般情况下，当机器M1开始加工S中的作业时，机器M2可能正在加工其它的作业，要等待时间t后才可用来加工S中的作业。将这种情况下流水线完成S中的作业所需的最短时间记为T(S,t)，则流水作业调度问题的最优值即是

。流水作业调度T(N,0)M1M2a1b1M1M2aibit3.3流水作业调度111.流水作业调度问题具有最优子结构性质设π是n个流水作业的一个最优调度（实际上是作业的一个排序），π(1)，···π(n)表示π中各个作业。该最优调度的加工时间为aπ(1)+T’,其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，···π(n)所需的时间。流水作业调度证明最优子结构性质就是证明如果π是最优调度，那么π中除去π(1)，在M2上等待时间为bπ(1)时，按照π中顺序安排π(2)，···π(n)的顺序是最优的。3.3流水作业调度12

若记S=N-{π(1)}，则T(S,bπ(1))为在M2上等待时间为bπ(1)时S的最优调度时间。证明T’=T(S,bπ(1))证明：由T’定义知，T’≥T(S,bπ(1)

)。

若T’>T(S,bπ(1)

)，设π’是作业集S在机器M2等待时间bπ(1)时的一个最优调度，则π(1),π’(2),···,π’(n)是N的一个调度。

该调度所需的时间为aπ(1)+

T(S,bπ(1)

)<aπ(1)+T’。这与π是N的一个最优调度矛盾，所以T’=T(S,bπ(1)

)，说明流水作业调度问题具有最优子结构性质。流水作业调度3.3流水作业调度132.递归计算最优值由流水作业调度问题的最优子结构性质可知,流水作业调度M1M2aibiajbj3.3流水作业调度14M1M2aibiajbjtt>ai等待时间t’=t–ai+biM1M2t<=ai等待时间t’=0+biajbjaibit上述关系式可以推广到一般情形计算T(S,t)：通过该式可给出流水调度的动态规划算法，但是其时间复杂度将是O(2n)。可采用下述Jonhson算法。3.3流水作业调度153.流水作业调度的Johnson法则本节后面推导要说明的问题如果作业i和j满足min{bi,aj}≥

min{bj,ai}，则称作业i和j满足Johnson不等式。如果作业i和j不满足Johnson不等式，则交换作业i和作业j的加工顺序，之后作业i和j将满足Johnson不等式，且不增加加工时间。流水作业调度原问题转化为求满足Johnson法则的调度问题，即找到的调度顺序中任意两个相邻作业满足Johnson法则。3.3流水作业调度163.流水作业调度的Johnson法则设π是所给n个流水作业的一个最优调度，若在这个调度中，安排在最前面的两个作业分别是i和j，即π(1)=i,π(2)=j，则动态规划递归式可得：tij为i和j在M1上结束后，需要等待多少时间才能开始在M2上加工。流水作业调度3.3流水作业调度17t>ai流水作业调度t<=aiaiajtbibjtbibjttbibibjbj3.3流水作业调度18

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

流水作业调度3.3流水作业调度20如果作业i和j满足Johnson不等式流水作业调度则3.3流水作业调度21Johnson法则的调度对于流水作业调度问题，必存在一个最优调度π，使得π(i)和π(i+1)满足Johnson不等式min{bπ(i),aπ(i+1)}≥min{bπ(i+1),aπ(i)}min{bπ(i),aπ(j)}≥min{bπ(j),aπ(i)}i<j

流水作业调度3.3流水作业调度22Johnson算法流水作业调度考虑这样构成的调度一定满足Johnson法则吗？3.3流水作业调度23算法描述流水作业调度intFlowShop(intn,int*a,int*b,int*c){classJobtype{public:intoperator<=(Jobtypea)const{return(key<=a.key);}intkey;intindex;booljob;};Jobtype*d=newJobtype[n];for(inti=0;i<n;i++){d[i].key=a[i]>b[i]?b[i]:a[i];d[i].job=a[i]<=b[i];d[i].index=I;}sort(d,n);intj=0,k=n-1;for(inti=0;i<n;i++){if(d[i].job)c[j++]=d[i].index;elsec[k--]=d[i].index;}j=a[c[0]];k=j+b[c[0]];for(inti=1;i<n;i++){j+=a[c[i]];k=j<k?k+b[c[i]]:j+b[c[i]];}deleted;returnk;}3.3流水作业调度245.计算复杂性分析算法的主要计算时间是排序，因此，最坏情况下算法所需的时间复杂度为O（nlogn）流水作业调度3.3流水作业调度25最优化原理

多阶段过程的最优决策序列应当具有性质：

无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。流水作业调度3.3流水作业调度26最优决策是否存在依赖于该问题是否有最优子结构性质：原问题的最优解包含了其子问题的最优解。流水作业调度