认识达内从这里开始

认真做教育专心促就业

武汉达内培训动态规划算法原理分析与应用

发布：武汉IT培训
来源：互联网
时间：2022-02-27 13:11

算法是程序员需要重点掌握的一个编程开发知识点，下面我们就通过案例分析来了解一下，动态规划算法原理分析与应用。

武汉达内培训动态规划算法原理分析与应用

和分治法一样，动态规划解决复杂问题的思路也是先对问题进行分解，然后通过求解小规模的子问题再反推出原问题的结果。但是动态规划分解子问题不是简单地按照“大事化小”的方式进行的，而是沿着决策的阶段来划分子问题，决策的阶段可以随时间划分，也可以随着问题的演化状态来划分。分治法要求子问题是互相独立的，以便分别求解并终合并出原始问题的解。分治法对所有的子问题都“一视同仁”地进行计算求解，如果分解的子问题中存在相同子问题，就会存在重复求解子问题的情况。

比如某个问题A，一次分解为A1和A2两个子问题，A1又可分解为A11和A12两个子问题，A2又分解为A21和A22两个子问题，分治法会分别求解A11、A12、A21和A22四个子问题，即便A12和A21是相同的子问题，分治法也依然会计算四次子问题的解，这就存在重复计算的问题，重复计算相同的子问题会影响求解的效率。

与之相反，动态规划法的子问题不是互相独立的，子问题之间通常有包含关系，甚至两个子问题可以包含相同的子子问题。比如，子问题A的解可能由子问题C的解递推得到，同时，子问题B的解也可能由子问题C的解递推得到。对于这种情况，动态规划法对子问题C只求解一次，然后将其结果保存在一张表中(此表也被称为备忘录)。当求解子问题A或子问题B的时候，如果发现子问题C已经求解过(在备忘录表中能查到)，则不再求解子问题C，而是直接使用从表中查到的子问题C的解，避免了子问题C被重复计算求解的问题。

动态规划法不像贪婪法或分治法那样有固定的算法实现模式，线性规划问题和区间动态规划问题的实现方法就完全不同。作为解决多阶段决策优化问题的一种思想，可以用带备忘录的穷举方法实现，也可以根据堆叠子问题之间的递推公式用递推的方法实现。但是从算法设计的角度分析，使用动态规划法一般需要四个步骤，分别是：

定义优子问题(优解的子结构)

定义状态(优解的值)

定义决策和状态转换方程(定义计算优解的值的方法)

确定边界条件

这四个问题解决了，算法也就确定了。

【免责声明】：本内容转载于网络，转载目的在于传递信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。更多内容请加danei0707学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。

< 上一篇：武汉达内培训软件编程算法基础知识

下一篇：武汉达内java培训大数据分析工具都有哪些需求 >