|
新聞詳情
動(dòng)態(tài)規(guī)劃經(jīng)典教程——多維狀態(tài)和動(dòng)態(tài)規(guī)劃的優(yōu)化發(fā)表時(shí)間：2021-03-09 16:24 3.多維狀態(tài)和動(dòng)態(tài)規(guī)劃的優(yōu)化 一般多維動(dòng)態(tài)規(guī)劃的時(shí)，空間復(fù)雜度較高，所以我們要想辦法將其優(yōu)化，我就把多維動(dòng)態(tài)規(guī)劃和動(dòng)態(tài)規(guī)劃的優(yōu)化放到一起了…… 多維動(dòng)態(tài)規(guī)劃以三，四維最為常見(jiàn)，在多的也沒(méi)有太大的研究?jī)r(jià)值，其實(shí)多維動(dòng)態(tài)規(guī)劃大多也就是上面的一維，和二維的加一些條件，或是在多進(jìn)程動(dòng)態(tài)規(guī)劃中要用到。當(dāng)然除了這些特點(diǎn)外，狀態(tài)的表示也有一些共性。 三維：狀態(tài)opt[i,j,k]一般可表示下面的含義： （1）二維狀態(tài)的基礎(chǔ)上加了某個(gè)條件，或其中一維變成兩個(gè)。 比如opt[L,i]表示起點(diǎn)為I，長(zhǎng)度為L的序列的最優(yōu)值。opt[L,i,j]就可表示起點(diǎn)是i和起點(diǎn)是j，長(zhǎng)度是L的兩個(gè)序列的最優(yōu)值。 （2）I，J，K組合表示一個(gè)正方形（（i,j）點(diǎn)為一角，邊長(zhǎng)為K）。 （3）I，J，K組合表示一個(gè)等邊三角形（（i,j）點(diǎn)為一角，邊長(zhǎng)為K）。 四維：除了二維和三維加條件外，還可以用i,j,k,t組合來(lái)描述一個(gè)矩形， （i,j）點(diǎn)和（k,t）點(diǎn)是兩個(gè)對(duì)頂點(diǎn)。 四維以上的一般都是前幾維加了條件了，這里就不多說(shuō)了。 動(dòng)態(tài)規(guī)劃的優(yōu)化： 動(dòng)態(tài)規(guī)劃的優(yōu)化往往需要較強(qiáng)的數(shù)學(xué)功底。 常見(jiàn)空間優(yōu)化： 滾動(dòng)數(shù)組，滾動(dòng)數(shù)組在前面也提到過(guò)，其實(shí)很簡(jiǎn)單，如果一個(gè)狀態(tài)的決策的步長(zhǎng)為N就只保留以求出的最后N（一般N=1）個(gè)階段的狀態(tài)，因?yàn)楫?dāng)前狀態(tài)只和后N個(gè)階段中的狀態(tài)有關(guān)，再以前的已經(jīng)利用過(guò)了，沒(méi)用了就可以替換掉了。具體實(shí)現(xiàn)是最好只讓下標(biāo)滾動(dòng)（這樣更省時(shí)間）。 X：=K1，K1：=K2，K2；=K3，K3：=X這樣就實(shí)現(xiàn)了一個(gè)N=3的下標(biāo)的滾動(dòng)，在滾動(dòng)完如果狀態(tài)是涉及累加，累乘類的操作要注意將當(dāng)前要求的狀態(tài)初始化。 常見(jiàn)時(shí)間優(yōu)化：利用一些數(shù)據(jù)結(jié)構(gòu)（堆，并查集，HASH）降低查找復(fù)雜度。 時(shí)間空間雙重優(yōu)化：改變狀態(tài)的表示法，降低狀態(tài)維數(shù)。 具體的多維動(dòng)態(tài)規(guī)劃和動(dòng)態(tài)規(guī)劃的優(yōu)化，我們從題目里體會(huì)吧！ 3.1矩陣問(wèn)題 先看一道題 例題27 蓋房子 來(lái)源：VIJOS P1057 【問(wèn)題描述】 永恒の靈魂最近得到了面積為n*m的一大塊土地（高興ING^_^），他想在這塊土地上建造一所房子，這個(gè)房子必須是正方形的。 【輸入文件】 輸入文件第一行為兩個(gè)整數(shù)n,m（1<=n,m<=1000），接下來(lái)n行，每行m個(gè)數(shù)字，用空格隔開(kāi)。0表示該塊土地有瑕疵，1表示該塊土地完好。 【輸出文件】 一個(gè)整數(shù)，最大正方形的邊長(zhǎng)。 【輸入樣例】 4 4 0 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 【輸出樣例】 2 【問(wèn)題分析】 題目中說(shuō)要求一個(gè)最大的符合條件的正方形，所以就想到判斷所有的正方形是否合法。 這個(gè)題目直觀的狀態(tài)表示法是opt[i,j,k]基類型是boolean，判斷以（i,j）點(diǎn)為左上角（其實(shí)任意一個(gè)角都可以，依據(jù)個(gè)人習(xí)慣）,長(zhǎng)度為K的正方形是否合理，再找到一個(gè)K值最大的合法狀態(tài)就可以了（用true表示合理，false表示不合理）。其實(shí)這就是遞推，（決策唯一）。 遞推式： opt[i,j,k]=opt[i+1,j+1,k-1] and opt[i+1,j,k-1] and opt[i,j+1,k-1] and (a[i,j]=1) 時(shí)間復(fù)雜度： 狀態(tài)數(shù)O（N3）*轉(zhuǎn)移代價(jià)O（1）=總復(fù)雜度O（N3） 空間復(fù)雜度： O（N3） 由于空間復(fù)雜度和時(shí)間復(fù)雜度都太高，不能AC，我們就的再想想怎么優(yōu)化？ 顯然何以用滾動(dòng)數(shù)組優(yōu)化空間，但是時(shí)間復(fù)雜度仍然是O（N3）。這就需要我們找另外一種簡(jiǎn)單的狀態(tài)表示法來(lái)解了。 仔細(xì)分析這個(gè)題目，其實(shí)我們沒(méi)必要知道正方形的所有長(zhǎng)度，只要知道以一個(gè)點(diǎn)為左上角的正方形的最大合理長(zhǎng)度就可以了。 如果這個(gè)左上角是0那么它的最大合理長(zhǎng)度自然就是0（不可能合理）。 如果這個(gè)左上角是1呢？ 回顧上面的遞推式，我們考慮的是以它的右面，下面，右下這個(gè)三個(gè)方向的正方形是否合理，所以我們還是要考慮這三個(gè)方向。具體怎么考慮呢？ 如果這三個(gè)方向合理的最大邊長(zhǎng)中一個(gè)最小的是X，那么它的最大合理邊長(zhǎng)就是X+1。為什么呢？ 看個(gè)例子： 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 上例中紅色的正方形，以（1,3）點(diǎn)為左上角，以（1，4），（2，3），（2，4）這三個(gè)點(diǎn)的最大合理邊長(zhǎng)分別是2，1，2。其中最小的是以（2，3）為左上角的正方形，最大合理邊長(zhǎng)是1。因?yàn)槿齻€(gè)方向的最大合理邊長(zhǎng)大于等于1，所以三個(gè)方向上邊長(zhǎng)為1的正方形是合理的，即上面低推式中: opt[1,3,2]=opt[1,4,1] and opt[2,3,1] and opt[2,4,1] and (a[1,3]=1) = true 成立 這樣就把一個(gè)低推判定性問(wèn)題轉(zhuǎn)化成最優(yōu)化問(wèn)題從而節(jié)省空間和時(shí)間。 具體實(shí)現(xiàn)： 設(shè)計(jì)一個(gè)狀態(tài)opt[i,j]表示以（i,j）為左上角的正方形的最大合理邊長(zhǎng)。 狀態(tài)轉(zhuǎn)移方程： min{opt[i+1,j],opt[i,j+1],opt[i+1,j+1]}+1 (a[i,j]=1) opt[i,j]=0 (a[i,j]=0) 時(shí)間復(fù)雜度：狀態(tài)數(shù)O（N2）*轉(zhuǎn)移代價(jià)O（1）=總代價(jià)O（N2） 空間復(fù)雜度：O（N2） 【源代碼】 program P1057; const maxn=1010; var opt,a:array[0..maxn,0..maxn] of longint; n,m,ans:longint; procedure init; var i,j:longint; begin read(n,m); for i:=1 to n do for j:=1 to m do read(a[i,j]); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); for i:=n downto 1 do for j:=m downto 1 do if a[i,j]<>0 then begin opt[i,j]:=opt[i+1,j]; if opt[i,j+1]<opt[i,j] then opt[i,j]:=opt[i,j+1]; if opt[i+1,j+1]<opt[i,j] then opt[i,j]:=opt[i+1,j+1]; inc(opt[i,j]); end; ans:=0; for i:=1 to n do for j:=1 to m do if opt[i,j]>ans then ans:=opt[i,j]; writeln(ans); end; begin init; main; end. |
