動態(tài)規(guī)劃優(yōu)化

1、動態(tài)規(guī)劃優(yōu)化第1頁，共48頁，2022年，5月20日，15點17分，星期一簡介動態(tài)規(guī)劃優(yōu)化的主要方法：1、降維（優(yōu)化狀態(tài)）2、優(yōu)化轉(zhuǎn)移3、常數(shù)優(yōu)化第2頁，共48頁，2022年，5月20日，15點17分，星期一1.降維降維是一個通用的說法，其實質(zhì)就是通過改變動態(tài)規(guī)劃的狀態(tài)含義，或者拋棄一些冗余狀態(tài)環(huán)節(jié)，達到減少狀態(tài)，加速動態(tài)規(guī)劃的目的第3頁，共48頁，2022年，5月20日，15點17分，星期一1.1轉(zhuǎn)變思路很多時候，當?shù)贸瞿撤N動態(tài)規(guī)劃模型的時候，不要著急動手，而是需要仔細思考一下，是不是有更好的狀態(tài)表示方法多積累經(jīng)驗，同時又不能拘泥于死板的模型理論，要有創(chuàng)新意識。第4頁，共48頁，2022年，

2、5月20日，15點17分，星期一1.1.1例題給定N*M的空白棋盤，在其中放任意放車（可以不放），要使得放在棋盤上的車兩兩不能攻擊，求方案總數(shù)MOD P的值。第5頁，共48頁，2022年，5月20日，15點17分，星期一1.1.1.1思路一按照基本的狀態(tài)壓縮動態(tài)規(guī)劃模型進行解答。optKS表示已經(jīng)放了前K行，并且每一列是否有車的狀態(tài)為S（S為一個0/1的2進制序列，那一位為1則表示對應一列已經(jīng)放過了一個車）的合法方案的數(shù)量。比如opt2(101)2即表示前2行放了車且第1，3列有車的狀態(tài)。第6頁，共48頁，2022年，5月20日，15點17分，星期一1.1.1.1思路一則轉(zhuǎn)移就是枚舉這一行放還

3、是不放，如果放的話則枚舉所有沒有放車的行，將對應的2進制位標記為1，進行轉(zhuǎn)移。時間復雜度O(NM2M)空間復雜度O(2M)但是如果N,M1000該怎么辦呢？第7頁，共48頁，2022年，5月20日，15點17分，星期一1.1.1.2思路二換一個角度來分析問題可以發(fā)現(xiàn)，我們需要知道的只是有多少列目前沒有放車，并不需要知道具體是哪些列沒有放車！因此optk(101)2和optk(110)2是本質(zhì)等價的。于是我們可以把狀態(tài)改為：optkS表示放置了前k行，并且有S列沒有放置。第8頁，共48頁，2022年，5月20日，15點17分，星期一1.1.1.2思路二此時轉(zhuǎn)移稍有不同optk+1S=optkS+

4、optkS+1*(S+1)此時時間復雜度為O(NM)空間復雜度為O(NM)問題得到了解決可見對問題透徹的分析是得出最有效規(guī)劃方式的前提。第9頁，共48頁，2022年，5月20日，15點17分，星期一1.2拋棄冗余很多時候一些狀態(tài)是不需要的，或者某些維是可以合并的。經(jīng)過合理的分析我們可以拋棄一些冗余信息，減少狀態(tài)，加速轉(zhuǎn)移。第10頁，共48頁，2022年，5月20日，15點17分，星期一1.2.1例題poet(NOI2009 day1 p2)有N個詩句，要每個詩句有一個長度Li，要將其排版，一行可以放若干詩句并且每句詩中間用一個空格隔開，有一標準長Len，每一行的難看度是當前行長度C與Len之差

5、絕對值的P次方。求一種最好看的排版方式使得總難看度最小。N10000 L200 1P10第11頁，共48頁，2022年，5月20日，15點17分，星期一1.2.1.1思路一由于標準行長L很小我們不難想到一個如下的動態(tài)規(guī)劃方法：optKS表示排版了前K個句子，并且當前行長是S。對于每個狀態(tài)轉(zhuǎn)移就是枚舉是將這個詩句放在行末還是換行。有一個問題是：如果一個詩句過長怎么辦？那我們也將數(shù)組下標開的很大么？第12頁，共48頁，2022年，5月20日，15點17分，星期一1.2.1.2思路二仔細分析，不難發(fā)現(xiàn)，第二維狀態(tài)是沒有用的。我們需要知道只是每一行最后一個詩句是那個就可以了，并不用關(guān)心每行具體多長。我

6、們拋棄第二維：optK表示安排了前K個詩句并且第K個詩句在行末所能獲得的最小難看度。第13頁，共48頁，2022年，5月20日，15點17分，星期一1.2.1.2思路二那么轉(zhuǎn)移就是optK=min(opti+cost(i+1,K)|iK)cost(i+1,K)表示第i+1到第K個詩句放一行的難看度。那如何利用LL且Sum(j,K)L則所有i之前的決策都是無用的。第14頁，共48頁，2022年，5月20日，15點17分，星期一1.2.1.2思路二時間復雜度O(NL)空間復雜度O(N)不難發(fā)現(xiàn)我們是利用L200這個條件在動態(tài)規(guī)劃中進行了一個剪枝從而將一個空間復雜度無法估計的動態(tài)規(guī)劃成功降低到了O(

7、N)，并成功將復雜度降低。剔除動態(tài)規(guī)劃中的冗余信息是優(yōu)化動態(tài)規(guī)劃的重要方面。第15頁，共48頁，2022年，5月20日，15點17分，星期一2.優(yōu)化轉(zhuǎn)移1、優(yōu)化轉(zhuǎn)移方式2、預處理3、費用提前計算4、參數(shù)分離5、單調(diào)性第16頁，共48頁，2022年，5月20日，15點17分，星期一2.1優(yōu)化轉(zhuǎn)移方式基本的轉(zhuǎn)移方式共有兩種1、通過狀態(tài)選擇決策2、通過決策來更新狀態(tài)第17頁，共48頁，2022年，5月20日，15點17分，星期一2.1.1狀態(tài)選擇決策對于每個狀態(tài)會有一些決策來選擇，我們從中選擇一個最優(yōu)的決策，來實現(xiàn)規(guī)劃的過程，并完成了當前這一狀態(tài)的計算。可以認為這是一個正向過程。一個簡單的例子opt

8、k=min(opti+1|AiAk)這是一個不下降子序列的動態(tài)規(guī)劃方程不難得到這個方法O(NlogN)轉(zhuǎn)移方式第18頁，共48頁，2022年，5月20日，15點17分，星期一2.1.2決策更新狀態(tài)當一個狀態(tài)計算完畢，那么這個狀態(tài)就自然的成為了后面狀態(tài)選擇的一個決策，于是我們可以在剛產(chǎn)生這個決策的時候更新所有可能用到這個決策的狀態(tài)?？梢哉f這是一個逆向行為的過程。大多數(shù)時候正向方式和逆向方式是差不多的，或者正向方式優(yōu)于逆向方式，當然也有例外，因此需要我們自己根據(jù)實際情況靈活選擇。第19頁，共48頁，2022年，5月20日，15點17分，星期一2.1.2.1例題給N*M的存在一些障礙的棋盤，在其中放

9、置1*2的多米諾骨牌，問合法的放置總數(shù)MOD P是多少。第20頁，共48頁，2022年，5月20日，15點17分，星期一2.1.2.1.1說在前面我們這里先介紹一種對于狀態(tài)壓縮動態(tài)規(guī)劃轉(zhuǎn)移和狀態(tài)表示的一般方法按格（點）轉(zhuǎn)移。optxyS表示當前決策格為(x,y)同時2進制狀態(tài)S表示當前掃描線上每個格子是否被覆蓋的狀況。第21頁，共48頁，2022年，5月20日，15點17分，星期一2.1.2.1.1說在前面OPTxy(000000)2OPTxy+1(011000)2第22頁，共48頁，2022年，5月20日，15點17分，星期一2.1.2.1.2分析不難發(fā)現(xiàn)我們之前選擇了一種逆向轉(zhuǎn)移的方式即從

10、當前狀態(tài)枚舉下一步行為，并向后更新這樣的好處在于（1）方便情況的討論，簡化轉(zhuǎn)移（2）避免了很多不可能出現(xiàn)的狀態(tài)（3）加速了決策時間復雜度 O(N2M)其實，還有一些情況是只有這種更新方式才能優(yōu)化的，限于篇幅和難度問題這里就不多說了第23頁，共48頁，2022年，5月20日，15點17分，星期一2.2 預處理預處理就是將動態(tài)規(guī)劃中常用的一些計算環(huán)節(jié)預先處理好，方便動態(tài)規(guī)劃中重復用到，很多時候利用這種并行計算的問題是可以大大降低算法復雜度的。第24頁，共48頁，2022年，5月20日，15點17分，星期一2.2.1例題Grid(BOI2008)有分成N*M格的土地，每個土地有一個工作時間，現(xiàn)在可以

11、將這些土地分成(r+1)*(s+1)塊，每塊由一個工作人員來完成工作，問最快能多長時間完成全部格子上的工作？rN18 sM18第25頁，共48頁，2022年，5月20日，15點17分，星期一2.2.1.1分析簡單的想法是首先枚舉橫向如何對土地進行分割，然后再對縱向進行動態(tài)規(guī)劃。枚舉部分我們不多說，這里共需要C(N,r)的時間，我們用數(shù)組lis記錄分割情況關(guān)于動態(tài)規(guī)劃，不難得到如下方程：optik表示第i個豎線為第k個分割線。轉(zhuǎn)移比較簡單optik=minmax(optjk-1,f(j,i)第26頁，共48頁，2022年，5月20日，15點17分，星期一2.2.1.1分析代價f我們可以邊轉(zhuǎn)移邊計

12、算。我們從i開始從后往前枚舉j，那么我們顯然每次只需要O(N)的代價就可以計算出當前的f。動態(tài)規(guī)劃的時間復雜度為O(rsM2)算法的總體復雜度為O(C(N,r)rsM2)第27頁，共48頁，2022年，5月20日，15點17分，星期一2.2.1.2優(yōu)化1.預處理出sumxy數(shù)組，記錄矩形(1,1)-(x,y)中每個格子的工作量之和。則對于任意矩形，我們都可以在O(1)時間內(nèi)計算出部分和。2.搜索完行的拆分之后，我們預處理出所有f數(shù)組。計算f數(shù)組的時間復雜度為O(M2r)此時動態(tài)規(guī)劃復雜度為O(M2s)總復雜度降為O(C(N,r)M2(r+s)第28頁，共48頁，2022年，5月20日，15點1

13、7分，星期一2.3 費用提前計算在動態(tài)規(guī)劃問題中很多時候計算轉(zhuǎn)移代價成了我們一個很棘手的問題，有些時候我們可能要花費很多的力氣來計算某一些特定狀態(tài)下的費用（比如邊界狀態(tài)等等）其實很多時候我們可以用一些方法，把費用計算花去的時間平攤到其他的地方，從而優(yōu)化動態(tài)規(guī)劃第29頁，共48頁，2022年，5月20日，15點17分，星期一2.3.1例題Sue的小球(sdtsc 2008) 天空中有N個坐標為(xi,yi)的小球，并會以vi速度勻速下降，這個小球的價值就是其y坐標的1000分之一你有一個在x坐標軸上滑行的飛行器，可以以單位速度在x軸上平移，只要和小球到同一x坐標就能收獲那個小球。假設(shè)你一開始在(

14、0,0)，并且希望收獲所有小球，問可能的最大收益是？N1000第30頁，共48頁，2022年，5月20日，15點17分，星期一2.3.1.1分析由于所有小球的x坐標是不變的，因此我們按照x坐標將小球排序。觀察一個性質(zhì)：我們獲得球必然是一個連續(xù)區(qū)間。因此不難得出動態(tài)規(guī)劃表示方法：optLR0/1表示獲得球的區(qū)間是L,R，同時此時飛行器在左邊/右邊球所對應的x坐標。第31頁，共48頁，2022年，5月20日，15點17分，星期一2.3.1.1分析但是，如何計算代價呢？考慮到一個很好的性質(zhì)：飛行器的移動速度是單位速度。一種簡單的方式是增加一維時間：optLRT0/1表示時刻T此時的狀態(tài)?？梢允褂藐犃?/p>

15、保存可行狀態(tài)，再使用更新狀態(tài)的方法進行轉(zhuǎn)移。第32頁，共48頁，2022年，5月20日，15點17分，星期一2.3.1.2優(yōu)化現(xiàn)在問題的關(guān)鍵在于如何快速的計算費用。我們現(xiàn)在糾結(jié)的問題在于，我們并不知道之前我們是如何行走的，所以如果沒有T，我們并不知道當前我們面對的球到底是多少價值。第33頁，共48頁，2022年，5月20日，15點17分，星期一2.3.1.2優(yōu)化我們不妨換個思路，為什么要去糾結(jié)于之前的狀態(tài)呢？當我們做了一個決策之后，對后面的影響我們是知道的，為什么不能把握這一我們清楚的信息呢？道理很清楚：第34頁，共48頁，2022年，5月20日，15點17分，星期一2.3.1.2優(yōu)化每次決策

16、后，我們將這一次移動對所有我們還沒有得到的小球產(chǎn)生的費用損失都在決策時計算。我們可以看作小球都沒有動，只是在我們每次決策是損失了一些價值。假設(shè)當前移動花費了時間T，我們還沒有得到的小球的速度和是SV，那么損失的代價就是T*SV/1000第35頁，共48頁，2022年，5月20日，15點17分，星期一2.3.1.3問題的解決我們用SI記錄前I個小球的速度和那么我們的轉(zhuǎn)移方程就是：optLR0/1-(SN-SR+SL-1)*T/1000+valueoptLR0/1時空復雜度 O(N2)第36頁，共48頁，2022年，5月20日，15點17分，星期一2.4參數(shù)分離這是一個信息學競賽中非常重要的手段，

17、當然難度也比較大，這里限于篇幅和難度，只是簡單說一下。參數(shù)分離就是通過數(shù)學變形將和決策有關(guān)的變量和狀態(tài)有關(guān)的變量分開，從而發(fā)現(xiàn)一些性質(zhì)來優(yōu)化動態(tài)規(guī)劃。第37頁，共48頁，2022年，5月20日，15點17分，星期一2.4.1例題Triangles (POI07-08 StageIII)給定平面上N1000個點，則顯然會構(gòu)成N(N-1)(N-2)/3個三角形求所有這些三角形的面積和第38頁，共48頁，2022年，5月20日，15點17分，星期一2.4.1.1預備知識首先必須要知道叉積向量a=(x1,y1)，b=(x2,y2)則有：a b = x1 * y2 x2 * y1=|a|b|sin為有向

18、角度因此只要保證方向為正，那么向量a和b組成的三角形面積即為(a b)/2第39頁，共48頁，2022年，5月20日，15點17分，星期一2.4.1.2分析首先我們花O(N)的時間枚舉左下角c所有需要計算的點都以點c為原點建系假設(shè)坐標為xi和yi按極角排序后，我們要求的就是不難得出一個O(N3)的算法第40頁，共48頁，2022年，5月20日，15點17分，星期一2.4.1.3優(yōu)化我們給式子做一個變形我們用Syi記錄yi到y(tǒng)N的和，Sxi記錄xi到xN的和，那么要求的就是注意此時i和j這兩個參數(shù)相互分離！第41頁，共48頁，2022年，5月20日，15點17分，星期一2.5 單調(diào)性這是很難的一部分內(nèi)容，個人認為，如果是把目標放在NOIP級別的比賽，是不用掌握這部分內(nèi)容的。但是，本著更高更快更強的精神：為了未來我們那崇高的理想！我們不應該著眼于現(xiàn)在！不要為現(xiàn)在而傷感，要相信自己！為了傳遞這份精神，還是淺淺談一下第42頁，共48頁，2022年，5月20日，15點17分，星期一2.5.1 四邊形不等式權(quán)函數(shù)w(i,j)，對于ii j j如果滿足w(i,j)w(i,j)則稱w滿足區(qū)間單調(diào)性如果滿足w(i,j)+w(i