【路徑規劃】基于matlab動态規劃法最短路徑規劃【含Matlab源碼 487期】

動态規劃适合與解決最優問題，求最大值最小值等，可以顯著降低時間複雜度。

1 動态規劃算法思想：

一個模型： 多階段決策最優解模型。

三個特征：

最優子結構：文圖的最優解包含子問題的最優解；

無後效性：推導後面階段的狀态時，隻關心前面階段的狀态值，不關心狀态時怎麼來的，某階段的狀态決定之後不受之後階段狀态的影響。

重複子問題：不同的決策序列，到達某個相同的階段可能會産生重複的狀态。

解決動态規劃問題的解題總結：

狀态轉移表法： 将解決問題轉化成狀态表，分階段填充狀态表的每個狀态。

解題思路：回溯算法實作 - 定義狀态 - 畫遞歸樹 - 找重複子問題 - 畫狀态轉移表 - 根據遞推關系填表 - 将填表過程翻譯成代碼。

狀态轉移方程法： 某個問題如何通過子問題來遞歸求解，也就是所謂的最優子結構。根據最優子結構，寫出遞歸公式，也就是所謂的狀态轉移方程，代碼的實作可以用遞歸加“備忘錄”或者是疊代遞推。

大緻思路可以概括為，找最優子結構 - 寫狀态轉移方程 - 将狀态轉移方程翻譯成代碼。

0-1背包問題：

回溯算法的思路：

窮舉搜尋所有可能的裝法，然後找出滿足條件的最大值。當計算有重複的時候采用“備忘錄”的方法記錄已經計算好的值，就可以避免備援計算。

2 動态規劃解決思路：

将問題分解為多個階段，每個階段對應一個決策。我們記錄每一個階段可達的狀态集合（去掉重複的），然後通過目前階段的狀态集合，來推導下一個階段的狀态集合，動态地往前推進。

貪心，分治，回溯，動态規劃算法的比較：

貪心算法： 是動态規劃算法的一種特殊情況。它解決問題起來更加高效，代碼實作也更加簡潔。不過，它可以解決的問題也更加有限。它能解決的問題需要滿足三個條件，最優子結構、無後效性和貪心選擇性；

分治算法： 解決的問題盡管大部分也是最優解問題，但是，大部分都不能抽象成多階段決策模型；

回溯算法： 相當于窮舉搜尋。窮舉所有的情況，然後對比得到最優解。不過，回溯算法的時間複雜度非常高，是指數級别的，隻能用來解決小規模資料的問題。對于大規模資料的問題，用回溯算法解決的執行效率就很低了；

動态規劃： 比回溯算法高效，需要滿足三個特征，最優子結構、無後效性和重複子問題。分治算法不能有重複的子問題，動态規劃之是以高效，就是因為回溯算法實作中存在大量的重複子問題。

1 matlab版本

2014a

2 參考文獻

[1] 包子陽,餘繼周,楊杉.智能優化算法及其MATLAB執行個體（第2版）[M].電子工業出版社，2016.

[2]張岩,吳水根.MATLAB優化算法源代碼[M].清華大學出版社，2017.