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

動態(tài)規(guī)劃優(yōu)化第1頁，共48頁，2023年，2月20日，星期日簡介動態(tài)規(guī)劃優(yōu)化的主要方法：1、降維（優(yōu)化狀態(tài)）2、優(yōu)化轉(zhuǎn)移3、常數(shù)優(yōu)化第2頁，共48頁，2023年，2月20日，星期日1.降維降維是一個通用的說法，其實質(zhì)就是通過改變動態(tài)規(guī)劃的狀態(tài)含義，或者拋棄一些冗余狀態(tài)環(huán)節(jié)，達到減少狀態(tài)，加速動態(tài)規(guī)劃的目的第3頁，共48頁，2023年，2月20日，星期日1.1轉(zhuǎn)變思路很多時候，當(dāng)?shù)贸瞿撤N動態(tài)規(guī)劃模型的時候，不要著急動手，而是需要仔細思考一下，是不是有更好的狀態(tài)表示方法多積累經(jīng)驗，同時又不能拘泥于死板的模型理論，要有創(chuàng)新意識。第4頁，共48頁，2023年，2月20日，星期日1.1.1例題給定N*M的空白棋盤，在其中放任意放車（可以不放），要使得放在棋盤上的車兩兩不能攻擊，求方案總數(shù)MODP的值。第5頁，共48頁，2023年，2月20日，星期日1.1.1.1思路一按照基本的狀態(tài)壓縮動態(tài)規(guī)劃模型進行解答。opt[K][S]表示已經(jīng)放了前K行，并且每一列是否有車的狀態(tài)為S（S為一個0/1的2進制序列，那一位為1則表示對應(yīng)一列已經(jīng)放過了一個車）的合法方案的數(shù)量。比如opt[2][(101)2]即表示前2行放了車且第1，3列有車的狀態(tài)。第6頁，共48頁，2023年，2月20日，星期日1.1.1.1思路一則轉(zhuǎn)移就是枚舉這一行放還是不放，如果放的話則枚舉所有沒有放車的行，將對應(yīng)的2進制位標(biāo)記為1，進行轉(zhuǎn)移。時間復(fù)雜度O(NM2M)空間復(fù)雜度O(2M)但是……如果N,M>1000該怎么辦呢？第7頁，共48頁，2023年，2月20日，星期日1.1.1.2思路二換一個角度來分析問題可以發(fā)現(xiàn)，我們需要知道的只是有多少列目前沒有放車，并不需要知道具體是哪些列沒有放車！因此opt[k][(101)2]和opt[k][(110)2]是本質(zhì)等價的。于是我們可以把狀態(tài)改為：opt[k][S]表示放置了前k行，并且有S列沒有放置。第8頁，共48頁，2023年，2月20日，星期日1.1.1.2思路二此時轉(zhuǎn)移稍有不同opt[k+1][S]=opt[k][S]+opt[k][S+1]*(S+1)此時時間復(fù)雜度為O(NM)空間復(fù)雜度為O(NM)問題得到了解決可見對問題透徹的分析是得出最有效規(guī)劃方式的前提。第9頁，共48頁，2023年，2月20日，星期日1.2拋棄冗余很多時候一些狀態(tài)是不需要的，或者某些維是可以合并的。經(jīng)過合理的分析我們可以拋棄一些冗余信息，減少狀態(tài)，加速轉(zhuǎn)移。第10頁，共48頁，2023年，2月20日，星期日1.2.1例題poet(NOI2009day1p2)有N個詩句，要每個詩句有一個長度Li，要將其排版，一行可以放若干詩句并且每句詩中間用一個空格隔開，有一標(biāo)準(zhǔn)長Len，每一行的難看度是當(dāng)前行長度C與Len之差絕對值的P次方。求一種最好看的排版方式使得總難看度最小。N<10000L<2001<P<10第11頁，共48頁，2023年，2月20日，星期日1.2.1.1思路一由于標(biāo)準(zhǔn)行長L很小我們不難想到一個如下的動態(tài)規(guī)劃方法：opt[K][S]表示排版了前K個句子，并且當(dāng)前行長是S。對于每個狀態(tài)轉(zhuǎn)移就是枚舉是將這個詩句放在行末還是換行。有一個問題是：如果一個詩句過長怎么辦？？？那我們也將數(shù)組下標(biāo)開的很大么？？第12頁，共48頁，2023年，2月20日，星期日1.2.1.2思路二仔細分析，不難發(fā)現(xiàn)，第二維狀態(tài)是沒有用的。我們需要知道只是每一行最后一個詩句是那個就可以了，并不用關(guān)心每行具體多長。我們拋棄第二維：opt[K]表示安排了前K個詩句并且第K個詩句在行末所能獲得的最小難看度。第13頁，共48頁，2023年，2月20日，星期日1.2.1.2思路二那么轉(zhuǎn)移就是opt[K]=min(opt[i]+cost(i+1,K)|i<K)cost(i+1,K)表示第i+1到第K個詩句放一行的難看度。那如何利用L<200的條件呢？用Sum(L,R)表示第L到第R個詩句放一行的總長如果對于i，存在j使得Sum(i,j-1)>L且Sum(j,K)>L則所有i之前的決策都是無用的。第14頁，共48頁，2023年，2月20日，星期日1.2.1.2思路二時間復(fù)雜度O(NL)空間復(fù)雜度O(N)不難發(fā)現(xiàn)我們是利用L<200這個條件在動態(tài)規(guī)劃中進行了一個剪枝從而將一個空間復(fù)雜度無法估計的動態(tài)規(guī)劃成功降低到了O(N)，并成功將復(fù)雜度降低。剔除動態(tài)規(guī)劃中的冗余信息是優(yōu)化動態(tài)規(guī)劃的重要方面。第15頁，共48頁，2023年，2月20日，星期日2.優(yōu)化轉(zhuǎn)移1、優(yōu)化轉(zhuǎn)移方式2、預(yù)處理3、費用提前計算4、參數(shù)分離5、單調(diào)性第16頁，共48頁，2023年，2月20日，星期日2.1優(yōu)化轉(zhuǎn)移方式基本的轉(zhuǎn)移方式共有兩種1、通過狀態(tài)選擇決策2、通過決策來更新狀態(tài)第17頁，共48頁，2023年，2月20日，星期日2.1.1狀態(tài)選擇決策對于每個狀態(tài)會有一些決策來選擇，我們從中選擇一個最優(yōu)的決策，來實現(xiàn)規(guī)劃的過程，并完成了當(dāng)前這一狀態(tài)的計算。可以認(rèn)為這是一個正向過程。一個簡單的例子opt[k]=min(opt[i]+1|A[i]<A[k])這是一個不下降子序列的動態(tài)規(guī)劃方程不難得到這個方法O(NlogN)轉(zhuǎn)移方式第18頁，共48頁，2023年，2月20日，星期日2.1.2決策更新狀態(tài)當(dāng)一個狀態(tài)計算完畢，那么這個狀態(tài)就自然的成為了后面狀態(tài)選擇的一個決策，于是我們可以在剛產(chǎn)生這個決策的時候更新所有可能用到這個決策的狀態(tài)。可以說這是一個逆向行為的過程。大多數(shù)時候正向方式和逆向方式是差不多的，或者正向方式優(yōu)于逆向方式，當(dāng)然也有例外，因此需要我們自己根據(jù)實際情況靈活選擇。第19頁，共48頁，2023年，2月20日，星期日2.1.2.1例題給N*M的存在一些障礙的棋盤，在其中放置1*2的多米諾骨牌，問合法的放置總數(shù)MODP是多少。第20頁，共48頁，2023年，2月20日，星期日2.1.2.1.1說在前面我們這里先介紹一種對于狀態(tài)壓縮動態(tài)規(guī)劃轉(zhuǎn)移和狀態(tài)表示的一般方法——按格（點）轉(zhuǎn)移。opt[x][y][S]表示當(dāng)前決策格為(x,y)同時2進制狀態(tài)S表示當(dāng)前掃描線上每個格子是否被覆蓋的狀況。第21頁，共48頁，2023年，2月20日，星期日2.1.2.1.1說在前面OPT[x][y][(000000)2]OPT[x][y+1][(011000)2]第22頁，共48頁，2023年，2月20日，星期日2.1.2.1.2分析不難發(fā)現(xiàn)我們之前選擇了一種逆向轉(zhuǎn)移的方式——即從當(dāng)前狀態(tài)枚舉下一步行為，并向后更新這樣的好處在于（1）方便情況的討論，簡化轉(zhuǎn)移（2）避免了很多不可能出現(xiàn)的狀態(tài)（3）加速了決策時間復(fù)雜度O(N2M)其實，還有一些情況是只有這種更新方式才能優(yōu)化的，限于篇幅和難度問題這里就不多說了第23頁，共48頁，2023年，2月20日，星期日2.2預(yù)處理預(yù)處理就是將動態(tài)規(guī)劃中常用的一些計算環(huán)節(jié)預(yù)先處理好，方便動態(tài)規(guī)劃中重復(fù)用到，很多時候利用這種并行計算的問題是可以大大降低算法復(fù)雜度的。第24頁，共48頁，2023年，2月20日，星期日2.2.1例題Grid(BOI2008)有分成N*M格的土地，每個土地有一個工作時間，現(xiàn)在可以將這些土地分成(r+1)*(s+1)塊，每塊由一個工作人員來完成工作，問最快能多長時間完成全部格子上的工作？r<N<18s<M<18第25頁，共48頁，2023年，2月20日，星期日2.2.1.1分析簡單的想法是首先枚舉橫向如何對土地進行分割，然后再對縱向進行動態(tài)規(guī)劃。枚舉部分我們不多說，這里共需要C(N,r)的時間，我們用數(shù)組lis記錄分割情況關(guān)于動態(tài)規(guī)劃，不難得到如下方程：opt[i][k]表示第i個豎線為第k個分割線。轉(zhuǎn)移比較簡單opt[i][k]=min{max(opt[j][k-1],f(j,i))}第26頁，共48頁，2023年，2月20日，星期日2.2.1.1分析代價f我們可以邊轉(zhuǎn)移邊計算。我們從i開始從后往前枚舉j，那么我們顯然每次只需要O(N)的代價就可以計算出當(dāng)前的f。動態(tài)規(guī)劃的時間復(fù)雜度為O(rsM2)算法的總體復(fù)雜度為O(C(N,r)rsM2)第27頁，共48頁，2023年，2月20日，星期日2.2.1.2優(yōu)化1.預(yù)處理出sum[x][y]數(shù)組，記錄矩形(1,1)-(x,y)中每個格子的工作量之和。則對于任意矩形，我們都可以在O(1)時間內(nèi)計算出部分和。2.搜索完行的拆分之后，我們預(yù)處理出所有f數(shù)組。計算f數(shù)組的時間復(fù)雜度為O(M2r)此時動態(tài)規(guī)劃復(fù)雜度為O(M2s)總復(fù)雜度降為O(C(N,r)M2(r+s))第28頁，共48頁，2023年，2月20日，星期日2.3費用提前計算在動態(tài)規(guī)劃問題中很多時候計算轉(zhuǎn)移代價成了我們一個很棘手的問題，有些時候我們可能要花費很多的力氣來計算某一些特定狀態(tài)下的費用（比如邊界狀態(tài)等等）其實很多時候我們可以用一些方法，把費用計算花去的時間平攤到其他的地方，從而優(yōu)化動態(tài)規(guī)劃第29頁，共48頁，2023年，2月20日，星期日2.3.1例題Sue的小球(sdtsc2008)天空中有N個坐標(biāo)為(xi,yi)的小球，并會以vi速度勻速下降，這個小球的價值就是其y坐標(biāo)的1000分之一你有一個在x坐標(biāo)軸上滑行的飛行器，可以以單位速度在x軸上平移，只要和小球到同一x坐標(biāo)就能收獲那個小球。假設(shè)你一開始在(0,0)，并且希望收獲所有小球，問可能的最大收益是？N<1000第30頁，共48頁，2023年，2月20日，星期日2.3.1.1分析由于所有小球的x坐標(biāo)是不變的，因此我們按照x坐標(biāo)將小球排序。觀察一個性質(zhì)：我們獲得球必然是一個連續(xù)區(qū)間。因此不難得出動態(tài)規(guī)劃表示方法：opt[L][R][0/1]表示獲得球的區(qū)間是[L,R]，同時此時飛行器在左邊/右邊球所對應(yīng)的x坐標(biāo)。第31頁，共48頁，2023年，2月20日，星期日2.3.1.1分析但是，如何計算代價呢？考慮到一個很好的性質(zhì)：飛行器的移動速度是單位速度。一種簡單的方式是增加一維時間：opt[L][R][T][0/1]表示時刻T此時的狀態(tài)?？梢允褂藐犃斜４婵尚袪顟B(tài)，再使用更新狀態(tài)的方法進行轉(zhuǎn)移。第32頁，共48頁，2023年，2月20日，星期日2.3.1.2優(yōu)化現(xiàn)在問題的關(guān)鍵在于如何快速的計算費用。我們現(xiàn)在糾結(jié)的問題在于，我們并不知道之前我們是如何行走的，所以如果沒有T，我們并不知道當(dāng)前我們面對的球到底是多少價值。第33頁，共48頁，2023年，2月20日，星期日2.3.1.2優(yōu)化我們不妨換個思路，為什么要去糾結(jié)于之前的狀態(tài)呢？當(dāng)我們做了一個決策之后，對后面的影響我們是知道的，為什么不能把握這一我們清楚的信息呢？道理很清楚：第34頁，共48頁，2023年，2月20日，星期日2.3.1.2優(yōu)化每次決策后，我們將這一次移動對所有我們還沒有得到的小球產(chǎn)生的費用損失都在決策時計算。我們可以看作小球都沒有動，只是在我們每次決策是損失了一些價值。假設(shè)當(dāng)前移動花費了時間T，我們還沒有得到的小球的速度和是SV，那么損失的代價就是T*SV/1000第35頁，共48頁，2023年，2月20日，星期日2.3.1.3問題的解決我們用S[I]記錄前I個小球的速度和那么我們的轉(zhuǎn)移方程就是：opt[L][R][0/1]-(S[N]-S[R’]+S[L’-1])*T/1000+valueopt[L’][R’][0/1]時空復(fù)雜度O(N2)第36頁，共48頁，2023年，2月20日，星期日2.4參數(shù)分離這是一個信息學(xué)競賽中非常重要的手段，當(dāng)然難度也比較大，這里限于篇幅和難度，只是簡單說一下。參數(shù)分離就是通過數(shù)學(xué)變形將和決策有關(guān)的變量和狀態(tài)有關(guān)的變量分開，從而發(fā)現(xiàn)一些性質(zhì)來優(yōu)化動態(tài)規(guī)劃。第37頁，共48頁，2023年，2月20日，星期日2.4.1例題Triangles(POI07-08StageIII)給定平面上N<1000個點，則顯然會構(gòu)成N(N-1)(N-2)/3個三角形求所有這些三角形的面積和第38頁，共48頁，2023年，2月20日，星期日2.4.1.1預(yù)備知識首先必須要知道叉積……向量a=(x1,y1)，b=(x2,y2)則有：a×b=x1*y2–x2*y1=|a||b|sinΘΘ為有向角度因此只要保證方向為正，那么向量a和b組成的三角形面積即為(a×b)/2第39頁，共48頁，2023年，2月20日，星期日2.4.1.2分析首先我們花O(N)的時間枚舉左下角c所有需要計算的點都以點c為原點建系假設(shè)坐標(biāo)為x[i]和y[i]按極角排序后，我們要求的就是不難得出一個O(N3)的算法第40頁，共48頁，2023年，2月20日，星期日2.4.1.3優(yōu)化我們給式子做一個變形我們用Sy[i]記錄y[i]到y(tǒng)[N]的和，Sx[i]記錄x[i]到x[N]的和，那么要求的就是注意此時i和j這兩個參數(shù)相互分離！第41頁，共48頁，2023年，2月20日，星期日2.5單調(diào)性這是很難的一部分內(nèi)容，個人認(rèn)為，如果是把目標(biāo)放在NOIP級別的比賽，是不用掌握這部分內(nèi)容的。但是，本著更高更快更強的精神：為了未來我們那崇高的理想！我們不應(yīng)該著眼于現(xiàn)在！不要為現(xiàn)在而傷感，要相信自己！為了傳遞這份精神，還是淺淺談一下第42頁，共48頁，2023年，2月20日，星期日2.5.1四邊形不等式權(quán)函數(shù)w(i,j)，對于i≤i’<j≤j’如果滿足w(i’,j)≤w(i,j’)則稱w滿足區(qū)間單調(diào)性如果滿足