经典中的经典算法:动态规划(详细解释,从入门到实践,逐步讲解) | 您所在的位置:网站首页 › locker动态规划 › 经典中的经典算法:动态规划(详细解释,从入门到实践,逐步讲解) |
首先,本博客为原创作品,欢迎指导,随意转载,如果可以请转载时说明出处,附上本文链接(https://blog.csdn.net/ailaojie/article/details/83014821),谢谢 首先,我们看一下官方定义: 定义: 动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。 动态规划算法的基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。 基本思想与策略编辑: 由于动态规划解决的问题多数有重叠子问题这个特点,为减少重复计算,对每一个子问题只解一次,将其不同阶段的不同状态保存在一个二维数组中。 (来自百度百科) 说实话,没有动态规划的基础很难看懂,但是也能从中看出一些信息,下面我翻译成人话: 首先是拆分问题,我的理解就是根据问题的可能性把问题划分成一步一步这样就可以通过递推或者递归来实现. 关键就是这个步骤,动态规划有一类问题就是从后往前推到,有时候我们很容易知道:如果只有一种情况时,最佳的选择应该怎么做.然后根据这个最佳选择往前一步推导,得到前一步的最佳选择 然后就是定义问题状态和状态之间的关系,我的理解是前面拆分的步骤之间的关系,用一种量化的形式表现出来,类似于高中学的推导公式,因为这种式子很容易用程序写出来,也可以说对程序比较亲和(也就是最后所说的状态转移方程式) 我们再来看定义的下面的两段,我的理解是比如我们找到最优解,我们应该讲最优解保存下来,为了往前推导时能够使用前一步的最优解,在这个过程中难免有一些相比于最优解差的解,此时我们应该放弃,只保存最优解,这样我们每一次都把最优解保存了下来,大大降低了时间复杂度 说很难理解清楚,容易懵懵懂懂的,所以下面结合实例看一下(建议结合实例,纸上谈兵不太好): 经典的数字三角形问题(简单易懂,经典动态规划);题目: 其实仔细观察,上面的解答过程时间复杂度难以想象的大,那是因为他对有的数字的解进行了多次的重复计算,具体如下图: 动规解题的一般思路(标准官方,不过经过前边讲解应该就能理解了): 将原问题分解为子问题(开头已经介绍了怎么分解) (注意:1,子问题与原问题形式相同或类似,只是问题规模变小了,从而变简单了; 2,子问题一旦求出就要保存下来,保证每个子问题只求解一遍)确定状态(状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间".我的理解就是状态就是某个问题某组变量,状态空间就是该问题的所有组变量) 另外:整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间确定一些初始状态(边界条件)的值 (这个视情况而定,千万别以为就是最简单的那个子问题解,上面只是例子,真正实践动规千变万化)确定状态转移方程 (这一步和第三步是最关键的 记住"人人为我"递推,由已知推未知)适合使用动规求解的问题: 1,问题具有最优子结构 2,无后效性 说的花里胡哨的,其实一般遇到求最优解问题一般适合使用动态规划 部分参考资料出自:北大信科郭炜老师 感觉自己洋洋洒洒写了几个小时,对动态规划有了一定的理解,也希望对你们有所帮助,动态规划千变万化,这仅仅是一个理解过程,我们还是应该多练习,共勉吧.转载的话,如果方便请加上转载地址,谢谢. |
CopyRight 2018-2019 实验室设备网 版权所有 |