狀態(tài)壓縮動(dòng)態(tài)規(guī)劃淺談

《狀態(tài)壓縮動(dòng)態(tài)規(guī)劃淺談》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、狀態(tài)壓縮動(dòng)態(tài)規(guī)劃淺談——鄭暾peter112358@163.com基礎(chǔ)知識(shí)動(dòng)態(tài)規(guī)劃(dynamicprogramming)運(yùn)籌學(xué)的一個(gè)分支，是求解決策過(guò)程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。動(dòng)態(tài)規(guī)劃是對(duì)解最優(yōu)化問(wèn)題的一種途徑、一種方法，而不是一種特殊算法。其往往是針對(duì)一種最優(yōu)化問(wèn)題。由于各種問(wèn)題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對(duì)不同的問(wèn)題，有各具特色的解題方法，而不存在一種萬(wàn)能的動(dòng)態(tài)規(guī)劃算法，可以解決各類(lèi)最優(yōu)化問(wèn)題?；A(chǔ)知識(shí)一些常見(jiàn)術(shù)語(yǔ)：階段，狀態(tài)，決策和遞推的區(qū)別：決策！基本知識(shí)一些必要性質(zhì)：無(wú)后效

2、性：對(duì)于狀態(tài)，如果給定某一階段的狀態(tài)，則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過(guò)程也就確定了。最優(yōu)子結(jié)構(gòu)性質(zhì)：要求問(wèn)題的最優(yōu)策略的子策略也是最優(yōu)?；局R(shí)狀態(tài)壓縮動(dòng)態(tài)規(guī)劃的使用動(dòng)機(jī)：一般的狀態(tài)描述不滿(mǎn)足無(wú)后效性原則，或者保存的信息不足夠進(jìn)行決策。將當(dāng)前一部分局面信息壓縮存儲(chǔ)，結(jié)合常見(jiàn)的一些局面描述，使得構(gòu)成的狀態(tài)滿(mǎn)足無(wú)后效性原則基礎(chǔ)知識(shí)名稱(chēng)：基于狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃、集合動(dòng)態(tài)規(guī)劃。含義：以一個(gè)集合內(nèi)的元素信息作為狀態(tài)，狀態(tài)總數(shù)為指數(shù)級(jí)別的動(dòng)態(tài)規(guī)劃。特點(diǎn)：1、本身要滿(mǎn)足動(dòng)態(tài)規(guī)劃的性質(zhì)：最優(yōu)性原理、無(wú)后效性。2

3、、數(shù)據(jù)某幾維規(guī)模比較小。傳統(tǒng)集合動(dòng)態(tài)規(guī)劃例題一：給定n個(gè)點(diǎn)的有向帶權(quán)圖，求一條經(jīng)過(guò)每個(gè)點(diǎn)一次的回路，并要求權(quán)和最小。范圍n<=15。傳統(tǒng)集合動(dòng)態(tài)規(guī)劃顯然對(duì)于某一個(gè)中間狀態(tài)，影響它的最后結(jié)果的僅僅是當(dāng)前所在點(diǎn)以及之前已經(jīng)經(jīng)過(guò)的點(diǎn)。而之前的路徑行走情況與之后的解無(wú)關(guān)。狀態(tài)F[i,opt]，i表示當(dāng)前所在點(diǎn)，opt是用2進(jìn)制記錄每個(gè)點(diǎn)是否已經(jīng)經(jīng)過(guò)。傳統(tǒng)集合動(dòng)態(tài)規(guī)劃例題二：炮兵陣地（NOI2001）在N*M網(wǎng)格地圖上部署炮兵部隊(duì)。每個(gè)炮兵可以控制橫縱2格范圍。任意一對(duì)炮兵互相不能處于控制范圍。地圖上有些點(diǎn)不能部署部隊(duì)。N<=100；M<=10。傳統(tǒng)集合動(dòng)

4、態(tài)規(guī)劃例題三：K-排列問(wèn)題考慮一個(gè)1~n的排列a[1],a[2],a[3]…a[n]，若max(abs(a[i]-i))=K，那么這個(gè)排列就稱(chēng)為K-排列。求n個(gè)數(shù)的K-排列的個(gè)數(shù)。范圍：n<=100,K<=5傳統(tǒng)集合動(dòng)態(tài)規(guī)劃例題四：生成樹(shù)計(jì)數(shù)（NOI2007）環(huán)狀圖，任意兩個(gè)點(diǎn)距離不超過(guò)k則連邊，求生成樹(shù)個(gè)數(shù)。K<=5實(shí)現(xiàn)插頭法轉(zhuǎn)移的復(fù)雜度降低時(shí)間復(fù)雜度降低傳統(tǒng)集合動(dòng)態(tài)規(guī)劃例題AnotherChocolateManiac(Sgu132)給定一個(gè)M*N的網(wǎng)格，網(wǎng)格中存在一些障礙物。在網(wǎng)格空地處放置最少的1*2的矩形塊，使得網(wǎng)格中無(wú)法再放入1*2的矩

5、形塊。1<=M<=701<=N<=7基于連通性的狀態(tài)壓縮動(dòng)態(tài)規(guī)劃在網(wǎng)格中尋找一條或多條路徑（回路）滿(mǎn)足一定的條件，求方案數(shù)或路徑總長(zhǎng)度最短。狀態(tài)除了記錄路徑“出口”，還要記錄其連通性?；谶B通性的狀態(tài)壓縮動(dòng)態(tài)規(guī)劃例題一：Formula1（Ural1519）給你一個(gè)m*n的棋盤(pán)，有的格子是障礙，問(wèn)共有多少條回路使得經(jīng)過(guò)每個(gè)非障礙格子恰好一次．m,n≤12．基于連通性的狀態(tài)壓縮動(dòng)態(tài)規(guī)劃思想：狀態(tài)壓縮動(dòng)態(tài)規(guī)劃。一個(gè)單元格中可能出現(xiàn)的路徑情況：實(shí)現(xiàn)細(xì)節(jié)總體實(shí)現(xiàn)：插頭法實(shí)現(xiàn)方法：記憶化搜索F[i,j,opt]表示當(dāng)前是i行j列，最后掃描的總共m個(gè)格子的狀態(tài)

6、為opt的方案數(shù)。Opt的記錄：m個(gè)格子向下伸出插頭的情況，以及最后一個(gè)格子向右伸出插頭的情況。插頭記錄：0表示無(wú)插頭，具體數(shù)字表示插頭的屬性（染色法記錄屬于第幾個(gè)連通塊，最小表示）。對(duì)于本題最多同時(shí)存在6個(gè)連通塊的插頭。實(shí)現(xiàn)細(xì)節(jié)轉(zhuǎn)移：分類(lèi)討論插頭方向。1、當(dāng)前格上方左方均有插頭：只能將這兩個(gè)連通塊連接。（1種）2、當(dāng)前格只有上方有插頭：將這個(gè)插頭向下向右延伸。（2種）3、當(dāng)前格只有左方有插頭：將這個(gè)插頭向下向右延伸。（2種）4、當(dāng)前格周?chē)鸁o(wú)插頭：若當(dāng)前格為障礙物，則無(wú)插頭，否則插入一個(gè)折線(xiàn)形插頭。實(shí)現(xiàn)細(xì)節(jié)合并連通塊：對(duì)于第一種情況，需要合并連通

7、塊。若不加限制，則會(huì)計(jì)算出包含多條回路的情況。限制：和并連通塊時(shí)，若兩個(gè)插頭屬于同一個(gè)連通塊，則當(dāng)且僅當(dāng)在最后一個(gè)有效格子中可以將這兩個(gè)插頭連接。最后統(tǒng)計(jì)：計(jì)算到最后一個(gè)有效格子時(shí)，需要統(tǒng)計(jì)答案。此時(shí)，要保證當(dāng)前狀態(tài)沒(méi)有剩余的插頭。實(shí)現(xiàn)細(xì)節(jié)一些可能存在的問(wèn)題：直接開(kāi)數(shù)組用序列記錄插頭好還是把狀態(tài)壓縮后記錄好？最小表示的如何實(shí)現(xiàn)？如何減小常數(shù)？實(shí)現(xiàn)細(xì)節(jié)一個(gè)優(yōu)化：若當(dāng)前格子連出的插頭指向一個(gè)障礙物格子，可以直接剪枝。對(duì)有障礙的情況，能減少很多無(wú)效狀態(tài)?；谶B通性的狀態(tài)壓縮動(dòng)態(tài)規(guī)劃例題二：ManhattanWriting（Japan2006）n*m網(wǎng)格

8、有一些障礙，要求把兩個(gè)2和兩個(gè)3分別用折線(xiàn)連起來(lái)，總長(zhǎng)度盡量小。n,m<=9基于連通性的狀態(tài)壓縮動(dòng)態(tài)規(guī)劃主體思想與之前相同。不同點(diǎn)：需要