歡迎來到動態規劃 (Dynamic Programming)!
歡迎來到決策數學 (Decision Mathematics) 中最強大的工具之一！如果你曾經規劃過一段需要多次轉乘的長途旅行，或者嘗試過如何在有限的預算下進行數個月的支出安排，其實你已經運用過動態規劃 (Dynamic Programming, DP) 的邏輯了。
在本章中，我們將探討一種「分而治之」(divide and conquer) 的方法。我們不會試圖一次解決一個龐大又嚇人的問題，而是將其拆解為較小、易於處理的「階段」(stages)，並一步步完成它們。別擔心一開始看起來數據量很大——一旦你掌握了表格的運作規律，這件事會變得非常有節奏感（而且是好的那種重複！）。
1. 核心概念：貝爾曼最優性原理 (Bellman’s Principle of Optimality)
在我們研究表格和數字之前，必須先理解 DP 的黃金法則，這被稱為貝爾曼最優性原理 (Bellman’s Principle of Optimality)。
原理： 一個最優策略具有這樣的屬性：無論初始狀態和初始決策為何，剩餘的決策對於由第一次決策所產生的狀態而言，必然構成一個最優策略。
等等，能說人話嗎？
想像一下，從倫敦到愛丁堡的最短路線經過約克 (York)。貝爾曼其實只是說：這段旅程中「約克到愛丁堡」的部分，必須是從約克到愛丁堡所有可能路徑中的最短路徑。如果不是，你只需要換一條從約克到愛丁堡更好的路，整段倫敦到愛丁堡的旅程就會變得更短！
小貼士： 在考試中，你幾乎總是需要逆向 (backwards) 思考。我們從終點線開始，一路往起點回推。這確保了我們找到的每一個子路徑都已經是「最佳」的選擇。
重點總結： 最優路徑的任何一部分，本身也必然是一條最優路徑。
2. 動態規劃的術語
要建立表格，我們需要先熟悉這些專有名詞。有兩個主要的變數是你必須知道的：
- 階段 (Stage)： 這通常代表「距離終點還有多少步」。如果你距離終點還有 3 個站，你就是在第 3 階段。
- 狀態 (State)： 這描述了你在某個階段開始時的當前狀況或位置。（例如：「我現在位於頂點 C」）。
比喻：電子遊戲
想像一個有 5 個關卡的遊戲。
階段 (Stage) 是你正處於第幾關（倒數至最終頭目）。
狀態 (State) 是你在進入該關卡開始時，擁有多少生命值或彈藥。
3. 通過列表法 (Tabulation) 解決問題
Edexcel 課程大綱要求你使用特定的表格格式。它看起來可能讓人望而生畏，但它遵循著邏輯流向。我們通常從階段 \(n\)（最後一步）向後工作，回到階段 1（第一步）。
標準表格欄位：
- 階段 (Stage)： 剩餘的步數。
- 狀態 (State)： 在此階段你的起點。
- 動作 (Action)： 你決定下一步要去哪裡。
- 目的地 (Destination)： 下一個階段你所到達的狀態。
- 數值 (Value)： 當前動作的成本/利潤 + 從前一個階段得出的最佳值。
- 最優值 (Optimal Value)： 該特定狀態的「最佳」結果。
你知道嗎？
這種逆向工作的過程稱為自下而上法 (Bottom-up approach)。從目的地規劃路徑回起點感覺可能有點反直覺，但它能防止你重複計算相同的路徑，效率極高！
4. 不同類型的目標
根據題目不同，你可能需要尋找不同類型的「最優」路徑。請仔細留意以下詞彙：
A. 最小化 (Minimising，如最短路徑或最低成本)
你想要的是總和最小。
公式： \(Value = (\text{當前成本}) + (\text{前一階段的最優值})\)
B. 最大化 (Maximising，如最高利潤)
你想要的是總和最大。
公式： \(Value = (\text{當前利潤}) + (\text{前一階段的最優值})\)
C. 極小極大化 (Minimax，即「安全第一」路線)
你想要找到一條路徑，使得你面臨的最大懲罰儘可能小。這常見於涉及風險或橋樑「最大載重」的問題。
公式： \(Value = \max(\text{當前值, 前一階段的最優值})\)
然後，在你的最優值欄位中選擇這些最大值中的最小值。
D. 極大極小化 (Maximin，即「最壞情況下的最好」路線)
你想要確保你的最小收益儘可能大。
公式： \(Value = \min(\text{當前值, 前一階段的最優值})\)
然後，在你的最優值欄位中選擇這些最小值中的最大值。
快速複習盒：
- 最小化 (Minimise)： 總和最小。
- 最大化 (Maximise)： 總和最大。
- 極小極大化 (Minimax)： 最大值中的最小值。
- 極大極小化 (Maximin)： 最小值中的最大值。
5. 逐步建立表格
如果一開始覺得棘手別擔心！請依照以下步驟解決標準的最短路徑問題：
- 識別階段： 在網絡圖上畫出垂直線。最終目的地是第 0 階段（無後續動作）。直接連向目的地的節點屬於第 1 階段。
- 開始繪表： 建立你的欄位，從第 1 階段開始。
- 填寫第 1 階段： 列出所有能到達目的地的狀態。其「最優值」就是該弧線前往目的地的權重。
- 移至第 2 階段： 列出所有能到達第 1 階段中那些節點的狀態。對於每一個動作，將弧線權重與你剛剛在第 1 階段找到的「最優值」相加。
- 挑選優勝者： 對於每個狀態，查看所有可能的動作，並選擇能產生最佳結果（例如：最小值）的那一個，填入「最優值」欄。
- 重複： 繼續操作，直到到達第 \(n\) 階段（你的起點）。
- 回溯： 表格完成後，從初始節點開始，依照「動作」欄位的指引，即可找出你的路徑。
6. 避免常見錯誤
- 順向工作： 除非題目明確要求（在 DM2 中這很罕見），否則請務必從目的地向起點逆向工作。
- 計算失誤： 由於 DP 是鏈式結構，在第 1 階段的一個微小加法錯誤都會摧毀之後所有的階段。務必仔細檢查你的加總！
- 搞混極大極小化與極小極大化： 記住：極小極大化 (Minimax) 是最小化一個最大值；極大極小化 (Maximin) 是最大化一個最小值。將公式寫在試卷頂端以防混亂。
- 遺漏動作： 確保表格中考慮了從某個狀態出發的所有可能路徑。
總結與重點回顧
恭喜！ 你已經掌握了動態規劃的基礎。以下是複習時需要記住的要點：
- 貝爾曼原理： 最優路徑由最優子路徑組成。
- 逆向規劃： 我們從終點往起點構建表格。
- 列表法： 精確的表格是滿分的關鍵。保持欄位整潔！
- 狀態與階段： 階段是時間/距離上的「步數」；狀態則是該步數時你「身處何處」。
繼續練習表格的排版——這是考試最常見的考察方式。你能行的！