1D1D動(dòng)態(tài)規(guī)劃優(yōu)化初步

1D/1D動(dòng)態(tài)規(guī)劃優(yōu)化初步所謂1D/1D動(dòng)態(tài)規(guī)劃，指的是狀態(tài)數(shù)為O(n),每一個(gè)狀態(tài)決策量為O(n)的動(dòng)態(tài)規(guī)劃方程。直接求解的時(shí)間復(fù)雜度為O(n2),但是，絕大多數(shù)這樣的方程通過(guò)合理的組織與優(yōu)化都是可以優(yōu)化到O(nlogn)乃至O(n)的時(shí)間復(fù)雜度的。這里就想講一講我對(duì)一些比較初步的經(jīng)典的優(yōu)化方法的認(rèn)識(shí)。本文中不想進(jìn)行過(guò)多的證明與推導(dǎo),主要想說(shuō)明經(jīng)典模型的建立、轉(zhuǎn)化與求解方法。由于本人認(rèn)識(shí)與水平相當(dāng)有限,如果出現(xiàn)什么錯(cuò)誤與疏漏,還請(qǐng)大牛多多指正。另外,也希望大牛們更多地向我們介紹一下有關(guān)動(dòng)態(tài)規(guī)劃優(yōu)化的更深入的東西。本文中使用兩種方式表示一個(gè)函數(shù)：f(x)與f[x]，用方括號(hào)表示的函數(shù)值可以在規(guī)劃之前全部算出(常量),而用圓括號(hào)表示的函數(shù)值必須在規(guī)劃過(guò)程中計(jì)算得到(變量)。無(wú)論是什么函數(shù)值一經(jīng)確定，在以后的計(jì)算中就不會(huì)更改。經(jīng)典模型一： f(x)=min{f(i)+w[i,x]}i=1相信這個(gè)方程大家一定是不陌生的。另外，肯定也知道一個(gè)關(guān)于決策單調(diào)性的性質(zhì)：假如用k(X)表示狀態(tài)X取到最優(yōu)值時(shí)的決策，則決策單調(diào)性表述為：Vi<jki<kj)當(dāng)且僅當(dāng)：Vi<jwijl+w羊1,i1<W圧1,升]wi,j對(duì)于這個(gè)性質(zhì)的證明讀者可以在任意一篇講述四邊形不等式的文章中找到，所以這里不再重復(fù)。而且，從實(shí)戰(zhàn)的角度來(lái)看，我們甚至都不需要驗(yàn)證w函數(shù)的這個(gè)性質(zhì)，最經(jīng)濟(jì)也是最可靠的方法是寫一個(gè)樸素算法打出決策表來(lái)觀察(反正你總還是要對(duì)拍)。當(dāng)然，有的時(shí)候題目要求你做一點(diǎn)準(zhǔn)備工作，去掉一些明顯不可能的決策，然后在應(yīng)用決策單調(diào)性。這是上述性質(zhì)也許會(huì)有點(diǎn)用處。正如前文中所述，我們關(guān)注的重點(diǎn)是怎樣實(shí)現(xiàn)決策單調(diào)性。有了決策單調(diào)性，怎樣高效地實(shí)現(xiàn)它呢？很容易想到在枚舉決策的時(shí)候，不需要從1開(kāi)始，只要從k(x-1)開(kāi)始就可以了，但這只能降低常數(shù)，不可能起到實(shí)質(zhì)性的優(yōu)化。另一種想法是從k(x-1)開(kāi)始枚舉決策更新f(x),—旦發(fā)現(xiàn)決策u不如決策u+1來(lái)得好，就停止決策過(guò)程，選取決策u作為f(x)的最終決策。這樣時(shí)間是很大提高了，但可惜是不正確的。決策單調(diào)性并沒(méi)有保證f(j)+w[j,x]有什么好的性質(zhì)，所以這樣做肯定是不對(duì)的。剛才我們總是沿著“f(x)的最優(yōu)決策是什么”這個(gè)思路進(jìn)行思考，下面我們換一個(gè)角度，思考對(duì)于一個(gè)已經(jīng)計(jì)算出來(lái)的狀態(tài)f(j)，“f(j)能夠更新的狀態(tài)有哪些”。這樣，每一步過(guò)程中某些狀態(tài)的決策可能不是最優(yōu)的，但是當(dāng)算法結(jié)束的時(shí)候所有狀態(tài)對(duì)應(yīng)的決策一定是最優(yōu)的。一開(kāi)始，只有f(1)的函數(shù)值被計(jì)算出來(lái)，于是所有狀態(tài)的當(dāng)前最優(yōu)決策都是1。111111111111111111111111111111111111111111111111111111111111111現(xiàn)在，顯然f(2)的值已經(jīng)確定了：它的最有決策只能是1。我們用決策2來(lái)更新這個(gè)決策表。由于決策單調(diào)性，我們知道新的決策表只能有這樣的形式：1111111111111111111111111111222222222222222222222222222222這意味著我們可以使用二分法來(lái)查找“轉(zhuǎn)折點(diǎn)”因?yàn)槿绻谝粋€(gè)點(diǎn)X上，如果決策2更好，則所有比x大的狀態(tài)都是決策2更好；如果x上決策1更好，則所有比x小的狀態(tài)都是決策1更好。現(xiàn)在決策1和決策2都已經(jīng)更新完畢，則f(3)業(yè)已確定，現(xiàn)在用決策3來(lái)更新所有狀態(tài)。根據(jù)決策單調(diào)性，現(xiàn)在的決策表只能有以下2種類型：1111111111111111111111111111112222222222222222223333333333311111111111111111111111333333333333333333333333333333333333而這樣的決策表示絕對(duì)不會(huì)出現(xiàn)的：11111111111333333333333333333322222222222222222222222222222，不可能。那么，我們的更新算法就是：1、 考察決策2的區(qū)間[b,e]的b點(diǎn)上是否決策3更優(yōu)，如果是，則全部拋棄決策2,將此區(qū)間劃歸決策3；如果否，則在決策2的區(qū)間[b,e]中二分查找轉(zhuǎn)折點(diǎn)。2、 如果第1問(wèn)的回答是“是”，則用同樣的方法考察決策1。推演到這一步，相信決策單調(diào)性的實(shí)現(xiàn)算法已經(jīng)明了了：使用一個(gè)棧來(lái)維護(hù)數(shù)據(jù)，占中的每一個(gè)元素保存一個(gè)決策的起始位置與終了位置，顯然這些位置相互連接且依次遞增。當(dāng)插入一個(gè)新的決策時(shí)，從后到前掃描棧，對(duì)于每一個(gè)老決策來(lái)說(shuō)，做這樣兩件事：1、 如果在老決策的起點(diǎn)處還是新決策更好，則退棧，全額拋棄老決策，將其區(qū)間合并至新決策中，繼續(xù)掃描下一個(gè)決策。2、 如果在老決策的起點(diǎn)處是老決策好，則轉(zhuǎn)折點(diǎn)必然在這個(gè)老決策的區(qū)間中；二分查找之，然后新決策進(jìn)棧，結(jié)束。由于一個(gè)決策出棧之后再也不會(huì)進(jìn)入，所以均攤時(shí)間為0(1)，但是由于二分查找的存在，所以整個(gè)算法的時(shí)間復(fù)雜度為O(nlogn)。下面我們來(lái)看兩個(gè)例題。例題1：玩具裝箱。題目來(lái)源：湖南省選2008。題目大意：有n個(gè)玩具需要裝箱，每個(gè)玩具的長(zhǎng)度為c[i]，規(guī)定在裝箱的時(shí)候，必須嚴(yán)格按照給出的順序進(jìn)行，并且同一個(gè)箱子中任意兩個(gè)玩具之間必須且只能間隔一個(gè)單位長(zhǎng)度，換句話說(shuō)，如果要在一個(gè)箱子中裝編號(hào)為i~j的玩具，則箱子的長(zhǎng)度必須且只能是1=j—i+工c[k]，規(guī)定每一個(gè)長(zhǎng)度為l的箱子的費(fèi)用是P-(l-L)2，其中L是給定的k=i一個(gè)常數(shù)?，F(xiàn)在要求你使用最少的代價(jià)將所有玩具裝箱，箱子的個(gè)數(shù)無(wú)關(guān)緊要。分析：本題可以很輕松地列出一個(gè)1D1D的動(dòng)態(tài)規(guī)劃方程：f(x)=min{i+)w+[ X其中w[i,j]=(j—i+2Lc[k]-L)2。ii k=i不難驗(yàn)證這個(gè)方程式滿足決策單調(diào)性的，于是我們可以直接套用上文中的方法進(jìn)行優(yōu)化，時(shí)間復(fù)雜度為O(nlogn)。例題2：土地購(gòu)買題目來(lái)源：USACOMonthly,March,2008,Gold題目大意：有N塊土地需要購(gòu)買，每塊土地都是長(zhǎng)方形的，有特定的長(zhǎng)與寬。你可以一次性購(gòu)買一組土地，價(jià)格是這組土地中長(zhǎng)的最大值乘以寬的最大值。比方說(shuō)一塊5*3的土地和一塊2*9的土地在一起購(gòu)買的價(jià)格就是9*3。顯然，怎樣分組購(gòu)買土地是一門學(xué)問(wèn)，你的任務(wù)就是設(shè)計(jì)一種方案用最少的錢買下所有的土地。分析：將所有土地按照長(zhǎng)度降序排列，依次檢索，則當(dāng)前土地的長(zhǎng)度必然在上一塊土地之內(nèi)，我們只需要考慮寬度就可以了。而在寬度的問(wèn)題上，當(dāng)前土地的行為只能是這樣：和前面若干塊土地綁定；同時(shí)這些綁定的土地和他們前后的土地分離。這樣很容易得出狀態(tài)轉(zhuǎn)移方程：f(n)=miin{(maxw[i])*l[k+1]+f(k)}k=0i=k+1這個(gè)方程還不能滿足決策單調(diào)性，下面我們?cè)噲D再做一下簡(jiǎn)化。如果將每一個(gè)土地的尺寸看成是一個(gè)二維坐標(biāo)的話，(如下圖)其中不難看出，紅色點(diǎn)完全可以忽略，這些點(diǎn)(x,y)必然滿足一個(gè)性質(zhì)：存在點(diǎn)(x',y')同時(shí)滿足x'>=x且y'>=y,這樣它就能被一個(gè)組完全覆蓋。這些被忽略的點(diǎn)可以通過(guò)一次線形的掃描得出。下面，我們著重來(lái)看一下不能被忽略的這些點(diǎn)，它們的排布方式必然是單調(diào)減。因此狀態(tài)轉(zhuǎn)移方程可以寫成這個(gè)樣子：f(n)=mni1n{x[n]*y[k+1]+f(k)}k=0這個(gè)轉(zhuǎn)移方程就是標(biāo)準(zhǔn)的決策單調(diào)性了，讀者可以通過(guò)w函數(shù)的性質(zhì)直接證明它。然后，就用上文中的方法在O(nlogn)時(shí)間內(nèi)求解。以上兩個(gè)例子都是決策單調(diào)性的直接應(yīng)用。其中第二個(gè)例子稍微復(fù)雜一些，如果不忽略那些“肯定無(wú)用”的決策，不對(duì)數(shù)據(jù)進(jìn)行有序化，則方程是不滿足決策單調(diào)性的。這也就提醒我們?cè)谧鲞@一類題目的時(shí)候不能鉆牛角尖死做，還得靈活一點(diǎn)。另外，決策單調(diào)性提供的只是O(nlogn)的算法，事實(shí)上上面兩個(gè)例題的最佳算法都是O(n)的，在后文中我們將詳細(xì)介紹另外一種經(jīng)典模型，并且試圖將這兩個(gè)規(guī)劃方程通過(guò)數(shù)學(xué)變換轉(zhuǎn)向另一個(gè)模型。下面我們來(lái)看一類特殊的w函數(shù)：Vi<j<k,w[i,j]+w[j,k]二w[i,k]，顯然，這一類函數(shù)都是滿足決策單調(diào)性的。但是不同的是，由于這一類函數(shù)的特殊性，他們可以用一種更加簡(jiǎn)潔也更加有借鑒意義的方法解決。由于w函數(shù)滿足Vi<j<k,w[i,j]+w[j,k]二w[i,k]，我們總是可以找到一個(gè)特定的一元函數(shù)w'x],使得Vi<j,w[i,j]二w'[j]-w'[x]，這樣，假設(shè)狀態(tài)f(x)的某一個(gè)決策是k，有：其中g(shù)(k)二f(k)—w[1,k]。f(x)=f(k)+w[k,x]=f(k)+w'[x]-w'[k]=g(k)+w'[x]其中g(shù)(k)二f(k)—w[1,k]。這樣我們發(fā)現(xiàn)：一旦f(k)被確定，相應(yīng)地g(k)也被確定，更加關(guān)鍵的是，無(wú)論k值如何，w'[x]-w'[1]總是一個(gè)常數(shù)。換句話說(shuō)，我們可以把方程寫成下述形式：f(x)二miin{g(k)}+w[1,x]。不難發(fā)現(xiàn)這個(gè)方程是無(wú)聊的，因?yàn)閙!n{g(k)}我們可以用一k=1 k=1個(gè)變量“打擂臺(tái)”直接存儲(chǔ)；但是，如果舐的下界上加上一個(gè)限制，那這個(gè)方程就不是很無(wú)聊了。于是，我們就得到了另一個(gè)經(jīng)典模型。經(jīng)典模型一:f(x)=rnin{g(k)}+w[x]，其中，b[x]隨X不降。k=b[x]這個(gè)方程怎樣求解呢？我們注意到這樣一個(gè)性質(zhì)：如果存在兩個(gè)數(shù)j,k，使得j<=k，而且g(k)<=g(j)，則決策j是毫無(wú)用處的。因?yàn)楦鶕?jù)b[x]單調(diào)的特性，如果j可以作為合法決策，那么k一定可以作為合法決策，又因?yàn)閗比j要優(yōu)，(注意：在這個(gè)經(jīng)典模型中，“優(yōu)”是絕對(duì)的，是與當(dāng)前正在計(jì)算的狀態(tài)無(wú)關(guān)的)，所以說(shuō)，如果把待決策表中的決策按照k排序的話，則g(k)必然是不降的。這樣，就引導(dǎo)我們使用一個(gè)單調(diào)隊(duì)列來(lái)維護(hù)決策表。對(duì)于每一個(gè)狀態(tài)f(x)來(lái)說(shuō)，計(jì)算過(guò)程分為以下幾步：1、 隊(duì)首元素出隊(duì)，直到隊(duì)首元素在給定的范圍中。2、 此時(shí)，隊(duì)首元素就是狀態(tài)f(x)的最優(yōu)決策，3、 計(jì)算g(x)，并將其插入到單調(diào)隊(duì)列的尾部，同時(shí)維持隊(duì)列的單調(diào)性(不斷地出隊(duì)，直到隊(duì)列單調(diào)為止)。重復(fù)上述步驟直到所有的函數(shù)值均被計(jì)算出來(lái)。不難看出這樣的算法均攤時(shí)間復(fù)雜度是0(1)的。下面我們來(lái)看幾個(gè)例題。例題3：TheSoundofSilence題目來(lái)源：BalticOlympiadinInformatics2007題目大意：給出一個(gè)N項(xiàng)的數(shù)列，如果對(duì)于一個(gè)連續(xù)的長(zhǎng)度為M的片段來(lái)說(shuō)，片段內(nèi)所有數(shù)中最大值與最小值的差不超過(guò)一個(gè)給定的常數(shù)C,則我們稱這樣的片段是一個(gè)合法的片段。編程求出所有的合法片段的起始位置。

分析：本題不難看出可以分解為兩個(gè)子問(wèn)題：求所有片段的最大值以及求所有片段的最小值。而這兩個(gè)任務(wù)實(shí)際上是一樣的，所以我們只需要求取所有的連續(xù)M個(gè)數(shù)的片段中的最小值。這個(gè)任務(wù)有很多很多種對(duì)數(shù)級(jí)算法，其中用堆或者用靜態(tài)最優(yōu)二叉樹(shù)都可以做到O(nlogm)，但是這題的O(n)算法還是不那么好想的。事實(shí)上，如果用g[x]表示數(shù)列中第x個(gè)數(shù)的值，用f(x)表示以x作為結(jié)尾的有M個(gè)數(shù)的連續(xù)片段的話，顯然有：f(x)二mingi[，直接吻合經(jīng)典模型二。套用算法，就可以在O(n)的時(shí)間內(nèi)解決問(wèn)題。i=x-ml-(當(dāng)然，本題還有一種別致的“窗口”算法，也漂亮地在O(n)的時(shí)間內(nèi)解決了問(wèn)題，詳細(xì)可以看官方的解題報(bào)告。這里引入本題的主要目的是在于佐證上文中討論到的經(jīng)典模型二)例題4：Islands題目來(lái)源：IOI2008題目大意：給出一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向加權(quán)圖，同時(shí)這個(gè)圖中有且恰有N條邊?，F(xiàn)在，對(duì)于這個(gè)圖中的每一個(gè)連通分量，求出其最長(zhǎng)路徑(權(quán)值和最大，一個(gè)節(jié)點(diǎn)在路徑上最多只能出現(xiàn)一次)。分析：當(dāng)然，這個(gè)問(wèn)題更多的是一個(gè)圖論題。但是在最后關(guān)鍵問(wèn)題的處理上還是可以看到經(jīng)典模型二的影子。首先，用BFS找出所有連通分量。然后，對(duì)于一個(gè)連通分量來(lái)說(shuō)，由于點(diǎn)數(shù)與邊數(shù)相同,因此必然構(gòu)成基環(huán)+外向樹(shù)的結(jié)構(gòu)。我們可以找出基環(huán)并確定所有外向樹(shù)的結(jié)構(gòu)。一條最長(zhǎng)路徑有兩種可能：完整地位于某一棵外向樹(shù)中；或者位于兩棵外向樹(shù)中，其間通過(guò)基環(huán)的一段連接。第一種可能可以通過(guò)樹(shù)形DP解決，問(wèn)題就在于第二種可能怎樣處理。如果枚舉兩棵外向樹(shù)，那就是O(n2),就不可以接受了。我們考慮破環(huán)為鏈，然后將鏈整體左移，制作一個(gè)副本。比方說(shuō)，如果原來(lái)的環(huán)是：以1為首破環(huán)，得：以1為首破環(huán)，得：1--2--3--4，然后制作副本，得2--3--4--1--2--3--4，制作副本的主要目的是使得對(duì)于每一個(gè)點(diǎn)的方程都有統(tǒng)一的形式，使得環(huán)上所有片段都可以對(duì)應(yīng)鏈上的一個(gè)片段。這種情況下，用g[x]表示x點(diǎn)上外向樹(shù)上的最長(zhǎng)下降路的長(zhǎng)度，f(x)表示以該點(diǎn)為終點(diǎn)的總最長(zhǎng)路徑的長(zhǎng)度，則有：f(x)=max{g[i]+g[x]+dis[i,x]}，其中w函數(shù)即w[i,j=di[s丿顯然滿足i=x-n-1Vi<j<kw,i]+w,j= w通過(guò)變換之后就可以變成經(jīng)典模型二。這樣，就在總O(n)的時(shí)間內(nèi)解決了本題。如果還嫌以上兩個(gè)問(wèn)題不夠典型，下面舉一個(gè)典型到所有OIer都耳熟能詳?shù)念}目。例題5：有限背包問(wèn)題。題目來(lái)源：經(jīng)典問(wèn)題。題目大意：有N件物品，每一件物品的價(jià)值為p[k]，重量為w[k]，最多只能選取m[k]次；現(xiàn)在給出背包的最大承重量C,要求在滿足重量要求的條件下使得背包中的物品價(jià)值總和最大。分析：如果m[k]=1或者m[k]=+s,就都很好做。但現(xiàn)在m[k]是一個(gè)有界值，就比較麻煩了。我們還是按照背包問(wèn)題的常見(jiàn)思路，一次枚舉每一個(gè)物品。設(shè)當(dāng)前枚舉的物品編號(hào)為k,用f(x)表示：為了到達(dá)價(jià)值x,背包的重量至少應(yīng)該是多少；則我們有：f(x)二min[f(x-i*p[k])+i*w[k]}，這個(gè)方程很麻煩，因?yàn)槟骋粋€(gè)狀態(tài)的決策不是連續(xù)i=1的，而是間斷性的。怎樣把決策區(qū)間變成一段連續(xù)區(qū)間呢？很容易想到等價(jià)類的思想；如果按照模p[k]對(duì)所有的f(x)劃分等價(jià)類，那么在同一個(gè)等價(jià)類中，決策區(qū)間就是連續(xù)的了，我們不妨把新函數(shù)設(shè)為h(x)，則方程變?yōu)椋簒-1h(x)=min{h(i)+w[k]*(x-i)}，其中，w函數(shù)即w[i,j]=w'[k]*(-i顯然滿足i=x-m[k]Vi<j<k,w[i,j]+w[j,k]=w[i,k]，(注意w'k]是一個(gè)與i和j無(wú)關(guān)的常量)經(jīng)過(guò)適當(dāng)?shù)淖兓罂梢赞D(zhuǎn)化為經(jīng)典模型二。于是有限背包問(wèn)題可以在O(NP)的時(shí)間內(nèi)解決，其中P是背包可能取到的最大價(jià)值。(其實(shí)換成重量也一樣)，這也就是“背包十講”中所說(shuō)的那個(gè)單調(diào)隊(duì)列法。我們注意到，如果m[k]=1的話，那么每一個(gè)f(x)的決策量都是0(1),這沒(méi)什么問(wèn)題；但如果m[k]=+R,有意味著什么呢？仔細(xì)觀察可以發(fā)現(xiàn)，這實(shí)際上就拿掉了方程中的循環(huán)變x-1量的下界，對(duì)應(yīng)的是f(x)=min{g(k)}+w[1,x]這樣的一個(gè)方程，這顯然是很簡(jiǎn)單的，適k=1用單變量打擂臺(tái)就可以解決了(盡管我們通常并不這樣做)。所以說(shuō)，借助經(jīng)典模型二，我們?cè)谝粋€(gè)更高的高度上統(tǒng)一了0-1、有限、無(wú)限三大背包問(wèn)題。下面我們?cè)俅蝸?lái)看一下例題2《土地購(gòu)買》中的那個(gè)方程：f(n)=mil"(k)+x[n]*y[k+1]},我們來(lái)仔細(xì)地觀察這個(gè)方程：f(k)是變量，y[k+1]是常k=0量，但不論怎么說(shuō)，這兩個(gè)量在以后的計(jì)算中都不會(huì)變化。而x[n]是一個(gè)比例系數(shù)，它與k無(wú)關(guān)，只隨著x的變化而變化。如果我們建立平面直角坐標(biāo)系，以f(k)作為橫軸，y[k+1]作為縱軸，則每一個(gè)狀態(tài)f(k)都可以看作是該坐標(biāo)系中的一個(gè)點(diǎn)。在求解狀態(tài)f(n)的過(guò)程中，我要求最小化：minP=x+ky，其中x,y是我建立的直角坐標(biāo)系中某一個(gè)點(diǎn)的坐標(biāo)(表示一個(gè)決策)，k就是方程中的x[n]，是只與n有關(guān)，而與決策無(wú)關(guān)的一個(gè)常量。這個(gè)最小化問(wèn)題是什么呢？其實(shí)就是一個(gè)平面上的線性規(guī)劃。我們把式子改寫成：1 P 1y=-丁x+，就演變成了這樣的一個(gè)問(wèn)題：在一個(gè)直線簇y=-丁x+C中，選取一條直k k k線，使得這條直線過(guò)某個(gè)給出的數(shù)據(jù)點(diǎn)，同時(shí)c要最小。既然問(wèn)題變成了這么有意思的線性規(guī)劃問(wèn)題，就有必要進(jìn)一步的研究，看看是不時(shí)有更好的解法，這就導(dǎo)致了我們的另一個(gè)經(jīng)典模型：經(jīng)典模型三： f(x)=min{a[x]*f(i)+b[x]*g(i)}oi=1注意：這個(gè)模型寫的比較抽象，其實(shí)它的涵蓋范圍是很廣的。首先，a[x],b[x]不一定要是常量，只要他們與決策無(wú)關(guān)，都可以接受；另外，f(i)和g(i)不管是常量還是變量都沒(méi)有關(guān)系，只要他們是一個(gè)有最優(yōu)的f(x)決定的二元組就可以了。因此，為了方便描述，我們把這個(gè)模型寫成下面這個(gè)形式：f(n)=niin{a[n]*x(i)+b[n]*y(i)}i=1 ，其中，x(i)，y(i)都是可以在常數(shù)時(shí)間內(nèi)通過(guò)f(i)唯一決定的二元組。這個(gè)經(jīng)典模型怎樣轉(zhuǎn)化求解呢？前文說(shuō)過(guò)，這樣的模型的求解與平面上的線性規(guī)劃有關(guān)，我們以x(i)為橫軸，y(i)為縱軸建立平面直角坐標(biāo)系，這樣一個(gè)狀態(tài)f(i)所決定的二元組就可以用坐標(biāo)系中的一個(gè)點(diǎn)表示。然后，我們的目標(biāo)是：aPminP=ax-b，其中a=a[n],b=b[n]，化成：y二一丁x+〒，假設(shè)b>0(反之亦bb然)，則我們的任務(wù)是使得這條直線的縱截距最小。可以想象有一組斜率相同的直線自負(fù)無(wú)窮向上平移，所碰到的第一個(gè)數(shù)據(jù)點(diǎn)就是最優(yōu)決策。這個(gè)時(shí)候，有一個(gè)重要的性質(zhì)，那就是：所有最優(yōu)決策點(diǎn)都在平面點(diǎn)集的凸包上。基于這個(gè)事實(shí)，我們可以開(kāi)發(fā)出很多令人滿意的算法。這時(shí)，根據(jù)直線斜率與數(shù)據(jù)點(diǎn)分布的特征，可以劃分為兩種情況：情況一：決策直線的斜率與二元組的橫坐標(biāo)同時(shí)滿足單調(diào)性。(具體的單調(diào)性視最優(yōu)化目標(biāo)的性質(zhì)而定)這樣的模型是比較好處理的，因?yàn)檫@個(gè)時(shí)候由于斜率變化是單調(diào)的，所以決策點(diǎn)必然在凸殼上單調(diào)移動(dòng)。我們只需要維護(hù)一個(gè)單調(diào)隊(duì)列和一個(gè)決策指針，每次決策時(shí)作這樣幾件事：1、 決策指針(也就是隊(duì)首)后移，直至最佳決策點(diǎn)。2、 進(jìn)行決策。3、 將進(jìn)行決策之后的新?tīng)顟B(tài)的二元組加入隊(duì)尾，同時(shí)作Graham-Scan式的更新操作維護(hù)凸殼。(注意此時(shí)當(dāng)前指針?biāo)诙M有可能被拋棄)算法的時(shí)間復(fù)雜度為O(n)情況二：沒(méi)有任何限制。這時(shí)問(wèn)題的解決就比較困難了。顯然，決策點(diǎn)還是應(yīng)該在凸殼上。我們不妨考慮一個(gè)單調(diào)減的凸殼，這個(gè)凸殼上點(diǎn)與點(diǎn)之間的連線必然滿足這樣的性質(zhì)：斜率單調(diào)減。通過(guò)細(xì)致的觀察我們可以發(fā)現(xiàn)，對(duì)于一個(gè)給定的斜率k來(lái)說(shuō)，對(duì)應(yīng)的直線簇中具有最大縱截距的直線通過(guò)的決策點(diǎn)必然滿足這樣的性質(zhì)：該點(diǎn)兩側(cè)的邊的斜率k1,k2滿足k1>k>k2。這樣，我們就可以通過(guò)二分查找來(lái)確定最佳的決策點(diǎn)。但是，在插入數(shù)據(jù)點(diǎn)的過(guò)程中，我們遇到的麻煩可能更大。首先，肯定是二分查找確定橫坐標(biāo)的插入點(diǎn)，然后對(duì)兩側(cè)分別進(jìn)行Graham維護(hù)凸性。但接下來(lái)的問(wèn)題就嚴(yán)重了：在維護(hù)凸形的過(guò)程中我們肯定刪掉了一些點(diǎn)，怎樣重新得到一個(gè)完整的凸殼決策表呢？使用move是一個(gè)折中的辦法，但是這與理論的時(shí)間復(fù)雜度分析根本無(wú)益。完美的解決方法是應(yīng)用平衡二叉樹(shù)。我們以橫坐標(biāo)為關(guān)鍵字建立平衡二叉樹(shù)，這樣查找和插入的過(guò)程都可以在O(logn)時(shí)間內(nèi)完成。當(dāng)我們做Graham維護(hù)時(shí)，首先將新數(shù)據(jù)點(diǎn)Splay到根節(jié)點(diǎn)，此時(shí)剩下的節(jié)點(diǎn)必然分居左子樹(shù)和右子樹(shù)。然后，我們以左子樹(shù)為例，后序遍歷依次查找節(jié)點(diǎn)，直至查找到一個(gè)滿足凸形的節(jié)點(diǎn)。將這個(gè)節(jié)點(diǎn)Splay到根節(jié)點(diǎn)的左孩子，然后刪掉這個(gè)節(jié)點(diǎn)的右孩子。這樣的算法的時(shí)間復(fù)雜度是O(nlogn)，但是實(shí)現(xiàn)起來(lái)非常復(fù)雜。下面我們來(lái)看幾個(gè)例題。例題6：《玩具裝箱》的線性算法。例題1中《玩具裝箱》的動(dòng)態(tài)規(guī)劃方程為：f(x)=miif{i壬X-(-+51ck-L2],下面，我們?cè)噲D通過(guò)數(shù)學(xué)變換將其變成經(jīng)i=l k=i+i典模型三。為了簡(jiǎn)化計(jì)算，設(shè)sum[x]=工c[x]，貝y：i=1f(x)=rniin{f(i)+(x-i-1-L+sum[x]-sum[i])2}i=i=mx1inf{i(+)s(u(mx[+]-xL--1)s(um+i2[]，i))}i=1不妨設(shè)a[x]=sum[x]+x-1-1,b[i]=sum[i]+i，顯然這兩個(gè)量都是常量，貝y：f(x)=min{f(i)+(a[x]-b[i])2}i=1=mxi1n{f(i)+a2[x]+b2[i]-2a[x]b[i]}i=1 ，=mxi1n{f(i)+b2[i]-2a[x]b[i]}+a2[x]i=1然后問(wèn)題就明朗了，設(shè)平面直角坐標(biāo)系中x(i)=b[i],y(i)=f(i)+b2[i]，則問(wèn)題變成:minP=2ax+y，其對(duì)應(yīng)的線性規(guī)劃的目標(biāo)直線為y=-2ax+P。回顧定義不難看出，a[x]隨著x的增大而增大，x(i)也隨著i的增大而增大。因此，問(wèn)題中直線斜率單調(diào)減，數(shù)據(jù)點(diǎn)橫坐標(biāo)單調(diào)增，符合經(jīng)典模型三種的情形1。使用單調(diào)隊(duì)列維護(hù)凸殼可以在O(n)的時(shí)間內(nèi)解決本題。例題七：貨幣兌換。題目來(lái)源：NOI2007題目大意：有3種貨幣體系：人民幣，A券，B券，其中A券與B券的價(jià)格在每一天都是不同的。在某一天D,你可以做3件事情：1、 如果你的手頭上有A券或B券，你可以將它們都按照當(dāng)天的價(jià)格換成人民幣。2、 如果你的手頭上有人民幣,你可以將它們按照一個(gè)特定的比例Rate并以照當(dāng)天的價(jià)格換成A券和B券(就是說(shuō)你兌換的A券和B券的價(jià)值比是Rate)3、什么也不做。一開(kāi)始你有一些人民幣，請(qǐng)你通過(guò)最佳的操作方式在最后一天結(jié)束的時(shí)候手頭上握有最多的人民幣。分析：試題中的Hint已經(jīng)告訴我們，如果我們想買進(jìn)人民幣，就必須全額買進(jìn)；如果我們想賣出人民幣，就必須全額賣出。由于不管是在哪一天，人民幣總是越多越好；我們用f(n)表示到了第n天最多可能持有的人民幣數(shù)量，用x(i)和y(i)表示在第i天，用最多的錢能夠換成的A券和B券。(注意：由于Rate確定，兌換金額確定，所以A券和B券的數(shù)量是唯一確定的)，我們有：f(n)=nia1x{a[n]*x(i)+b[n]*y(i)}，其中a[n]和b[n]代表A券和B券在第n天的牌價(jià)。這個(gè)方程式符合經(jīng)典模型三中的情形二。所以，我們應(yīng)該使用一個(gè)平衡樹(shù)來(lái)維護(hù)凸形。時(shí)間復(fù)雜度是O(nlogn)。由于數(shù)據(jù)弱，所以這道題目用move也是可以搞定的。這篇文章中，我們著重討論了這樣三類經(jīng)典模型的建立與求解過(guò)程：經(jīng)典模型一：f(x)二rminff(i)+w[i,x]}，w[i,x]滿足決策單調(diào)性。i=1經(jīng)典模型二：f(x)=mih{g(i)}+w[x]，其中b[x]單調(diào)增。i=b[x]經(jīng)典模型三：f(n)=niin{a[n]*x(i)+b[n]*y(i)}，其中x(i),y(i)可以由f(i)在常數(shù)i=1時(shí)間內(nèi)唯一確定。這三類模型都可以在至少O(nlogn)的時(shí)間內(nèi)解決，從而起到了對(duì)1D/1D的方程的優(yōu)化作用。另外，這三種模型并不是孤立存在的，而是可以互相轉(zhuǎn)化的，文中的很多例題就兼具多種模型的特點(diǎn)。當(dāng)然，本文只是對(duì)1D/1D動(dòng)態(tài)規(guī)劃優(yōu)化的很初步很淺顯的探討，