目錄
- 1 多階段決策和最優化原理
- 1.1 用遞推法求最短路
- 1.2 資源分配問題
- 1.3 前向優化和后向優化
- 2 定期多階段決策問題
- 2.1 背包問題
- 2.2 最長公共子序列問題
- 2.3 旅行售貨員問題
- 3 不定期多階段決策問題
- 3.1 一般圖上的最短路問題
- 3.2 單匯點最短路問題
- 4 連續變數的多階段決策問題
- 4.1 資源分配問題
1 多階段決策和最優化原理
- 對于此類問題有明顯的階段性，即系統可以分為若干個階段，每個階段系統有一個狀態，如第k個階段狀態為\(x_k\),每個狀態都有一個決策集合\(Q_k(x_k)\),我們在其中選擇一個 \(q_k \in Q_k(x_k)\)，則狀態由\(x_k\)轉移到\(x_{k+1}=T_k(x_k,q_k)\)，并得到收益\(R_k(x_k,q_k)\),系統的目標是在每個階段選擇一個收益，使得所有階段的總收益達到最大，
1.1 用遞推法求最短路
- 問題描述
- 問題求解
定義\(f_k(u,g)\)為從\(u\)經過\(k\)條邊走到\(g\)的最短路長度，則有如下迭代關系，原問題轉化為求\(f_n(a,g)\),其中\(a\)是起點，\(g\)是終點，\(n\)是階段數，
1.2 資源分配問題
- 問題描述
- 問題求解
設\(f_k(x)\)表示當前資源總量為\(k\)再經過\(k\)個階段投放完成目標可以得到的最大收益，則有下列迭代關系，原問題即求\(f_n(x)\)
1.3 前向優化和后向優化
- 前邊的兩個問題都是后向優化思想，即在建模的時候就采用還剩kge階段到達最終狀態的最優解，則在迭代程序中已知后k個階段的最優解，自然可以推后k+1個階段的最優解，一直向前推，最后得到經過n個階段到達最終狀態的最優解，
- 前向優化思想與后向優化思想正好相反，它是已知前k個決策，在此基礎上推出第k+1個決策，最終到達最終狀態，
- 資源分配問題的前向優化解法涉及到解方程組，復雜，這里不在展開，網上應該能搜到，
2 定期多階段決策問題
2.1 背包問題
- 問題描述
- 問題求解
- 時間復雜度：\(O(nW)\)，這個時間復雜度不是多項式的，原因在于W是問題輸入中的一個整數，
2.2 最長公共子序列問題
- 問題描述
- 問題求解
- 時間復雜度： 以上動態規劃法（LCS問題）的時間復雜度為\(O(mn)\)，這是一個多項式的時間復雜度，表明LCS問題是多項式時間可解的，
2.3 旅行售貨員問題
- 問題描述
- 問題求解
- 舉例
- 復雜度
3 不定期多階段決策問題
3.1 一般圖上的最短路問題
- 動態規劃法
- Flody-Warshall演算法
3.2 單匯點最短路問題
- 函式空間迭代法
- 策略空間迭代法
- 例子
4 連續變數的多階段決策問題
4.1 資源分配問題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/288899.html
標籤：其他
上一篇：C語言——簡單的走迷宮小游戲（無指標，無鏈表,無......!!!）
下一篇：分享一款好玩的工具