DP動(dòng)態(tài)規(guī)劃PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1DP動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃第1頁/共74頁第2頁/共74頁第3頁/共74頁第4頁/共74頁者最大者最大.第5頁/共74頁第6頁/共74頁第7頁/共74頁記憶化的功效第8頁/共74頁第9頁/共74頁第10頁/共74頁第11頁/共74頁顯然,從上圖可以看出,當(dāng)前狀態(tài)通過決策,回到了以前狀態(tài).可見決策其實(shí)就是狀態(tài)之間的橋梁。而以前狀態(tài)也就決定了當(dāng)前狀態(tài)的情況。數(shù)字三角形的決策就是選擇相鄰的兩個(gè)以前狀態(tài)的最優(yōu)值。第12頁/共74頁第13頁/共74頁第14頁/共74頁第15頁/共74頁第16頁/共74頁2 3 3 2 4 1 5 1 3 5 103 1 2 3 2 4 12 1 5 5 3 狀態(tài)的表示

2、狀態(tài)的表示fi,jfi,j表示前表示前i i個(gè)第一排的數(shù)字和前個(gè)第一排的數(shù)字和前j j個(gè)第二排的數(shù)字搭配的最優(yōu)值。個(gè)第二排的數(shù)字搭配的最優(yōu)值。當(dāng)前的狀態(tài)就是當(dāng)前你枚舉到的一組交錯(cuò)的后面兩個(gè)位置當(dāng)前的狀態(tài)就是當(dāng)前你枚舉到的一組交錯(cuò)的后面兩個(gè)位置. .例如上圖中當(dāng)前狀態(tài)是例如上圖中當(dāng)前狀態(tài)是3 3和和1(1(第一組交錯(cuò)第一組交錯(cuò)),),枚舉他的以前狀態(tài)就有枚舉他的以前狀態(tài)就有1 3.1 3.這樣在這樣在1 31 3之前會(huì)有一個(gè)最優(yōu)值存在之前會(huì)有一個(gè)最優(yōu)值存在, ,因此可以由此得到因此可以由此得到3 13 1的最優(yōu)值的最優(yōu)值. .第17頁/共74頁號(hào)為號(hào)為N N。第18頁/共74頁第19頁/共74頁

3、怎么怎么辦辦第20頁/共74頁當(dāng)前所在的某個(gè)車站這一題的以前狀態(tài)其實(shí)只有這一題的以前狀態(tài)其實(shí)只有3種種.即滿足即滿足3種距離種距離(收費(fèi)收費(fèi))情況的情況的3個(gè)車站個(gè)車站.要知道這要知道這3個(gè)車站可以先做一個(gè)預(yù)處理個(gè)車站可以先做一個(gè)預(yù)處理.顯然這顯然這3個(gè)車站在滿足距離限制的條件下應(yīng)該越遠(yuǎn)越好個(gè)車站在滿足距離限制的條件下應(yīng)該越遠(yuǎn)越好.第21頁/共74頁第22頁/共74頁第23頁/共74頁第24頁/共74頁第25頁/共74頁第26頁/共74頁第27頁/共74頁第28頁/共74頁或許你不明白我在說什么,那么我們通過題目來說明吧第29頁/共74頁第30頁/共74頁后后,乘積最大的一題也是乘積最大的一題

4、也是完全一樣的形式完全一樣的形式,誰還會(huì)誰還會(huì)去用搜索去用搜索?第31頁/共74頁第32頁/共74頁第33頁/共74頁尋找定量!第34頁/共74頁第35頁/共74頁第36頁/共74頁第37頁/共74頁第38頁/共74頁第39頁/共74頁第40頁/共74頁定量很不錯(cuò)啊!第41頁/共74頁第42頁/共74頁第43頁/共74頁第44頁/共74頁第45頁/共74頁第46頁/共74頁對(duì)于所給出的矩陣找出一條最長的遞減鏈,滿足鏈中相鄰的兩個(gè)元素間都是在矩陣中相鄰的.上圖中所給出的矩陣中的最長鏈?zhǔn)? 2 3 425.第47頁/共74頁第48頁/共74頁第49頁/共74頁第50頁/共74頁第51頁/共74頁第

5、52頁/共74頁|講完了比較實(shí)用的兩種種動(dòng)規(guī)的武器之后,我們來看看一些大家可能不太會(huì)做的動(dòng)規(guī)類型第53頁/共74頁第54頁/共74頁第55頁/共74頁第56頁/共74頁第第i個(gè)房間個(gè)房間.用用fi,j來表來表示示.第57頁/共74頁K表示的是和I連接的一個(gè)房間,ci表示進(jìn)入I號(hào)房間的花費(fèi).第58頁/共74頁會(huì)的總活躍指數(shù)最大。會(huì)的總活躍指數(shù)最大。第59頁/共74頁第60頁/共74頁j,0),j為為i的的i兒子）。兒子）。n這就是樹狀動(dòng)規(guī)的基這就是樹狀動(dòng)規(guī)的基本形態(tài)。本形態(tài)。第61頁/共74頁第62頁/共74頁第63頁/共74頁最小的結(jié)點(diǎn)有哪些。最小的結(jié)點(diǎn)有哪些。如有多個(gè)最小的如有多個(gè)最小的Ai，則都要輸出。這里則都要輸出。這里N=10000N=10000第64頁/共74頁