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