動(dòng)態(tài)規(guī)劃的個(gè)性化優(yōu)化

1、華東師大二附中項(xiàng)榮璟優(yōu)化勢在必行。一些適用一類狀態(tài)轉(zhuǎn)移方程的優(yōu)化：利用四邊形不等式、函數(shù)的凸性等。大多數(shù)狀態(tài)轉(zhuǎn)移方程的求解需要采用“個(gè)性化”的優(yōu)化手段。優(yōu)化的關(guān)鍵：減少冗余。重疊子問題無用的結(jié)果n本書，編號1,2,n。每本pi頁。全部分給m個(gè)抄寫員。每人分到順序連續(xù)的若干本，每本只分給一人。求一種方案，使每人分到的頁數(shù)和的最大值為最小。例子：n=9,m=3100 200 300 400 500 / 600 700 / 800 900 n項(xiàng)工作，編號為1,2,n。給定每項(xiàng)工作花費(fèi)系數(shù)Fi和所需時(shí)間Ti?？砂葱蚍殖扇我舛嗯来螆?zhí)行，每批包含編號連續(xù)的工作。第一批開始于時(shí)間0。若某批包含工作i,i+

2、1,j，開始于時(shí)間t，則該批中所有工作的完成時(shí)間是t+s+(Ti+Ti+1+Tj)。這也是下一批的開始時(shí)間。一個(gè)工作的花費(fèi)是其完成時(shí)間*Fi，求最小可能的總花費(fèi)。例子：n=5,s=1(T1,T2,T5)=(1,3,4,2,1) (F1,F2,F5)=(3,2,3,3,4)可分成三批1,234,5，完成時(shí)間為(5,5,10,14,14)，總花費(fèi)153。線性排列的元件C1,C2,Cn。Ci寬wi，高h(yuǎn)i。要折疊成寬度為W的若干行（即每行元件總寬度W)，每行高度為該行中最高元件高度。行與行之間為布線通道，若Ci與Ci+1之間折疊，則它們所在行之間布線高度為li，ln=0。求最小總高度。進(jìn)入hiwiC

3、1 C2C3 C9 C10C11.c1c2c3c4c5.最小化第一行布線高度第二行共同點(diǎn)：給定一個(gè)序列，求一種滿足一些條件的最優(yōu)化劃分，使題中定義的某種“花費(fèi)”最小。面對這三個(gè)相似的問題，我們大多會(huì)采用模式化的方法：以序列每個(gè)數(shù)為階段以此前的每個(gè)數(shù)為最近的劃分點(diǎn)按狀態(tài)轉(zhuǎn)移方程判斷若給定劃分的區(qū)間數(shù)目，則增加一維。問題一O(n3)，問題二O(n2) ，問題三O(n2)。f(i,j)：pi+pi+1+pj。g(i,k)：在將i,n中的數(shù)分成k份的最優(yōu)劃分中，花費(fèi)最大區(qū)間的花費(fèi)值。) 1, 1(),(maxmin),(),(max) 1,(),() 1 ,(1kjgjifkigjjfinignifi

4、gknjinji如果j是i+1,n的第一個(gè)劃分點(diǎn)（即動(dòng)態(tài)規(guī)劃的決策）i,j的花費(fèi)不大于j+1,n中花費(fèi)最大區(qū)間的花費(fèi)值那么：j也是i,n的第一個(gè)劃分點(diǎn)。性質(zhì)一：性質(zhì)一：i+1,j是是g(i+1,k)對應(yīng)的分劃中的第一個(gè)對應(yīng)的分劃中的第一個(gè)區(qū)間，如果區(qū)間，如果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)。轉(zhuǎn)折點(diǎn)轉(zhuǎn)折點(diǎn)是第一個(gè)這樣的劃分點(diǎn)是第一個(gè)這樣的劃分點(diǎn)j j，它使，它使i,ji,j 的花費(fèi)為的花費(fèi)為i,ni,n 中所有區(qū)間花費(fèi)的中所有區(qū)間花

5、費(fèi)的最大值最大值。形式化定義為：令0in,2km,i si,kn，如果f(i,si,k-1)g(j+1,k-1)，又根據(jù)si,k定義及性質(zhì)二，有isi,kjj，從而容易確定si,k，繼而應(yīng)用性質(zhì)三。for i:=n downto 1 do g(i,1):=f(i,n);邊界條件for k:=2 to m do 計(jì)算邊界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) 性質(zhì)三 if g(i,k)=g(j,k-1) then j:=j-1】end_for_k外層每循環(huán)一次，j遞減的工作量是O(n)。因此總的復(fù)雜度O(n)。分析問題性質(zhì)：深入挖掘題意尋找在最優(yōu)性和可行性的約束下中間結(jié)果必須滿足的必要條件。由淺入深將不成熟的想法轉(zhuǎn)化為言之有理的論斷。問題三ti,j=Ti+Ti+1+Tj；fi=Fi+Fi+1+.+Fn。D(i)：劃分i,n的最小總花費(fèi)。C(i,k)：劃分i,n時(shí)第一個(gè)區(qū)間是i,k-1的最小總花費(fèi)。則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性質(zhì)一：性質(zhì)一：1iklikl，如果，如果 g(k,l)ffi i, ,那么那么C(i,k)C(i,l)C(i,k)C(i,l)。注意到1ji時(shí)，fjfi于是有推論一：如果推論一：如果g(k,l)ffi i, ,那么對所有那么對所有1ji1ji，C(j,k)C(j,l)C(j,k)C(j,l)。推論一暗示了計(jì)算D(i),D(i-1),D(1)時(shí)都不必考慮在l-1處劃分。ilkilkftlDkDftkDlDliCkiC1,1,/)()(0)()(),(),(性質(zhì)二：對性質(zhì)二：對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)由上式和性質(zhì)一，C(i,i1)C(i,i2)C(i,ir)從而D(i)=C(i,i1)。動(dòng)態(tài)維護(hù)i1,i2,ir的數(shù)據(jù)結(jié)構(gòu)：線性表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。注意到j(luò)w(i,k)及R(j,k) R(i,k)，則有性質(zhì)一：如果性質(zhì)一：如果a,b是是Si中元素，且中元素，且alsthead+1lsttailF(lsthead)F(lsthead+1)F(lsttail)根據(jù)w(i,j)在ijn上單調(diào)增，從表頭刪數(shù)能完成刪除一；從表尾刪數(shù)能完成刪除二，然后將i添加到表尾，依然能保持表中元素有序性?？紤]在計(jì)算F(i)時(shí)，將F(j)與R(i+1,j)聯(lián)系起

10、來。由性質(zhì)二連續(xù)的R值可能是相等的，即R(i+1,j)=R(i+1,j+1)=R(i+1,k)=h，此時(shí)我們可以將F(j),F(j+1),F(k)都與h相聯(lián)系。), 1()(min)(jiRjFliFiSji性質(zhì)二：性質(zhì)二：ij，如果，如果hj+1hj，則，則 R(i,j+1)=R(i,j)維護(hù)一個(gè)表Hlst，表頭指針p，表尾指針q。在遞推到第i階段，bottop：Si中第bot到第top個(gè)元素（即：lstbot,lstbot+1,lsttop)都與h聯(lián)系。Hlstk.bot=Hlstk-1.top+1。valuehbottopkHlistqpheadtailb bo ot tt to op

11、pHlstlstF(lstHlistk.bot)F(lstHlstk.bot+1)top時(shí)刪除value，且移動(dòng)p或q。當(dāng)改變bot指針時(shí)，須改變value值；將i添加到lst表后，也更新Hlst的表尾，然后從Hlst表尾開始不斷按照性質(zhì)二合并表中元素，使Hlstq.hHlstq-1.hHlstp.h。某個(gè)value值被改變、添加或刪除時(shí)，同時(shí)調(diào)整堆。堆調(diào)整一次的復(fù)雜度是O( n)。每個(gè)元素進(jìn)出lst各一次，Hlst的維護(hù)與lst是同步的，Hlst合并的總次數(shù)不會(huì)超過n，因此堆調(diào)整的次數(shù)O(n)?？偟臅r(shí)間復(fù)雜度：O(n n)。根據(jù)問題性質(zhì)選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)：扎實(shí)的基礎(chǔ)靈活和富有創(chuàng)造性的運(yùn)用能力本題的數(shù)據(jù)結(jié)構(gòu)：lst是觀察到性質(zhì)1而設(shè)的有序表，它結(jié)構(gòu)上既不同于隊(duì)列又不同于棧。滿足了動(dòng)態(tài)規(guī)劃各階段對插入和刪除候選決策的需要。Hlst利用了性質(zhì)2合并lst中元素，從而保證了堆調(diào)整的次數(shù)為O(n)。堆的設(shè)置是建立在對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的算法