動(dòng)態(tài)規(guī)劃的技巧

動(dòng)態(tài)規(guī)劃的技巧一一階段的劃分和狀態(tài)的表示動(dòng)態(tài)規(guī)劃的技巧階段的劃分和狀態(tài)的表示在動(dòng)態(tài)規(guī)劃的設(shè)計(jì)過程中，階段的劃分和狀態(tài)的表示是非常重要的兩步，這兩步會(huì)直接影響該問題的計(jì)算復(fù)雜性，有時(shí)候階段劃分或狀態(tài)表示的不合理還會(huì)使得動(dòng)態(tài)規(guī)劃法不適用。［例9］街道問題在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。這是一道簡(jiǎn)單而又典型的動(dòng)態(tài)規(guī)劃題，許多介紹動(dòng)態(tài)規(guī)劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的:按照?qǐng)D中的虛線來劃分階段，即階段變量k表示走過的步數(shù)，而狀態(tài)變量xk表示當(dāng)前處于這一階段上的哪一點(diǎn)。這時(shí)的模型實(shí)際上已經(jīng)轉(zhuǎn)化成了一個(gè)特殊的多段圖。用決策變量uk=0表示向右走，uk=1表示向上走，則狀態(tài)轉(zhuǎn)移方程如下:（這里的row是地圖豎直方向的行數(shù)）我們看到，這個(gè)狀態(tài)轉(zhuǎn)移方程需要根據(jù)k的取值分兩種情況討論，顯得非常麻煩。相應(yīng)的，把它代入規(guī)劃方程而付諸實(shí)現(xiàn)時(shí)，算法也很繁。因而我們?cè)趯?shí)現(xiàn)時(shí)，一般是不會(huì)這么做的，而代之以下面方法:，頊n私+皿璀（這里Distance表示相鄰兩點(diǎn)間的邊長(zhǎng)）這樣做確實(shí)要比上面的方法簡(jiǎn)單多了，但是它已經(jīng)破壞了動(dòng)態(tài)規(guī)劃的本來面目，而不存在明確的階段特征了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分階段的話，那么它的"狀態(tài)轉(zhuǎn)移"就不全是在兩個(gè)階段之間進(jìn)行的了。也許這沒什么大不了的，因?yàn)閷?shí)踐比理論更有說服力。但是，如果我們把題目擴(kuò)展一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，并且要求兩條路徑的總長(zhǎng)度最短。這時(shí)，再用這種”簡(jiǎn)單"的方法就不太好辦了。如果非得套用這種方法的話，則最優(yōu)指標(biāo)函數(shù)就需要有四維的下標(biāo)，并且難以處理兩條路徑"不能重疊"的問題。而我們回到原先"標(biāo)準(zhǔn)"的動(dòng)態(tài)規(guī)劃法，就會(huì)發(fā)現(xiàn)這個(gè)問題很好解決，只需要加一維狀態(tài)變量就成了。即用xk=（ak,bk）分別表示兩條路徑走到階段k時(shí)所處的位置，相應(yīng)的，決策變量也增加一維，用uk=（xk,yk）分別表示兩條路徑的行走方向。狀態(tài)轉(zhuǎn)移時(shí)將兩條路徑分別考慮丸+i二如+1—必次I二%+孔，如十1二席+%*＞廠口并在寫規(guī)劃方程時(shí)，只要對(duì)兩條路徑走到同一個(gè)點(diǎn)的情況稍微處理一下，減少可選的決策個(gè)數(shù)：危"房*心叫））+兩條邊長(zhǎng)）叫fmin（兄+i（L+兩條誼長(zhǎng)）點(diǎn)上尹如/（岫膽W叫5從這個(gè)例子可以看出，合理地劃分階段和選擇狀態(tài)可以給解題帶來方便。[例10]LITTLESHOPOFFLOWERS（IOI’99PROBLEMYouwanttoarrangethewindowofyourflowershopinamostpleasantway.YouhaveFbunchesofflowers,eachbeingofadifferentkind,andatleastasmanyvasesorderedinarow.Thevasesaregluedontotheshelfandarenumberedconsecutively1thiftougHiereVisthenumberofvases,fromlefttorightsothatthevase1istheleftmost,an(thevas^istherightmostvase.ThebunchesaremoveableandareuniquelyidentifiedbyintegersbetweenFlandseid-numbershaveasignificance:Theydeterminetherequiredorderofappearanceoftheflowerbunchesintherowofvasessothatthiniisincieinavasetotheleftofthevasecontainingjwhenhveri<jSuppose,forexample,youhaveabunchofazaleas(id-number=1),abunchofbegonias(id-number=2)andabunchofcarnations(id-number=3).Now,allthebunchesmustbeputintothevaseskeepingtheirid-numbersinorder.Thebunchofazaleasmustbeinavasetotheleftofbegonias,andthebunchofbegoniasmustbeinavasetotheleftofcarnations.Iftherearemorevasesthanbunchesofflowersthentheexcesswillbeleftempty.Avasecanholdonlyonebunchofflowers.Eachvasehasadistinctcharacteristic(justlikeflowersdo).Hence,puttingabunchofflowersinavaseresultsinacertainaestheticvalue,expressedbyaninteger.Theaestheticvaluesarepresentedinatableasshownbelow.Leavingavaseemptyhasanaestheticvalueof0.VASES12345Bunches1(azaleas)723-5-24162(begonias)521-410233(carnations)-215-4-2020Accordingtothetable,azaleas,forexample,wouldlookgreatinvase2,buttheywouldlookawfulinvase4.Toachievethemostpleasanteffectyouhavetomaximizethesumofaestheticvaluesforthearrangementwhilekeepingtherequiredorderingoftheflowers.Ifmorethanonearrangementhasthemaximalsumvalue,anyoneofthemwillbeacceptable.Youhavetoproduceexactlyonearrangement.ASSUMPTIONS.1<=F<=100whereFisthenumberofthebunchesofflowers.Thebunchesarenumbered1throughF..F<=V<=100whereVisthenumberofvases..-50<=A..<=50whereA.,istheaestheticvalueobtainedbyputtingtheflowerbunchiintothevasej.INPUTTheinputisatextfilenamedflower.inp.?Thefirstlinecontainstwonumbers:F,V..ThefollowingFlines:EachoftheselinescontainsVintegers,sothatA.,isgivenasthejthnumberonthe(i+1)stlineoftheinputfile.yOUTPUTTheoutputmustbeatextfilenamedflower.outconsistingoftwolines:.Thefirstlinewillcontainthesumofaestheticvaluesforyourarrangement..ThesecondlinemustpresentthearrangementasalistofFnumbers,sothatthek’thnumberonthislineidentifiesthevaseinwhichthebunchkisput.EXAMPLEflower.inp:35723-5-2416521-41023-215-4-2020flower.out:EVALUATION.Yourprogramwillbeallowedtorun2seconds..Nopartialcreditcanbeobtainedforatestcase.

本題雖然是IOI’9中較為簡(jiǎn)單的一題，但其中大有文章可作。說它簡(jiǎn)單，是因?yàn)樗行颍虼宋覀円谎郾憧煽闯鲞@題應(yīng)該用動(dòng)態(tài)規(guī)劃來解決。但是，如何動(dòng)態(tài)規(guī)劃呢？如何劃分階段，又如何選擇狀態(tài)呢？<方法1>以花束的編號(hào)來劃分階段。在這里，第k階段布置第k束花，共有F束花，有F+1個(gè)階段，增加第F+1階段是為了計(jì)算的方便；狀態(tài)變量xk表示第k束花所在的花瓶。而對(duì)于每一個(gè)狀態(tài)xk，決策uk就是第k+1束花放置的花瓶號(hào)；最優(yōu)指標(biāo)函數(shù)fk(xk)表示從第k束花到第n束花所得到的最大美學(xué)值；A(iJ)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F是花的總數(shù)。狀態(tài)轉(zhuǎn)移方程為況十1=歐規(guī)劃方程為max3(乩片)+兀+10fc+l))邊界條件為:事實(shí)上這是一個(gè)虛擬的邊界。最后要求的最大美學(xué)價(jià)值是

max<方法2>方法1的規(guī)劃方程中的允許決策空間：xk+1<uk<V-(F-k)+1比較麻煩，因此有待改進(jìn)。還是以花束的編號(hào)來劃分階段，第k階段布置第k束花;狀態(tài)變量xk表示第k束花所在的花瓶；注意，這里我們考慮倒過來布置花瓶，即從第F束花開始布置到第1束花。于是狀態(tài)變量uk表示第k-1束花所在的花瓶；最優(yōu)指標(biāo)fk(xk)表示從第一束花到第k束花所獲得的美學(xué)價(jià)值；A(ij)是花束i插在花瓶j中的美學(xué)值,▼是花瓶總數(shù),F是花的總數(shù)。則狀態(tài)轉(zhuǎn)移方程為：西卜1=蜘規(guī)劃方程為：兀(&)二max0(在叫)+兀項(xiàng)％]))增加的虛擬邊界條件為：席偵口)=0最后要求的最大美學(xué)價(jià)值是:max可以看出，這種方法實(shí)質(zhì)上和方法1沒有區(qū)別，但是允許決策空間的表示變得簡(jiǎn)單了。max<方法3>以花瓶的數(shù)目來劃分階段，第k個(gè)階段決定花瓶k中是否放花；狀態(tài)變量xk表示前k個(gè)花瓶中放了多少花；而對(duì)于任意一個(gè)狀態(tài)xk，決策就是第xk束花是否放在第k個(gè)花瓶中，用變量uk=1或0來表示。最優(yōu)指標(biāo)函數(shù)fk(xk)表示前k個(gè)花瓶中插了xk束花，所能取得的最大美學(xué)值。注意，這里仍然是倒過來考慮。狀態(tài)轉(zhuǎn)移方程為4-1~xk~uk規(guī)劃方程為后(％)二巴對(duì)以項(xiàng)去如十蛉用謚成))邊界條件為時(shí))=0三種不同的方法都成功地解決了問題，只不過因?yàn)殡A段的劃分不同，狀態(tài)的表示不