【正文】 把握本質(zhì)，靈活運(yùn)用——?jiǎng)討B(tài)規(guī)劃的深入探討把握本質(zhì)，靈活運(yùn)用——?jiǎng)討B(tài)規(guī)劃的深入探討浙江省蕭山中學(xué) 來煜坤【關(guān)鍵字】 動(dòng)態(tài)規(guī)劃 構(gòu)思 實(shí)現(xiàn)【摘要】 本文討論了動(dòng)態(tài)規(guī)劃這一思想的核心內(nèi)容和其基本特點(diǎn)，探討了動(dòng)態(tài)規(guī)劃思想的適用范圍，動(dòng)態(tài)規(guī)劃子問題空間和遞推關(guān)系式確立的一般思路。通過例子說明在子問題確立過程中的一些問題的解決辦法：通過加強(qiáng)命題或適當(dāng)調(diào)節(jié)確定狀態(tài)的變量等手段幫助建立動(dòng)態(tài)規(guī)劃方程，通過預(yù)處理使動(dòng)態(tài)規(guī)劃的過程容易實(shí)現(xiàn)等。接著，分析動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)中可能出現(xiàn)的空間溢出問題及一些解決辦法。總結(jié)指出，動(dòng)態(tài)規(guī)劃這一思想，關(guān)鍵還在于對不同的問題建立有效的數(shù)學(xué)模型，在把握本質(zhì)的基礎(chǔ)上靈活運(yùn)用一、引言 動(dòng)態(tài)規(guī)劃是一種重要的程序設(shè)計(jì)思想，具有廣泛的應(yīng)用價(jià)值。使用動(dòng)態(tài)規(guī)劃思想來設(shè)計(jì)算法，對于不少問題往往具有高時(shí)效，因而，對于能夠使用動(dòng)態(tài)規(guī)劃思想來解決的問題，使用動(dòng)態(tài)規(guī)劃是比較明智的選擇。能夠用動(dòng)態(tài)規(guī)劃解決的問題，往往是最優(yōu)化問題，且問題的最優(yōu)解(或特定解)的局部往往是局部問題在相應(yīng)條件下的最優(yōu)解，而且問題的最優(yōu)解與其子問題的最優(yōu)解要有一定的關(guān)聯(lián)，要能建立遞推關(guān)系。如果這種關(guān)系難以建立，即問題的特定解不僅依賴于子問題的特定解，而且與子問題的一般解相關(guān)，那么，一方面難以記錄下那么多的“一般解”，另一方面，遞推的效率也將是很低的；此外，為了體現(xiàn)動(dòng)態(tài)規(guī)劃的高時(shí)效，子問題應(yīng)當(dāng)是互相重疊的，即很多不同的問題共享相同的子問題。(如果子問題不重疊，則宜使用其它方法，如分治法等。)動(dòng)態(tài)規(guī)劃一般可以通過兩種手段比較高效地實(shí)現(xiàn)，其一是通過自頂向下記憶化的方法，即通過遞歸或不遞歸的手段，將對問題最優(yōu)解的求解，歸結(jié)為求其子問題的最優(yōu)解，并將計(jì)算過的結(jié)果記錄下來，從而實(shí)現(xiàn)結(jié)果的共享；另一種手段，也就是最主要的手段，通過自底向上的遞推的方式，由于這種方式代價(jià)要比前一種方式小，因而被普遍采用，下面的討論均采用這種方式實(shí)現(xiàn)。動(dòng)態(tài)規(guī)劃之所以具有高時(shí)效，是因?yàn)樗趯栴}規(guī)模不斷減小的同時(shí)，有效地把解記錄下來，從而避免了反復(fù)解同一個(gè)子問題的現(xiàn)象，因而只要運(yùn)用得當(dāng)，較之搜索而言，效率就會有很大的提高。動(dòng)態(tài)規(guī)劃的思想，為我們解決與重疊子問題相關(guān)的最優(yōu)化問題提供了一個(gè)思考方向：通過迭代考慮子問題，將問題規(guī)模減小而最終解決問題。適于用動(dòng)態(tài)規(guī)劃解決的問題，是十分廣泛的。動(dòng)態(tài)規(guī)劃的思想本身是重要的，但更重要的是面對具體問題的具體分析。要分析問題是否具備使用動(dòng)態(tài)規(guī)劃的條件，確定使用動(dòng)態(tài)規(guī)劃解題的子問題空間和遞推關(guān)系式等，以及在(常規(guī))內(nèi)存有限的計(jì)算機(jī)上實(shí)現(xiàn)這些算法。下面分別就構(gòu)思和實(shí)現(xiàn)兩個(gè)方面進(jìn)一步探討動(dòng)態(tài)規(guī)劃這一思想。二、動(dòng)態(tài)規(guī)劃解題的構(gòu)思當(dāng)我們面對一個(gè)問題考慮用動(dòng)態(tài)規(guī)劃時(shí)，十分重要的一點(diǎn)就是判斷這個(gè)問題能否用動(dòng)態(tài)規(guī)劃高效地解決。用動(dòng)態(tài)規(guī)劃構(gòu)思算法時(shí)，往往要考慮到這個(gè)問題所涉及到的子問題(子問題空間)，以及如何建立遞推式，并最終實(shí)現(xiàn)算法。其實(shí)，這些過程往往是交織在一起的，子問題空間與遞推關(guān)系本身就是緊密相聯(lián)的，為了有效地建立起遞推關(guān)系，有時(shí)就要調(diào)整子問題空間；而根據(jù)大致確定的子問題空間又可以啟發(fā)我們建立遞推關(guān)系式。而能否最終用一個(gè)遞推關(guān)系式來聯(lián)系問題與其子問題又成了判斷一個(gè)問題能否使用動(dòng)態(tài)規(guī)劃思想解決的主要依據(jù)。因而孤立地來看這其中的每一部分，硬把思考過程人為地分成幾個(gè)部分，是困難的，也是不必要的。而且動(dòng)態(tài)規(guī)劃這種思想方法，沒有固定的數(shù)學(xué)模型，要因題而異，因而也就不可能歸納出一種“萬能”的方法。但是對大多數(shù)問題而言，還是能夠有一個(gè)基本的思考方向的。首先，要大致分析一個(gè)問題是否可能用動(dòng)態(tài)規(guī)劃解決。如果一個(gè)問題難以確定子問題，或問題與其子問題的特殊解之間毫無關(guān)系，就要考慮使用其它方法來解決(如搜索或其它方法等)。做一個(gè)大概的判斷是有必要的，可以防止在這上面白花時(shí)間。通常一個(gè)可以有效使用動(dòng)態(tài)規(guī)劃解決的問題基本上滿足以下幾方面的特性： 子問題的最優(yōu)解僅與起點(diǎn)和終點(diǎn)(或有相應(yīng)代表意義的量)有關(guān)而與到達(dá)起點(diǎn)、終點(diǎn)的路徑無關(guān)。 大量子問題是重疊的，否則難以體現(xiàn)動(dòng)態(tài)規(guī)劃的優(yōu)越性。下面以IOI’97的“字符識別”問題為例進(jìn)行分析一般情況下動(dòng)態(tài)規(guī)劃思路的建立。IOI’97的字符識別問題，題目大意是：(空格)、A—Z這27個(gè)符號的字形說明。對每一個(gè)符號的字符點(diǎn)陣，用20行每行20個(gè)“0”或者“1”表示。在另一個(gè)輸入文件中，描述了一串字符的點(diǎn)陣圖象(共N行)，但字符可能是“破損的”，即有些0變成了1，而有些1變成了0。每行固定也為20個(gè)“0”或“1”，但每一個(gè)字符對應(yīng)的行可能出現(xiàn)如下情形：* 仍為20行，此時(shí)沒有丟失的行也沒有被復(fù)制的行；* 為19行，此時(shí)有一行被丟失了；* 為21行，此時(shí)有一行被復(fù)制了，復(fù)制兩行可能出現(xiàn)不同的破損。要求輸出，在一個(gè)假定的行的分割情況下，使得“0”與“1”的反相最少的方案所對應(yīng)的識別結(jié)果(字符串)。在初步確定這個(gè)問題可以用動(dòng)態(tài)規(guī)劃思想解決之后，我認(rèn)為可以考慮用數(shù)學(xué)的方法(或觀點(diǎn))來刻劃這個(gè)問題，比如通常的最優(yōu)化問題(這也是動(dòng)態(tài)規(guī)劃解決的主要問題)，總會有一個(gè)最優(yōu)化的標(biāo)準(zhǔn)，動(dòng)態(tài)規(guī)劃要通過遞推來實(shí)現(xiàn)，就要求分析確定這個(gè)狀態(tài)所需要的量。比如字符識別問題，在問題規(guī)模下相當(dāng)于求N行的一種分割與對應(yīng)方法，因而很自然地，考慮前幾行就成了一個(gè)確定狀態(tài)的量。最優(yōu)的標(biāo)準(zhǔn)題中已經(jīng)給出，即在某種假設(shè)(包括分割方法與對應(yīng)識別方法)下，使得“0”與“1”反相數(shù)最少。如果把這個(gè)度量標(biāo)準(zhǔn)看作一個(gè)函數(shù)，這實(shí)際上就是一個(gè)最優(yōu)化函數(shù)(指標(biāo)函數(shù))，最優(yōu)化函數(shù)的值依賴于自變量，即確定狀態(tài)的量。自變量的個(gè)數(shù)(這里是一個(gè)，即行數(shù)，考慮前幾行之意)，要因題而異，關(guān)鍵是要有效地確定狀態(tài)，在這種狀態(tài)下，因保證靠這些量已經(jīng)能夠確定最優(yōu)化函數(shù)的值，即最優(yōu)化函數(shù)在這些量確定的時(shí)候理論上應(yīng)有確定的值，否則量是不夠的或要使用其它量來刻劃，而即使能夠完全確定，但在建立遞推關(guān)系式時(shí)發(fā)生困難，也要根據(jù)困難相應(yīng)調(diào)整確定最優(yōu)化函數(shù)值的自變量。而反過來，如果設(shè)定了過多的量來確定最優(yōu)化函數(shù)值，那么，動(dòng)態(tài)規(guī)劃的效率將會大大下降，或者解了許多不必要解的子問題，或者將重疊子問題變成了在這種自變量條件下的非重疊子問題，從而大大降低效率，甚至完全失去動(dòng)態(tài)規(guī)劃的高效。在這個(gè)例子中，對于前L行，此最優(yōu)化函數(shù)顯然有確定的值。動(dòng)態(tài)規(guī)劃的遞推的一種重要思想是將復(fù)雜的問題分解為其子問題。因而確定子問題空間及建立遞推關(guān)系式是十分重要的。根據(jù)確定最優(yōu)化函數(shù)值的自變量，往往對子問題空間有著暗示的作用。通常，通過對最接近問題的這步進(jìn)行倒推，可以得到這個(gè)問題規(guī)模減小一些的子問題，不斷這樣迭代考慮，就往往能夠體會到問題的子問題空間。而在這個(gè)過程中，通過這種倒推分析，也比較容易得出這種遞推關(guān)系。需要指出，這僅僅是對一些題目解題思考過程的總結(jié)，不同的題目原則上仍應(yīng)區(qū)別對待。比如字符識別問題，考慮n行該最優(yōu)化函數(shù)值時(shí)，注意到最終一定是按照字符分割與識別的，因而最后一個(gè)字符或者是19行，或者是20行，再或者是21行，僅這樣三種可能情況，依次考慮這三種分割方法，對于切割下來的這一段對應(yīng)于一個(gè)字符，對于每一種切割方案，當(dāng)然應(yīng)該選擇最匹配的字符(否則，如果不使用反相情況最少的字符作為匹配結(jié)果而導(dǎo)致全局的最優(yōu)，那么只要在這一步換成反相情況最少的字符，就得到比假定的“最優(yōu)”更優(yōu)的結(jié)果，從而導(dǎo)致矛盾)。在去除一個(gè)字符后，行數(shù)有所減少，而這些行去匹配字符顯然也應(yīng)當(dāng)使用最優(yōu)的匹配(可以用反證法證明，與前述類似)，于是得到一個(gè)與原問題相似(同確定變量，同最優(yōu)化標(biāo)準(zhǔn))但規(guī)模較小的子問題，與此同時(shí)子問題與原問題的遞推關(guān)系事實(shí)上也得到了建立：f[i]:=min{Compare19[i19+1]+f[i19],Compare20[i20+1]+f[i20], Compare21[i21+1]+f[i21]}f[i]表示對前i行進(jìn)行匹配的最優(yōu)化函數(shù)值；Compare19[i]、Compare20[i]、Compare21[i]分別表示從i行開始的19行、20行、21行與這三種匹配方式下最接近的字符的反相的“0”與“1”的個(gè)數(shù)。初始情況，f[0]=0，對于不可能匹配的行數(shù)，用一個(gè)特殊的大數(shù)表示即可。當(dāng)然，本題的問題主要還不在于動(dòng)態(tài)規(guī)劃的基本思考上(這里只是通過這個(gè)例子，講一下對于不少動(dòng)態(tài)規(guī)劃問題的一種基本的思考方向)，還有數(shù)學(xué)建模(用2進(jìn)制表示0、1串)等(源程序見附錄中的程序1)。有時(shí)雖然按上述思路得出的確定狀態(tài)的量已經(jīng)能夠使最優(yōu)化函數(shù)具有確定的值，但是在建立遞推關(guān)系時(shí)發(fā)生困難，通過引入新的變量或調(diào)整已有變量，也是一條克服困難的途徑。比如，NOI’97的一題“積木游戲”，題目大意是：積木是一個(gè)長方體，已知N個(gè)有編號的積木的三邊(a、b、c邊)長，要求出用N塊中的若干塊堆成M(1≤M≤N≤100)堆，使總高度最大的高度值，且滿足：* 第K堆中任意一塊的編號大于第K+1堆中任意一塊積木的編號；* 任意相鄰兩塊，下面的塊的上表面要能包含上面的那塊的下表面，且下面的塊的編號要小于上面積木的編號。因?yàn)轭}目要求編號小的堆的積木編號較大，這不太自然，在不改變結(jié)果的前提下，把題目改作編號小的堆的積木編號較小，這顯然不會影響到最終的高度和，而且，此時(shí)每一種合理的堆放方法可看作，按編號遞增的順序選擇若干積木，按堆編號遞增的順序逐堆放置，每堆中積木依次在前一個(gè)上面堆放而最終形成一種堆放方案。使用上面一般的分析方法，很容易看出，考慮前i個(gè)木塊放置成前j堆，這樣，i、j兩個(gè)量顯然能夠確定最優(yōu)函數(shù)的值，然而遞推關(guān)系卻不易直接建立，稍作分析就會發(fā)現(xiàn)，問題主要出在第i塊到底能否堆放到其子問題(i1,j作變量確定的狀態(tài))的最優(yōu)解方案的最后一堆上。如果考慮增加該序列最后一塊的頂部的長與寬的(最小)限制這兩個(gè)變量，建立遞推關(guān)系并不困難，然而，很明顯，遞推過程中大量結(jié)果并未被用到，這就人為地?cái)U(kuò)大了子問題空間，不僅給存儲帶來麻煩，而且效率也很低。其實(shí)，建立遞推需要的僅僅是在子問題解最后一堆頂部能否容納當(dāng)前積木塊，而題中可能產(chǎn)生的這種限制性的面最多僅有3*100+1(無限制)=301種情況，這樣在多引入一個(gè)“最后一堆頂部能夠容納下第k種面的要求”這個(gè)量后，遞推關(guān)系只要分當(dāng)前塊另起一堆、當(dāng)前塊加在前一堆上(如果可能的話)和當(dāng)前塊不使用這三種情況就可以了。(源程序參見所附程序2)此外，有些問題可能會出現(xiàn)僅靠這種調(diào)整遞推關(guān)系仍難以建立，這時(shí)，通過增加其它量或函數(shù)來建立遞推關(guān)系式也是一種思考方向(類似于數(shù)學(xué)歸納法證明時(shí)的“加強(qiáng)命題”)。因?yàn)?，用?dòng)態(tài)規(guī)劃解題的一個(gè)重要特征是通過遞推，而遞推是利用原有結(jié)果得到新結(jié)果的過程。如果在理論上可以證明，一個(gè)難以直接實(shí)現(xiàn)遞推的問題可以通過引入新的遞推關(guān)系，同時(shí)將兩者解決，這看起來把問題復(fù)雜化了，而實(shí)際上由于對于每一步遞推，在增加了解決的問題的同時(shí)也增加了條件（以前解決的值），反而使遞推容易進(jìn)行。舉例說明，IOI’98中的“多邊形”一題，大意如下：有一個(gè)多邊形（N邊形），頂點(diǎn)上放整數(shù)，邊上放“+”或“*”，要尋找一種逐次運(yùn)算合并的順序，通過N1次運(yùn)算，使最后結(jié)果最大。如果單純考慮用MAX[I,L]，從I開始進(jìn)行L個(gè)運(yùn)算所得的最大值，則難以實(shí)現(xiàn)遞推，而根據(jù)數(shù)學(xué)知識，引入了MIN[I,L]為從I開始進(jìn)行L個(gè)運(yùn)算所得的最小值，在進(jìn)行遞推時(shí)，卻能夠有效地用較小的I，L來得到較大時(shí)的結(jié)果，從而事實(shí)上同時(shí)解決了最小值與最大值兩個(gè)問題。遞推關(guān)系式如下：(考慮I從1到N,L從1到N1)考慮t(最后一步運(yùn)算位置)從0到L1：如果最后一步運(yùn)算為“+”則： min(i,L)=最小值{min(i,t)+min((i+t+11) mod N+1,Lt1)} max(i,L)=最大值{max(i,t)+max((i+t+11) mod N+1,Lt1)}如果最后一步運(yùn)算為“*”則： min(i,L)=最小值{min(i,t)*min((i+t+11) mod N+1,Lt1), min(i,t)*max((i+t+11) mod N+1,Lt1), max(i,t)*min((i+t+11) mod N+1,Lt1), max(i,t)*max((i+t+11) mod N+1,Lt1)} max(i,L)=最大值{min(i,t)*min((i+t+11) mod N+1,Lt1), min(i,t)*max((i+t+11) mod N+1,LT1) max(i,t)*min((i+t+11) mod N+1,Lt1), max(i,t)*max((i+t+11) mod N+1,Lt1)}(源程序見附錄中的程序3)此外，動(dòng)態(tài)規(guī)劃通過遞推來實(shí)現(xiàn)，因而問題與子問題越相似，越有規(guī)律就越容易進(jìn)行操作。因而對于某些自身的階段和規(guī)律不怎么明顯的問題，可以通過一個(gè)預(yù)處理，使其變得更整齊，更易于實(shí)現(xiàn)。例如，ACM’97亞洲賽區(qū)/上海區(qū)競賽一題“正則表達(dá)式(Regular Expression)的匹配”問題，題目大意是：正則表達(dá)式是含有通配符的表達(dá)式，題目定義的廣義符有：* . 表示任何字符* [c1c2] 表示字符c1與c2間的任一字符* [^c1c2] 表示不在字符c1與c2間的任一字符* * 表示它前面的字符可出現(xiàn)0或多次* + 表示它前面的字符可出現(xiàn)一次或多次* \ 表示它后面的字符以一個(gè)一般字符對待。 對一個(gè)輸入串，尋找最左邊的與正則表達(dá)式匹配的串(相同條件下要最長的)。這里如果不作預(yù)處理，則有時(shí)一個(gè)廣義符可對應(yīng)多個(gè)字符，有時(shí)又是多個(gè)廣義符僅對應(yīng)一個(gè)字符，給系統(tǒng)化處理帶來很多麻煩。因而有必要對正則表達(dá)式進(jìn)行標(biāo)準(zhǔn)化，使得或者某個(gè)結(jié)點(diǎn)僅對應(yīng)一個(gè)字符，或者用一特殊標(biāo)記表明它可以重復(fù)多次。定義記錄類型：NodeType=Record StartChar: Char。 {開始字符} EndChar: Char。 {結(jié)束字符} Belong: Boolean {是否