高考申論題
112年
[工業工程] 作業研究
第 四 題
四、考慮以下網路圖（如圖一所示），弧上數字為各弧所連結兩節點的距離，某人要從節點A以最短距離抵達節點J。請寫出此問題的動態規劃模式〔亦即此問題的最佳值函數（optimal value function）、遞迴關係式（recursive relation）以及邊界條件（boundary condition）〕。然後依此求算此問題之最佳路徑及距離。（20分）
(圖略，節點包含 A, B, C, D, E, F, G, H, I, J，目標為 A 到 J)
📝 此題為申論題
思路引導 VIP
本題為經典的最短路徑問題，需以動態規劃（Dynamic Programming）的逆向推導法求解。考生應先明確定義階段（剩餘步數）、狀態（目前節點）與決策變數，寫出最佳值函數、遞迴關係式與邊界條件，接著由終點逆推回起點，逐階計算出各節點至終點的最短距離，最終回溯找出最佳路徑。
🤖
AI 詳解
AI 專屬家教
【解題思路】利用動態規劃（Dynamic Programming）逆向推導法，將問題依「到達終點尚需經過的階段數」劃分為四個階段，建立遞迴關係式並逐階反向求解。 【詳解】 一、動態規劃模式定義
▼ 還有更多解析內容