信息學聯(lián)賽知識：動態(tài)規(guī)劃的狀態(tài)表示(二)

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

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

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

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

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

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

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

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

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

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

　　對于連續(xù)多邊形（X，Y），只要我們選擇邊（X，Y）與頂點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)子結構性質(zhì)。

　　注意到初始多邊形是一個連續(xù)多邊形，根據(jù)數(shù)學歸納法，它的子問題都是連續(xù)多邊形。因此二元組（X，Y）是一個正確的狀態(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,

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

　　子問題空間復雜度是O（n2），在本文的假設條件下，使用基本堆空間可以處理頂點數(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）要連接的頂點}

　　if 頂點j與頂點s、t連接合法 then

　　begin

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

　　If 頂點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)表示描述的子問題空間以及相應動態(tài)規(guī)劃算法的時空性能。在圖7中，動態(tài)規(guī)劃的時間復雜度、空間復雜度與子問題空間增長是同階的。事實上，這樣的關系不僅僅局限于這個例子，它具有普遍意義。首先，動態(tài)規(guī)劃空間花費主要是用來存儲描述子問題的狀態(tài)表示，因此空間復雜度自然隨著子問題的增多而增大。其次，動態(tài)規(guī)劃的時間花費主要取決于要解決的不同子問題的數(shù)目，隨著子問題數(shù)目的增多，時間復雜度當然就增大了。

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

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

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

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

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

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

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

　　a

　　(a#a)

　　((a#a)#a)

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

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

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

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

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

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

　　因為對每個數(shù)而言，各位數(shù)字和與最大數(shù)字、最小數(shù)字兩個信息具有獨立性，我們可以分別記錄這兩個信息。用一元組（X）表示各位數(shù)字和，用二元組（Y,Z）表示最大數(shù)字、最小數(shù)字。

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

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

　　因為一次運算后的數(shù)值最大是三位數(shù)，各位數(shù)值和不超過27，用來存儲數(shù)值和的數(shù)組可定義為

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

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

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

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

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