信息學(xué)聯(lián)賽知識(shí)：動(dòng)態(tài)規(guī)劃的狀態(tài)表示(二)

　　動(dòng)態(tài)規(guī)劃的狀態(tài)表示(二)

　　三、狀態(tài)表示對(duì)動(dòng)態(tài)規(guī)劃性能的影響

　　我們分析問題的時(shí)候，總是從不同的角度去思考，以便能全面、本質(zhì)地認(rèn)識(shí)問題。分析問題的狀態(tài)表示，我們也是盡可能從不同角度去思考。由此會(huì)得到對(duì)問題的不同狀態(tài)表示，從動(dòng)態(tài)規(guī)劃原理來看，其中有些狀態(tài)表示不能合乎要求，而在滿足要求的那些狀態(tài)表示中，我們可以以之為基礎(chǔ)，構(gòu)造動(dòng)態(tài)規(guī)劃模型，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法。在通常情況下，基于不同的狀態(tài)表示的動(dòng)態(tài)規(guī)劃算法性能存在著差異，這主要從算法的時(shí)間復(fù)雜度和空間復(fù)雜度體現(xiàn)出來。

　　上面介紹了問題二的兩種狀態(tài)表示， 狀態(tài)表示2-1從問題的自然特征來思考， 提出對(duì)一般多邊形的表示方法，具有其通用性，狀態(tài)表示2-2則根據(jù)多邊形劃分中關(guān)于頂點(diǎn)劃分的性質(zhì)來思考，進(jìn)而提出了半連續(xù)多邊形， 現(xiàn)在我們考慮關(guān)于多邊形邊的劃分性質(zhì)，提出狀態(tài)表示2-3， 并比較三種狀態(tài)表示，探討狀態(tài)表示對(duì)動(dòng)態(tài)規(guī)劃性能的影響。

　　狀態(tài)表示2-3

　　定義2-3 多邊形（A1,A2,…,Ak）是由多邊形（1，2，…，N）劃分而來的多邊形，我們稱多邊形（A1,A2,…,Ak）為連續(xù)多邊形，當(dāng)且僅當(dāng)Ai+1 = Ai+1 ,

　　k>i >0。圖6中多邊形（3，4，5，6，7）就是一個(gè)連續(xù)多邊形。

　　性質(zhì)2-3 對(duì)于一個(gè)多邊形，它的任一條邊一定與另一個(gè)頂點(diǎn)組成三角形。如圖5，邊（1，2）可以與頂點(diǎn)4等頂點(diǎn)相連，形成三角形。

　　根據(jù)性質(zhì)2-3， 對(duì)多邊形劃分時(shí)，我們可以按需要選擇邊來與其他頂點(diǎn)相連，而不會(huì)遺漏多邊形的任一種劃分，自然也不會(huì)遺漏多邊形的最優(yōu)劃分。

　　連續(xù)多邊形（X，X+1，,…,Y）可以用二元組（X,Y）來表示，則D(X,Y)表示連續(xù)多邊形的劃分區(qū)域數(shù)。

　　對(duì)于連續(xù)多邊形（X，Y），只要我們選擇邊（X，Y）與頂點(diǎn)Z(X<Z<Y)連接，那么（X，Y）劃分為三部分：連續(xù)多邊形（X，Z）、連續(xù)多邊形（Z，Y）和三角形（X,Z,Y）。（X，Y）的最優(yōu)劃分包含了（X，Z）、（Z，Y）的最優(yōu)劃分，滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。

　　注意到初始多邊形是一個(gè)連續(xù)多邊形，根據(jù)數(shù)學(xué)歸納法，它的子問題都是連續(xù)多邊形。因此二元組（X，Y）是一個(gè)正確的狀態(tài)表示。狀態(tài)轉(zhuǎn)移方程為

　　D(X,Y) = min(g(X,Y,Z) + D(X,Z)+D(Z,Y)), X<Z<Y,

　　f(i,i) = 0, n+1>i>0,

　　當(dāng)x,y,z在一條直線時(shí)，g(x,y,z) = 0, 否則g(x,y,z) = 1。

　　子問題空間復(fù)雜度是O（n2），在本文的假設(shè)條件下，使用基本堆空間可以處理頂點(diǎn)數(shù)700以內(nèi)的多邊形。下面是求連續(xù)多邊形最優(yōu)劃分區(qū)域數(shù)的函數(shù)。

　　[算法2-3]：

　　function Dynamic(s, t : integer) : integer; {求連續(xù)多邊形（s,t）的最優(yōu)劃分}

　　var j, tot : integer;

　　begin

　　if D[s, t][1] = 255 then

　　if t - s = 1 then D[s, t][1] := 0

　　else

　　begin

　　for j := s + 1 to t - 1 do {j 是邊（s,t）要連接的頂點(diǎn)}

　　if 頂點(diǎn)j與頂點(diǎn)s、t連接合法 then

　　begin

　　Tot := Dynamic(s, j) + Dynamic(j, t); {子多邊形的最優(yōu)劃分}

　　If 頂點(diǎn)s、t、j不在一條直線上 then Tot := Tot + 1;

　　if Tot < D[s, t][1] then

　　begin

　　D[s, t][1] := Tot;

　　D[s, t][2] := j;

　　end;

　　end;

　　end;

　　Dynamic := D[s, t][1];

　　end;

　　圖7

　　我們來比較三種狀態(tài)表示描述的子問題空間以及相應(yīng)動(dòng)態(tài)規(guī)劃算法的時(shí)空性能。在圖7中，動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度、空間復(fù)雜度與子問題空間增長(zhǎng)是同階的。事實(shí)上，這樣的關(guān)系不僅僅局限于這個(gè)例子，它具有普遍意義。首先，動(dòng)態(tài)規(guī)劃空間花費(fèi)主要是用來存儲(chǔ)描述子問題的狀態(tài)表示，因此空間復(fù)雜度自然隨著子問題的增多而增大。其次，動(dòng)態(tài)規(guī)劃的時(shí)間花費(fèi)主要取決于要解決的不同子問題的數(shù)目，隨著子問題數(shù)目的增多，時(shí)間復(fù)雜度當(dāng)然就增大了。

　　既然不同的狀態(tài)表示會(huì)描述不同大小的子問題空間，那么原因何在呢？在這道題中，我們僅僅從多邊形的定義來看，有這樣的關(guān)系：{連續(xù)多邊形} 是{半連續(xù)多邊形}的子集，{半連續(xù)多邊形}是{多邊形}的子集。由此可知，應(yīng)該是狀態(tài)表示描述子問題不精確造成。

　　回顧狀態(tài)表示2-1和狀態(tài)表示2-2、2-3的分析，我們之所以采取狀態(tài)表示2-1 是基于對(duì)多邊形自然特征的認(rèn)識(shí)，而沒有考慮到在特定環(huán)境下多邊形劃分而成的子多邊形與多邊形本身有特殊的聯(lián)系。比較狀態(tài)表示2-2、2-3，兩者都利用了多邊形劃分的性質(zhì)，但顯然研究的深度不同。狀態(tài)表示2-3保證了每種劃分都是對(duì)多邊形的不同劃分，因?yàn)橹辽儆幸粭l邊所在的三角形是與其他劃分中所在的三角形不一樣。狀態(tài)2-2就不能保證這一點(diǎn)，如下圖所示的兩種劃分順序得出了同一種劃分。因?yàn)檫@種無意義的劃分而產(chǎn)生的多邊形屬于{半連續(xù)多邊形}-{連續(xù)多邊形}，如半連續(xù)多邊形（1，3，5）。

　　狀態(tài)表示的改進(jìn)不僅僅使動(dòng)態(tài)規(guī)劃的性能提高，通常也會(huì)使算法實(shí)現(xiàn)更加簡(jiǎn)潔。比較算法[2-2]、[2-3]我們就可以看出這一點(diǎn)。算法[2-3]的程序見附錄。

　　以上，我們主要討論狀態(tài)表示描述的子問題空間不同而影響動(dòng)態(tài)規(guī)劃。這是狀態(tài)表示影響動(dòng)態(tài)規(guī)劃性能的主要原因，但是在算法實(shí)現(xiàn)過程中，由于某種原因我們可能對(duì)同一子問題采取了不同的描述方法，存儲(chǔ)空間會(huì)產(chǎn)生極大的差異。下面這個(gè)例子說明了這個(gè)問題。

　　問題三： "#"這個(gè)操作符被定義為一個(gè)雙目運(yùn)算符，且兩個(gè)運(yùn)算對(duì)象為正整數(shù)，對(duì)于整數(shù)X，Y，# 號(hào)運(yùn)算定義為（X#Y）=十進(jìn)制數(shù)X各數(shù)字之和*十進(jìn)制數(shù)Y的最大數(shù)字+十進(jìn)制數(shù)Y的最小數(shù)字。例

　�。�9#30）=9*3+0=27，（30#9）=3*9+9=36

　　對(duì)于表達(dá)式我們約定或是一正數(shù)或是（表達(dá)式#表達(dá)式）。以下表達(dá)式是合法的表達(dá)式

　　a

　　(a#a)

　　((a#a)#a)

　　(a#(a#a)#(a#a)#a))

　　對(duì)于給定的十進(jìn)制正數(shù)a和表達(dá)式的值K，計(jì)算具有K值的表達(dá)式中"#"的個(gè)數(shù)。具有k值的表達(dá)式可能有許多，并且具有不同的#個(gè)數(shù)，只需輸出最小個(gè)數(shù)。a，k是均不大于1000000000的正整數(shù)。

　　運(yùn)算時(shí)，我們描述的是正整數(shù)k的各位數(shù)字和、最大數(shù)字和最小數(shù)字兩個(gè)信息（這里把最大、最小數(shù)字看成一個(gè)信息）以及得到k所用的最少 # 數(shù)，那么可以有兩種狀態(tài)表示。

　　狀態(tài)表示3-1

　　我們用一元組（k）表示正數(shù)k, D(k)表示所用的#數(shù)目。(k)已經(jīng)隱含了各數(shù)字和、最大數(shù)字和最小數(shù)字兩個(gè)信息。

　　狀態(tài)表示3-2

　　因?yàn)閷?duì)每個(gè)數(shù)而言，各位數(shù)字和與最大數(shù)字、最小數(shù)字兩個(gè)信息具有獨(dú)立性，我們可以分別記錄這兩個(gè)信息。用一元組（X）表示各位數(shù)字和，用二元組（Y,Z）表示最大數(shù)字、最小數(shù)字。

　　我們對(duì)輸入的數(shù)a進(jìn)行特殊處理，而一次運(yùn)算后的最大數(shù)字不超過738，狀態(tài)表示3-1只要開一個(gè)數(shù)組，定義如下

　　Type NumBerType = array[1..738] of integer

　　因?yàn)橐淮芜\(yùn)算后的數(shù)值最大是三位數(shù)，各位數(shù)值和不超過27，用來存儲(chǔ)數(shù)值和的數(shù)組可定義為

　　Type TotalType = array[1..27] of integer

　　最大數(shù)字、最小數(shù)字與數(shù)大小無關(guān)，它們范圍在[0，9]，定義為

　　Type MaxMinType = array[0..9,0..9] of integer

　　狀態(tài)表示3-1用一元組同時(shí)記錄了兩個(gè)信息，而狀態(tài)表示3-2則分別記錄了這兩個(gè)信息。顯然狀態(tài)表示3-2所用的空間比狀態(tài)表示3-1所用的要小的多。同樣一個(gè)對(duì)象，只是由于我們采取不同的描述方法，所用的空間大小就迥然不同。程序見附錄。

　　綜上所述，狀態(tài)表示對(duì)動(dòng)態(tài)規(guī)劃的性能的影響是多方面的。因此，在解決問題時(shí)，從各方面比較狀態(tài)表示，根據(jù)具體情況選擇高效的狀態(tài)表示，才能進(jìn)一步優(yōu)化動(dòng)態(tài)規(guī)劃。