算法合集之《例析动态规划的“个性化”优化》

《算法合集之《例析动态规划的“个性化”优化》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、充分利用问题性质——例析动态规划的“个性化”优化华东师大二附中项荣璟动态规划的优化优化势在必行。一些适用一类状态转移方程的优化：利用四边形不等式、函数的凸性等。大多数状态转移方程的求解需要采用“个性化”的优化手段。动态规划的优化优化的关键：减少冗余。冗余空间换取时间，利用已知结果分析问题性质，排除不必要的计算量问题一——书稿复制(cerc98)n本书，编号1,2,…,n。每本pi页。全部分给m个抄写员。每人分到顺序连续的若干本，每本只分给一人。求一种方案，使每人分到的页数和的最大值为最小。例子：n=9,m=3100200300400500/600700/8009

2、00问题二——工作分批(ioi2002)n项工作，编号为1,2,…,n。给定每项工作花费系数Fi和所需时间Ti。可按序分成任意多批依次执行，每批包含编号连续的工作。第一批开始于时间0。若某批包含工作i,i+1,…,j，开始于时间t，则该批中所有工作的完成时间是t+s+(Ti+Ti+1+…+Tj)。这也是下一批的开始时间。一个工作的花费是其完成时间*Fi，求最小可能的总花费。例子：n=5,s=1(T1,T2,…,T5)=(1,3,4,2,1)(F1,F2,…F5)=(3,2,3,3,4)可分成三批{1,2}{3}{4,5}，完成时间为(5,5,10,14,14)，

3、总花费153。问题三——元件折叠线性排列的元件C1,C2,…,Cn。Ci宽wi，高hi。要折叠成宽度为W的若干行（即每行元件总宽度≤W)，每行高度为该行中最高元件高度。行与行之间为布线通道，若Ci与Ci+1之间折叠，则它们所在行之间布线高度为li，ln=0。求最小总高度。进入“通用”的解法共同点：给定一个序列，求一种满足一些条件的最优化划分，使题中定义的某种“花费”最小。面对这三个相似的问题，我们大多会采用模式化的方法：以序列每个数为阶段以此前的每个数为最近的划分点按状态转移方程判断若给定划分的区间数目，则增加一维。问题一O(n3)，问题二O(n2)，问题三O(

4、n2)。问题一——方程f(i,j)：pi+pi+1+…+pj。g(i,k)：在将[i,n]中的数分成k份的最优划分中，花费最大区间的花费值。问题一——分析（1）如果j是[i+1,n]的第一个划分点（即动态规划的决策）[i,j]的花费不大于[j+1,n]中花费最大区间的花费值那么：j也是[i,n]的第一个划分点。性质一：[i+1,j]是g(i+1,k)对应的分划中的第一个区间，如果f(i,j)≤g(j+1,k-1)那么g(i,k)=g(j+1,k-1)，即g(i,k)=g(i+1,k)。问题一——分析（2）转折点是第一个这样的划分点j，它使[i,j]的花费为[i,

5、n]中所有区间花费的最大值。形式化定义为：令0≤i≤n,2≤k≤m,i≤si,k≤n，如果f(i,si,k-1)

6、)；否则f(i,j)>g(j+1,k-1)，又根据si,k定义及性质二，有i≤si,k≤j，从而容易确定si,k，继而应用性质三。问题一——算法分析fori:=ndownto1dog(i,1):=f(i,n);｛边界条件｝fork:=2tomdo计算边界g(n-k+1,k);j:=n-k+1;fori:=n-kdowntom-k+1doiff(I,j)<=g(j+1,k-1)theng(i,k):=g(j+1,k-1)｛性质一｝elseiff(i,i)>=g(i+1,k-1)then【g(i,k):=f(i,i);j:=i】else【whilef(i,j-1)>

7、=g(j,k-1)doj:=j-1;{定si,k}g(i,k):=min{f(i,j),g(j,k-1)}{性质三}ifg(i,k)=g(j,k-1)thenj:=j-1】end_for_k外层每循环一次，j递减的工作量是O(n)。因此总的复杂度O(n２)。问题一——小结分析问题性质：深入挖掘题意寻找在最优性和可行性的约束下中间结果必须满足的必要条件。由浅入深将不成熟的想法转化为言之有理的论断。问题三问题二——方程ti,j=Ti+Ti+1+…+Tj；fi=Fi+Fi+1+..+Fn。D(i)：划分[i,n]的最小总花费。C(i,k)：划分[i,n]时第一个区间是

8、[i,k-1]的最小总花