浙江大學(xué)_acm程序設(shè)計(jì)競(jìng)賽_動(dòng)態(tài)規(guī)劃講義-展示頁
2025-01-16 22:44本頁面
【正文】 飛來的高度，計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈。 某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。 攔截導(dǎo)彈 ? 攔截導(dǎo)彈（ Noip2022） ? 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。 動(dòng)規(guī)的要訣－狀態(tài) ? 我們一般在動(dòng)規(guī)的時(shí)候所用到的一些數(shù)組，也就是用來存儲(chǔ)每個(gè)狀態(tài)的最優(yōu)值的。而以前狀態(tài)也就決定了當(dāng)前狀態(tài)的情況。為了避免浪費(fèi)，很顯然，我們存放一個(gè) opt數(shù)組： 記憶化搜索 ? Opt[i, j] 每產(chǎn)生一個(gè) f(i, j)，將 f(i, j)的值放入 opt中，以后再次調(diào)用到 f(i, j)的時(shí)候，直接從opt[i, j]來取就可以了。時(shí)間復(fù)雜度為 2n，明顯是會(huì)超時(shí)的。 ? if f1f2 then f:=f1+a[i,j] else f:=f2+a[i,j]。 ? 解決方法： 記憶化搜索 ? 我們嘗試從正面的思路去分析問題，如上例，不難得出一個(gè)非常簡單的遞歸過程 : ? f1:=f(i1,j+1)。動(dòng)態(tài)規(guī)劃專題講義 前言 ?本文只是個(gè)人對(duì)動(dòng)態(tài)規(guī)劃的一些見解 ,理論性并不一定能保證正確 ,有不足和缺漏之處請(qǐng)諒解和及時(shí)地指出 . 動(dòng)態(tài)規(guī)劃 ? 是信息學(xué)競(jìng)賽中選手必須熟練掌握的一種算法 ,他以其多元性廣受出題者的喜愛 . 目錄 ?什么是動(dòng)態(tài)規(guī)劃 ?狀態(tài) 階段 決策 ?一種確立狀態(tài)的方法 ?兩種簡單的動(dòng)規(guī)武器 ?三種特殊的動(dòng)態(tài)規(guī)劃 什么是動(dòng)態(tài)規(guī)劃 ?在學(xué)習(xí)動(dòng)態(tài)規(guī)劃之前你一定學(xué)過搜索 .那么搜索與動(dòng)態(tài)規(guī)劃有什么關(guān)系呢 ?我們來下面的一個(gè)例子 . 數(shù)字三角形 ?給你一個(gè)數(shù)字三角形 , 形式如下 : 1 2 3 4 5 6 7 8 9 10 找出從第一層到最后一層的一條 路 ,使得所經(jīng)過的權(quán)值之和最小或 者最大 . 數(shù)字三角形 ? 無論對(duì)與新手還是老手，這都是再熟悉不過的題了，很容易地，我們寫出狀態(tài)轉(zhuǎn)移方程： f(i, j)=a[i, j] + min{f(i1, j)+f(i1, j + 1)} ? 對(duì)于動(dòng)態(tài)規(guī)劃算法解決這個(gè)問題，我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向，比較容易地寫出動(dòng)態(tài)規(guī)劃的循環(huán)表示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時(shí)候，也許寫出循環(huán)式的動(dòng)態(tài)規(guī)劃就不是那么簡單了。 f2:=f(i1,j)。 ? 顯而易見，這個(gè)算法就是最簡單的搜索算法。分析一下搜索的過程，實(shí)際上，很多調(diào)用都是不必要的，也就是把產(chǎn)生過的最優(yōu)狀態(tài)，又產(chǎn)生了一次。 ? 于是動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直觀地表示出來了，這樣節(jié)省了思維的難度，減少了編程的技巧，而運(yùn)行時(shí)間只是相差常數(shù)的復(fù)雜度，而且在相當(dāng)多的情況下，遞歸算法能更好地避免浪費(fèi)，在比賽中是非常實(shí)用的 . 記憶化的功效 動(dòng)態(tài)規(guī)劃的實(shí)質(zhì) ?可以看出動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)就是 ?這也就是為什么我們常說動(dòng)態(tài)規(guī)劃必須滿足重疊子問題的原因 .記憶化 ,正符合了這個(gè)要求 . 狀態(tài) 階段 決策 ?或許有一種對(duì)動(dòng)態(tài)規(guī)劃的簡單稱法 ,叫分階段決策 .其實(shí)我認(rèn)為這個(gè)稱法并不是很能讓人理解 .那么下面我們來看看階段 ,狀態(tài) ,決策這三者間得關(guān)系吧 . 狀態(tài) 階段 決策 ? 狀態(tài)是表現(xiàn)出動(dòng)態(tài)規(guī)劃核心思想的一個(gè)東西 .而分階段決策這個(gè)東西有似乎沒有提到狀態(tài) ,這是不科學(xué)的 . ? 階段 ,有些題目并不一定表現(xiàn)出一定的階段性 .數(shù)字三角形的階段就是每一層 .這里我們引入一個(gè)概念 以前狀態(tài) .但階段不是以前狀態(tài) ,狀態(tài)是階段的表現(xiàn)形式 .數(shù)字三角形的以前狀態(tài)就是當(dāng)前層的前一層 . ? 那什么是決策呢 ?我們看看下面一張圖就知道了 . 決策 顯然 ,從上圖可以看出 ,當(dāng)前狀態(tài)通過決策 ,回到了以前狀態(tài) .可見決策其實(shí)就是狀態(tài)之間的橋梁。 數(shù)字三角形的決策就是選擇相鄰的兩個(gè)以前狀態(tài)的最優(yōu)值。 ? 我們就從動(dòng)態(tài)規(guī)劃的要訣，也就是核心部分“狀態(tài)”開始，來逐步了解動(dòng)態(tài)規(guī)劃。但是這種導(dǎo)彈攔截系統(tǒng) 有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高 于前一發(fā)的高度。由于該系統(tǒng)還在試用階段，所以 只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。 攔截導(dǎo)彈 ? 狀態(tài)的表示－ f[i]，表示當(dāng)?shù)?i個(gè)導(dǎo)彈必須選擇時(shí)，前 i個(gè)導(dǎo)彈最多能攔截多少。以前狀態(tài)就是在這個(gè)導(dǎo)彈以前打的那個(gè)導(dǎo)彈。 最長公共子串 ?給出兩個(gè)字符串序列。 交錯(cuò)匹配 ?交錯(cuò)匹配（最長公共子串的改編） 給你兩排數(shù)字 ,只能將兩排中數(shù)字相同的兩個(gè)位置相連 ,而每次相連必須有兩個(gè)匹配形成一次交錯(cuò) ,交錯(cuò)的連線不能再和別的交錯(cuò)連線有交點(diǎn) .問這兩排數(shù)字最多能形成多少個(gè)交錯(cuò)匹配 . 1 2 3 3 2 4 1 5 1 3 5 10 3 1 2 3 2 4 12 1 5 5 3 狀態(tài)的表示－ f[i,j]表示前 i個(gè)第一排的數(shù)字和前 j個(gè)第二排的數(shù)字搭配的最優(yōu)值。 兩城之間還有其他一些停靠站 ,總站數(shù)為 N。 Ekaterinburg城編號(hào)為 1，Sverdlovsk城編號(hào)為 N。 比如，在上面的例圖中， 26沒有直達(dá)票，有幾種買票 方法可以從 26，其中一種是買 C2元的 23車票，再買 C3元的 36車票。 for i:=en downto be do begin while (way[i]way[
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1