信息學聯賽知識：動態規劃的狀態表示(二)

　　動態規劃的狀態表示(二)

　　三、狀態表示對動態規劃性能的影響

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

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

　　狀態表示2-3

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

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

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

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

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

　　對于連續多邊形（X，Y），只要我們選擇邊（X，Y）與頂點Z(X<Z<Y)連接，那么（X，Y）劃分為三部分：連續多邊形（X，Z）、連續多邊形（Z，Y）和三角形（X,Z,Y）。（X，Y）的最優劃分包含了（X，Z）、（Z，Y）的最優劃分，滿足最優子結構性質。

　　注意到初始多邊形是一個連續多邊形，根據數學歸納法，它的子問題都是連續多邊形。因此二元組（X，Y）是一個正確的狀態表示。狀態轉移方程為

　　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），在本文的假設條件下，使用基本堆空間可以處理頂點數700以內的多邊形。下面是求連續多邊形最優劃分區域數的函數。

　　[算法2-3]：

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

　　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); {子多邊形的最優劃分}

　　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

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

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

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

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

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

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

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

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

　　a

　　(a#a)

　　((a#a)#a)

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

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

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

　　狀態表示3-1

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

　　狀態表示3-2

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

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

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

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

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

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

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

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

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