【路径规划】基于matlab动态规划法最短路径规划【含Matlab源码 487期】

动态规划适合与解决最优问题，求最大值最小值等，可以显著降低时间复杂度。

1 动态规划算法思想：

一个模型： 多阶段决策最优解模型。

三个特征：

最优子结构：文图的最优解包含子问题的最优解；

无后效性：推导后面阶段的状态时，只关心前面阶段的状态值，不关心状态时怎么来的，某阶段的状态决定之后不受之后阶段状态的影响。

重复子问题：不同的决策序列，到达某个相同的阶段可能会产生重复的状态。

解决动态规划问题的解题总结：

状态转移表法： 将解决问题转化成状态表，分阶段填充状态表的每个状态。

解题思路：回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。

状态转移方程法： 某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程，代码的实现可以用递归加“备忘录”或者是迭代递推。

大致思路可以概括为，找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。

0-1背包问题：

回溯算法的思路：

穷举搜索所有可能的装法，然后找出满足条件的最大值。当计算有重复的时候采用“备忘录”的方法记录已经计算好的值，就可以避免冗余计算。

2 动态规划解决思路：

将问题分解为多个阶段，每个阶段对应一个决策。我们记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

贪心，分治，回溯，动态规划算法的比较：

贪心算法： 是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性；

分治算法： 解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型；

回溯算法： 相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了；

动态规划： 比回溯算法高效，需要满足三个特征，最优子结构、无后效性和重复子问题。分治算法不能有重复的子问题，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。

1 matlab版本

2014a

2 参考文献

[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）[M].电子工业出版社，2016.

[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社，2017.