動(dòng)態(tài)規(guī)劃ppt課件(2)(參考版)
2025-05-09 12:08本頁(yè)面
【正文】 課后作業(yè) ? 編程練習(xí)題：課后編寫本次課程中的 Flight Planning 的程序。 } } 總結(jié)及回顧： 本次課主要講解了如下內(nèi)容： ? 動(dòng)態(tài)規(guī)劃的要素； ? 多段圖問(wèn)題； ? 動(dòng)態(tài)規(guī)劃的求解步驟； ? 導(dǎo)彈攔截問(wèn)題； ? Flight Planning。++k） t[k]=r[k]。 //這三步選擇最好的結(jié)果 } for（ k=0。 if（ a[i][x[1]]a[i][r[j]]） r[j]=x[1]。k++） x[k]=t[（ 1k） ^j]。++j） { //j表示 8種結(jié)果 for（ k=0。i） { //從后往前采用動(dòng)態(tài)規(guī)劃 for（ j=0。 //初始化 for（ i=n1。i8。a[i][j]） 。j8。in。n） 。c） 。 //存儲(chǔ)表決傾向 int main（） { int r[8],t[8],x[3]。 char oute[8][4]={NNN,NNY,NYN,NYY,YNN,YNY,YYN,YYY}。從后面往前計(jì)算，對(duì)每一種情況，可以選擇的變化是三個(gè)，從這三個(gè)變化中找到最好的結(jié)果。 倒數(shù)第二個(gè)： 8 3 6 5 1 2 7 4 倒數(shù)第一個(gè)： 1 2 3 4 5 6 7 8 NNN,NNY, NYN, NYY, YNN, YNY, YYN, YYY ? 得到的狀態(tài)序列將是 ? NNY NNN NNN NNY NNN NNY NYN NYY ? NNN NNY NNY NYY NNY NYY NYY NNY ? NNY NYY NYY NNY NYY NNY NNY NYY ? NYY NNY NNY NYY NNY NYY NYY NNY ? 這是一個(gè)系列的決策過(guò)程，所以可以采用動(dòng)態(tài)規(guī)劃的方法。 ? 倒數(shù)第二怎么投？ ? 假設(shè)他面對(duì)的是 NYY，他可以變?yōu)?{NNY， NYN， YYY}，這其中他最喜歡的是 NNY，但他就會(huì)選擇 NNY嗎？不會(huì)！ ? 因?yàn)檫x擇 NNY，最后（通過(guò)最后牧師表決）的結(jié)果就是NNN，是他最不喜歡的，他的選擇是 YYY，因?yàn)樽詈蟮慕Y(jié)果將是 NYY，是可以得到的最好結(jié)果。如果你是 1號(hào)海盜，你會(huì)提出怎樣的分配方案，使你獲得最多的寶石且保住性命？ ? 因?yàn)楹１I很聰明，所以你能想到的別的也能想到。再由 2號(hào)海盜提出他的分配方案，重復(fù)以上過(guò)程，直到找到分配方案止。他們決定將寶石分掉之后就分手，洗手不干了。 ?所以，貪心的思路不行。假如有兩個(gè)人來(lái)選擇，選擇傾向是： 2 1 7 4 5 8 3 6 3 8 6 4 5 1 2 7 ?如果按照貪心的思想去做，第一個(gè)人應(yīng)該選擇 NNY,但第二個(gè)人肯定會(huì)選擇成 YNY，結(jié)果是第一個(gè)人最不滿意的。 輸入樣例 2 4 8 7 6 5 4 3 2 1 8 6 3 1 2 4 5 7 8 3 6 5 1 2 7 4 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 輸出樣例 NYY NNY 解題思路 ?這個(gè)題似乎可以采用貪心來(lái)做。 輸出 ?對(duì)于每個(gè)問(wèn)題，輸出三個(gè)議案的表決結(jié)果。對(duì)于每種結(jié)果（ NNN,NNY, NYN, NYY, YNN, YNY, YYN, YYY, ‘N’表示否，‘ Y’表示是） ,給一個(gè) [1…8] 之間的數(shù)，越小的數(shù)字表示選擇可能性越大。每次表決由一個(gè)整數(shù) m開始， 1=m=100，表示牧師的數(shù)目。 輸入 ? 輸入從一個(gè)整數(shù) n開始 ,1=n=100，代表表決的次數(shù)。不管怎么說(shuō)，只有牧師們的表決傾向留下來(lái)了，沒(méi)有實(shí)際的表決結(jié)果。由于彼此間都知道表決傾向，每位牧師都爭(zhēng)取對(duì)自己最有利的結(jié)果，而且 Uxuhul人具有高超的邏輯推理能力，對(duì)游戲規(guī)則又很了解，每個(gè)牧師都能找到最理想的方法！ ?最后，復(fù)雜刻板行政系統(tǒng)導(dǎo)致 Uxuhul文明的崩潰。 ? Uxuhul的政治相當(dāng)復(fù)雜，大量代表不同利益的游說(shuō)（和行賄），影響三個(gè)議案的八種結(jié)果。不允許不表決。最初所有的石塊都是黑色的面朝上，表示所有的議案都是否定的結(jié)果。在桌子上放了三片石塊，一面黑，一面白。每次嚴(yán)格限定表決三個(gè)議案，每個(gè)議案只有是 /否的回答。在中美洲叢林中，大約從公元前 3200年的黃金時(shí)代， Uxuhul文化繁榮了近千年。 輸出最小的總耗油量 data[k,data3[k]]。 for i:=k downto 2 do data3[il]← data2{i,data3[i]}。 將滿足上式的 l記入記憶表 data2[i,j]。 顯然這個(gè)最優(yōu)化問(wèn)題包含了重疊子問(wèn)題，采用動(dòng)態(tài)程序設(shè)計(jì)方法是最合適不過(guò)的了，按照上述分析，我們可以直接寫出動(dòng)態(tài)規(guī)劃的方程： 1≤i≤k 20≤j≤40 20≤l≤40 ????????1ij ] }l,g [ i ,l]1,m i n { d a t a [ i1ij]g [ 1 , 0 ,j]d a t a [ i , ? 求解 data表和 data2表的算法十分簡(jiǎn)單： for j:=20 to 40 do data[1,j] ← g[1,0,j]。 j]data2[i,g [ i ,d a t a 2 [ i ,j ] ,j ] ? ?? ?ji,d a t a 21,id a t a ?? ?ji,da ta? ?ji,data 下面我們來(lái)分析一下最優(yōu)表達(dá)式的構(gòu)造： ? 飛機(jī)由地域 1起飛，因此 data[1,j]=g[1,0,j] (20≤ j≤40 ). ? 然后順序計(jì)算， data[2,20] … data[2,40],data[3,20], … ,data[3,40],.....data[k,20], … ,data[k,40]. 在計(jì)算 data[i,j]時(shí)，我們無(wú)法預(yù)計(jì)飛機(jī)在地域 i1應(yīng)以怎樣的高度飛行方可使表達(dá)式的值最小。 由于 為一個(gè)定值，因此 的值必須最小。每垂直偏離 aopt高度一個(gè)單位，需要增加耗油量 aoptm ?g p h e x t r aa o p tmg p h o p tb ????? i的實(shí)際飛行時(shí)間 c c = 地域 i的長(zhǎng)度 / 地域 i的實(shí)際飛行速度 由于地域 i的風(fēng)速垂直反向線性變化， m單位處的風(fēng)速為在 20單位處的風(fēng)速與 40單位處的風(fēng)速的平均數(shù)，因此地域 i的等高風(fēng)速為 2040)40()20(－的低空風(fēng)速地域的高空風(fēng)速地域 imim ????? 而飛機(jī)的實(shí)際速度為 VCRUISE與地域 i等高風(fēng)速的矢量和，因此 c = 地域 i的長(zhǎng)度 / (地域 i的等高風(fēng)速＋ VCRUISE) 顯而易見， ? ? cbamlig ???,? 二．規(guī)劃飛行方案 設(shè) 為在確定地域 i的飛行高度為 j的情況下，飛機(jī)由地域 l飛至地域 i所耗費(fèi)的最小總耗油量； 為記憶表。 } printf（ %d\n,c） 。 d[i]=max+1。amp。jcount。i） { //用動(dòng)態(tài)規(guī)劃計(jì)算所有最優(yōu)值 max=0。 for（ i=count2。 //輸入高度 d[count1]=1。//h表示高度值，d表示最優(yōu)值， c是能攔截得最多導(dǎo)彈數(shù) count=0。這樣，每個(gè) D（ i）的值只計(jì)算一次，并在計(jì)算的同時(shí)把計(jì)算結(jié)果保存下來(lái)，從而避免了有些子問(wèn)題被重復(fù)計(jì)算的情況發(fā)生，提高了程序的效率。 ? 其實(shí)，通過(guò)以上分析，我們已經(jīng)知道： D（ n） =1。比如在調(diào)用遞歸函數(shù)計(jì)算 D（ 1）的時(shí)候，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1