[計算機]動態(tài)規(guī)劃的模型構(gòu)建(已修改)
2024-10-28 23:00 本頁面
【正文】 動態(tài)規(guī)劃的模型構(gòu)建 長沙市雅禮中學(xué) 朱全民 NOIP的動態(tài)規(guī)劃試題 ? 加分二叉樹 (2021)— 樹型動態(tài)規(guī)劃 ? 合唱隊形 (2021)— 線型動態(tài)規(guī)劃 ? 青蛙過河 (2021)— 線型動態(tài)規(guī)劃 ? 能量項鏈 (2021)— 合并類型動態(tài)規(guī)劃 ? 金明的預(yù)算方案 (2021)— 資源類型動態(tài)規(guī)劃 ? 矩陣取數(shù)游戲 (2021)— 規(guī)則類型動態(tài)規(guī)劃 ? 傳紙條 (2021)— 規(guī)則類型動態(tài)規(guī)劃 ? 星球貿(mào)易 (2021) — 線型動態(tài)規(guī)劃 ? 烏龜棋 (2021) — 線型動態(tài)規(guī)劃 引例：數(shù)字三角形 如圖所示的數(shù)字三角形中 ? 從第一行的數(shù)字出發(fā) ? 每次向左下或右下走一格，直到最后一行 ? 要求沿途數(shù)字之和最大 1 3 2 4 10 1 4 3 2 20 動態(tài)規(guī)劃的基本概念 ? 階段：把問題分成幾個相互聯(lián)系的有順序的幾個環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。 ? 狀態(tài)：某一階段的出發(fā)位置稱為狀態(tài)。通常一個階段包含若干狀態(tài)。 ? 決策：從某階段的一個狀態(tài)演變到下一個階段某狀態(tài)的選擇。 ? 策略：由開始到終點的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。 動態(tài)規(guī)劃的基本概念 ? 狀態(tài)轉(zhuǎn)移方程：前一階段的終點就是后一階段的起點，前一階段的決策選擇導(dǎo)出了后一階段的狀態(tài)，這種關(guān)系描述了由 k階段到 k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。 ? 目標(biāo)函數(shù)與最優(yōu)化概念：目標(biāo)函數(shù)是衡量多階段決策過程優(yōu)劣的準(zhǔn)則。最優(yōu)化概念是在一定條件下找到一個途徑，經(jīng)過按題目具體性質(zhì)所確定的運算以后，使全過程的總效益達到最優(yōu)。 最優(yōu)化原理 ? 一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。 ? 簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。 ? 最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。 無后效性 ? “過去的步驟只能通過當(dāng)前狀態(tài)影響未來的發(fā)展，當(dāng)前的狀態(tài)是歷史的總結(jié)”。這條特征說明動態(tài)規(guī)劃只適用于解決當(dāng)前決策與過去狀態(tài)無關(guān)的問題。狀態(tài)，出現(xiàn)在策略任何一個位置，它的地位相同，都可實施同樣策略，這就是無后效性的內(nèi)涵。 ? 舉例 ? 最短路（不帶負權(quán)邊，帶負權(quán)邊） 動態(tài)規(guī)劃的解題步驟 ? 劃分階段：注意階段一定要是有序的或者是可排序的，否則問題就無法求解。 ? 選擇狀態(tài)：狀態(tài)的選擇要滿足無后效性。 ? 確定決策：決策決定著狀態(tài)的轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。 ? 寫出狀態(tài)轉(zhuǎn)移方程（包括邊界條件和取值范圍）：根據(jù)問題的性質(zhì)（求最大 /最?。脭?shù)學(xué)方程描述狀態(tài)轉(zhuǎn)移的方法和過程 編程實現(xiàn)？ ? 循環(huán) – For i … – For j … – (dummy) ? 遞歸 – Solve(i,j) – If solved f[i][j] return f[i][j] – (dummy) 數(shù)字三角形求解 ? 狀態(tài)： f(i,j)表示走到第 i行 j列獲得的最大值 ? 狀態(tài)轉(zhuǎn)移方程 : f(i,j)=max{f(i1,j),f(i1,j+1)}+a[i,j] 初始： f(0,0)=0 問題 1：求最短距離（ 1） ? 某人要從 S1前往 SN，其中 Si至 Si+1有若干種行進方式（步行，自行車，公交車，越野車
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1