算法合集之《例析動態(tài)規(guī)劃的“個性化”優(yōu)化》.ppt

充分利用問題性質(zhì),例析動態(tài)規(guī)劃的“個性化”優(yōu)化,華東師大二附中項榮璟,動態(tài)規(guī)劃的優(yōu)化,優(yōu)化勢在必行。一些適用一類狀態(tài)轉(zhuǎn)移方程的優(yōu)化：利用四邊形不等式、函數(shù)的凸性等。大多數(shù)狀態(tài)轉(zhuǎn)移方程的求解需要采用“個性化”的優(yōu)化手段。,動態(tài)規(guī)劃的優(yōu)化,優(yōu)化的關(guān)鍵：減少冗余。,冗余,空間換取時間，利用已知結(jié)果,分析問題性質(zhì)，排除不必要的計算量,問題一書稿復(fù)制(cerc98),n本書，編號1,2,n。每本pi頁。全部分給m個抄寫員。每人分到順序連續(xù)的若干本，每本只分給一人。求一種方案，使每人分到的頁數(shù)和的最大值為最小。例子：n=9,m=3100200300400500/600700/800900,問題二工作分批(ioi2002),n項工作，編號為1,2,n。給定每項工作花費系數(shù)Fi和所需時間Ti?？砂葱蚍殖扇我舛嗯来螆?zhí)行，每批包含編號連續(xù)的工作。第一批開始于時間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,234,5，完成時間為(5,5,10,14,14)，總花費153。,問題三元件折疊,線性排列的元件C1,C2,Cn。Ci寬wi，高hi。要折疊成寬度為W的若干行（即每行元件總寬度W)，每行高度為該行中最高元件高度。行與行之間為布線通道，若Ci與Ci+1之間折疊，則它們所在行之間布線高度為li，ln=0。求最小總高度。進入,“通用”的解法,共同點：給定一個序列，求一種滿足一些條件的最優(yōu)化劃分，使題中定義的某種“花費”最小。面對這三個相似的問題，我們大多會采用模式化的方法：以序列每個數(shù)為階段以此前的每個數(shù)為最近的劃分點按狀態(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)劃分中，花費最大區(qū)間的花費值。,問題一分析（1）,如果j是i+1,n的第一個劃分點（即動態(tài)規(guī)劃的決策）i,j的花費不大于j+1,n中花費最大區(qū)間的花費值那么：j也是i,n的第一個劃分點。性質(zhì)一：i+1,j是g(i+1,k)對應(yīng)的分劃中的第一個區(qū)間，如果f(i,j)g(j+1,k-1)那么g(i,k)=g(j+1,k-1)，即g(i,k)=g(i+1,k)。,問題一分析（2）,轉(zhuǎn)折點是第一個這樣的劃分點j，它使i,j的花費為i,n中所有區(qū)間花費的最大值。形式化定義為：令0in,2km,isi,kn，如果f(i,si,k-1)g(j+1,k-1)，又根據(jù)si,k定義及性質(zhì)二，有isi,kj，從而容易確定si,k，繼而應(yīng)用性質(zhì)三。,問題一算法分析,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(i+1,k-1)then【g(i,k):=f(i,i);j:=i】else【whilef(i,j-1)=g(j,k-1)doj:=j-1;定si,kg(i,k):=minf(i,j),g(j,k-1)性質(zhì)三ifg(i,k)=g(j,k-1)thenj:=j-1】end_for_k外層每循環(huán)一次，j遞減的工作量是O(n)。因此總的復(fù)雜度O(n)。,問題一小結(jié),分析問題性質(zhì)：深入挖掘題意尋找在最優(yōu)性和可行性的約束下中間結(jié)果必須滿足的必要條件。由淺入深將不成熟的想法轉(zhuǎn)化為言之有理的論斷。問題三,問題二方程,ti,j=Ti+Ti+1+Tj；fi=Fi+Fi+1+.+Fn。D(i)：劃分i,n的最小總花費。C(i,k)：劃分i,n時第一個區(qū)間是i,k-1的最小總花費。則C(i,k)=D(k)+(S+ti,k-1)fi。,問題二分析（1）,對于ikl,令g(k,l)=(D(k)-D(l)/tk,l-1性質(zhì)一：1ikl，如果g(k,l)fi,那么C(i,k)C(i,l)。注意到1jir，則必須滿足：fig(i2,i1)g(i3,i2).g(ir,ir-1),問題二分析（3）,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)。動態(tài)維護i1,i2,ir的數(shù)據(jù)結(jié)構(gòu)：線性表lst，頭指針head，尾指針tail。表頭表尾刪除，表尾添加。,問題二算法分析,head:=1;tail:=1;lst1:=n+1;cn+1:=0;表初始化fori:=ndownto1dowhile(head=g(lsthead+1,lsthead)doinc(head);按推論一刪除D(i):=C(i,lsthead);while(headW的元素j，再添加i。注意到j(luò)w(i,k)及R(j,k)R(i,k)，則有性質(zhì)一：如果a,b是Si中元素，且alsthead+1lsttailF(lsthead)F(lsthead+1)F(lsttail)根據(jù)w(i,j)在ijn上單調(diào)增，從表頭刪數(shù)能完成刪除一；從表尾刪數(shù)能完成刪除二，然后將i添加到表尾，依然能保持表中元素有序性。,問題三分析（3）,考慮在計算F(i)時，將F(j)與R(i+1,j)聯(lián)系起來。由性質(zhì)二連續(xù)的R值可能是相等的，即R(i+1,j)=R(i+1,j+1)=R(i+1,k)=h，此時我們可以將F(j),F(j+1),F(k)都與h相聯(lián)系。,性質(zhì)二：ij，如果hj+1hj，則R(i,j+1)=R(i,j),問題三分析（4）,維護一個表Hlst，表頭指針p，表尾指針q。在遞推到第i階段，bottop：Si中第bot到第top個元素（即：lstbot,lstbot+1,lsttop)都與h聯(lián)系。Hlstk.bot=Hlstk-1.top+1。,問題三分析（5）,F(lstHlistk.bot)F(lstHlstk.bot+1)top時刪除value，且移動p或q。當(dāng)改變bot指針時，須改變value值；將i添加到lst表后，也更新Hlst的表尾，然后從Hlst表尾開始不斷按照性質(zhì)二合并表中元素，使Hlstq.hHlstq-1.hHlstp.h。某個value值被改變、添加或刪除時，同時調(diào)整堆。堆調(diào)整一次的復(fù)雜度是O(n)。每個元素進出lst各一次，Hlst的維護與lst是同步的，Hlst合并的總次數(shù)不會超過n，因此堆調(diào)整的次數(shù)O(n)?？偟臅r間復(fù)雜度：O(nn)。,問題三小結(jié),根據(jù)問題性質(zhì)選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)：扎實的基礎(chǔ)靈活和富有創(chuàng)造性的運用能力本題的數(shù)據(jù)結(jié)構(gòu)：lst是觀察到性質(zhì)1而設(shè)的有序表，它結(jié)構(gòu)上既不同于隊列又不同于棧。滿足了動態(tài)規(guī)劃各階段對插入和刪除候選決策的需要。Hlst利用了性質(zhì)2合并lst中元素，從而保證了堆調(diào)整的次數(shù)為O(n)。堆的設(shè)置是建立在對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的算法和性能充分