动态规划的个性化优化

1、华东师大二附中项荣璟优化势在必行。一些适用一类状态转移方程的优化：利用四边形不等式、函数的凸性等。大多数状态转移方程的求解需要采用“个性化”的优化手段。优化的关键：减少冗余。重叠子问题无用的结果n本书，编号1,2,n。每本pi页。全部分给m个抄写员。每人分到顺序连续的若干本，每本只分给一人。求一种方案，使每人分到的页数和的最大值为最小。例子：n=9,m=3100 200 300 400 500 / 600 700 / 800 900 n项工作，编号为1,2,n。给定每项工作花费系数Fi和所需时间Ti。可按序分成任意多批依次执行，每批包含编号连续的工作。第一批开始于时间0。若某批包含工作i,i+

2、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,234,5，完成时间为(5,5,10,14,14)，总花费153。线性排列的元件C1,C2,Cn。Ci宽wi，高hi。要折叠成宽度为W的若干行（即每行元件总宽度W)，每行高度为该行中最高元件高度。行与行之间为布线通道，若Ci与Ci+1之间折叠，则它们所在行之间布线高度为li，ln=0。求最小总高度。进入hiwiC

3、1 C2C3 C9 C10C11.c1c2c3c4c5.最小化第一行布线高度第二行共同点：给定一个序列，求一种满足一些条件的最优化划分，使题中定义的某种“花费”最小。面对这三个相似的问题，我们大多会采用模式化的方法：以序列每个数为阶段以此前的每个数为最近的划分点按状态转移方程判断若给定划分的区间数目，则增加一维。问题一O(n3)，问题二O(n2) ，问题三O(n2)。f(i,j)：pi+pi+1+pj。g(i,k)：在将i,n中的数分成k份的最优划分中，花费最大区间的花费值。) 1, 1(),(maxmin),(),(max) 1,(),() 1 ,(1kjgjifkigjjfinignifi

4、gknjinji如果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(j+1,k-1)那么那么g(i,k)=g(j+1,k-1)g(i,k)=g(j+1,k-1)，即，即g(i,k)=g(i+1,k)g(i,k)=g(i+1,k)。转折点转折点是第一个这样的划分点是第一个这样的划分点j j，它使，它使i,ji,j 的花费为的花费为i,ni,n 中所有区间花费的中所有区间花

5、费的最大值最大值。形式化定义为：令0in,2km,i si,kn，如果f(i,si,k-1)g(j+1,k-1)，又根据si,k定义及性质二，有isi,kjj，从而容易确定si,k，继而应用性质三。for i:=n downto 1 do g(i,1):=f(i,n);边界条件for k:=2 to m do 计算边界g(n-k+1,k); j:=n-k+1; for i:=n-k downto m-k+1 do if f(I,j)=g(i+1,k-1) then 【 g(i,k):=f(i,i); j:=i 】 else 【while f(i,j-1)=g(j,k-1) do j:=j-1;

6、 定si,k g(i,k):=minf(i,j),g(j,k-1) 性质三 if g(i,k)=g(j,k-1) then j:=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时第一个区间是i,k-1的最小总花费。则C(i,k)=D(k)+(S+ti,k-1)fi。0)(),(min)(11nDki

7、CiDnki对于ikl,令g(k,l)=(D(k)-D(l)/tk,l-1性质一：性质一：1iklikl，如果，如果 g(k,l)ffi i, ,那么那么C(i,k)C(i,l)C(i,k)C(i,l)。注意到1ji时，fjfi于是有推论一：如果推论一：如果g(k,l)ffi i, ,那么对所有那么对所有1ji1ji，C(j,k)C(j,l)C(j,k)C(j,l)。推论一暗示了计算D(i),D(i-1),D(1)时都不必考虑在l-1处划分。ilkilkftlDkDftkDlDliCkiC1,1,/)()(0)()(),(),(性质二：对性质二：对1jkljkl，若，若g(j,k)g(j,k)

8、g(k,l)g(k,l)，则对所有，则对所有1ijii2ir，则必须满足：fig(i2,i1)g(i3,i2).g(ir,ir-1)fig(i2,i1)g(i3,i2).g(ir,ir-1)由上式和性质一，C(i,i1)C(i,i2)C(i,ir)从而D(i)=C(i,i1)。动态维护i1,i2,ir的数据结构：线性表lst，头指针head，尾指针tail。表头表尾删除，表尾添加。head:=1; tail:=1; lst1:=n+1; cn+1:=0; 表初始化for i:=n downto 1 do while (head=g(lsthead+1,lsthead) do inc(head)

9、; 按推论一删除 D(i):=C(i,lsthead); while (headtail) and (g(i,lsttail)W。Si可由Si+1得到：从Si+1中除去w(i+1,j)W的元素j，再添加i。注意到jw(i,k)及R(j,k) R(i,k)，则有性质一：如果性质一：如果a,b是是Si中元素，且中元素，且alsthead+1lsttailF(lsthead)F(lsthead+1)F(lsttail)根据w(i,j)在ijn上单调增，从表头删数能完成删除一；从表尾删数能完成删除二，然后将i添加到表尾，依然能保持表中元素有序性。考虑在计算F(i)时，将F(j)与R(i+1,j)联系起

10、来。由性质二连续的R值可能是相等的，即R(i+1,j)=R(i+1,j+1)=R(i+1,k)=h，此时我们可以将F(j),F(j+1),F(k)都与h相联系。), 1()(min)(jiRjFliFiSji性质二：性质二：ij，如果，如果hj+1hj，则，则 R(i,j+1)=R(i,j)维护一个表Hlst，表头指针p，表尾指针q。在递推到第i阶段，bottop：Si中第bot到第top个元素（即：lstbot,lstbot+1,lsttop)都与h联系。Hlstk.bot=Hlstk-1.top+1。valuehbottopkHlistqpheadtailb bo ot tt to op

11、pHlstlstF(lstHlistk.bot)F(lstHlstk.bot+1)top时删除value，且移动p或q。当改变bot指针时，须改变value值；将i添加到lst表后，也更新Hlst的表尾，然后从Hlst表尾开始不断按照性质二合并表中元素，使Hlstq.hHlstq-1.hHlstp.h。某个value值被改变、添加或删除时，同时调整堆。堆调整一次的复杂度是O( n)。每个元素进出lst各一次，Hlst的维护与lst是同步的，Hlst合并的总次数不会超过n，因此堆调整的次数O(n)。总的时间复杂度：O(n n)。根据问题性质选择恰当的数据结构：扎实的基础灵活和富有创造性的运用能力本题的数据结构：lst是观察到性质1而设的有序表，它结构上既不同于队列又不同于栈。满足了动态规划各阶段对插入和删除候选决策的需要。Hlst利用了性质2合并lst中元素，从而保证了堆调整的次数为O(n)。堆的设置是建立在对基础数据结构的算法