[計算機(jī)]動態(tài)規(guī)劃的模型構(gòu)建-展示頁
2024-10-25 23:00本頁面
【正文】 。 顯然時間復(fù)雜度為 O(n2)。 ? 問最快到達(dá)的時間是多少？ 分析 ? 劃分階段、選擇狀態(tài)： ? 使用與上面一樣的方案發(fā)現(xiàn)不可行，無法解決判定是否需要切換行進(jìn)方式 ? 加一維狀態(tài)進(jìn)行表示 ? 用 f[i][j]表示要從 S1到達(dá) Si，在 Si時使用的出行方式為 j，所需最短的時間 ? 寫出規(guī)劃方程（包括邊界條件） 思考？ ? 必須在每個地點切換行進(jìn)方式？ ? “ Si至 Si+1有若干種行進(jìn)方式”為“ Si至 Sj(ji)有若干種行進(jìn)方式”？ ? 若為任意兩點 Si至 Sj之間都有若干種行進(jìn)方式？ ? 若在切換時候需要行進(jìn)方式時須增加時間？ ? 中途經(jīng)過的地點不能超過 X個，該如何處理？ ? 若費用為負(fù)怎么辦？ 分析 ? 設(shè) f(i)表示前 i個數(shù)的最長不上升序列的長度。 ? 確定決策：決策決定著狀態(tài)的轉(zhuǎn)移，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。 ? 舉例 ? 最短路（不帶負(fù)權(quán)邊，帶負(fù)權(quán)邊） 動態(tài)規(guī)劃的解題步驟 ? 劃分階段：注意階段一定要是有序的或者是可排序的，否則問題就無法求解。這條特征說明動態(tài)規(guī)劃只適用于解決當(dāng)前決策與過去狀態(tài)無關(guān)的問題。 ? 最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)，任何問題，如果失去了最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。 最優(yōu)化原理 ? 一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。 ? 目標(biāo)函數(shù)與最優(yōu)化概念：目標(biāo)函數(shù)是衡量多階段決策過程優(yōu)劣的準(zhǔn)則。 ? 策略：由開始到終點的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。通常一個階段包含若干狀態(tài)。動態(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)規(guī)劃的基本概念 ? 狀態(tài)轉(zhuǎn)移方程：前一階段的終點就是后一階段的起點，前一階段的決策選擇導(dǎo)出了后一階段的狀態(tài)，這種關(guān)系描述了由 k階段到 k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。最優(yōu)化概念是在一定條件下找到一個途徑，經(jīng)過按題目具體性質(zhì)所確定的運算以后，使全過程的總效益達(dá)到最優(yōu)。 ? 簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。 無后效性 ? “過去的步驟只能通過當(dāng)前狀態(tài)影響未來的發(fā)展，當(dāng)前的狀態(tài)是歷史的總結(jié)”。狀態(tài)，出現(xiàn)在策略任何一個位置，它的地位相同，都可實施同樣策略，這就是無后效性的內(nèi)涵。 ? 選擇狀態(tài)：狀態(tài)的選擇要滿足無后效
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1