Question

简述动态规划算法和分治法有什么相同点?有什么异同点

Answer 1

说明分治法与动态规划法的相同点和不同之处?解答如下：

相同点:基本思想都是将待求解问题分解成若干个子问题先求解子问题,然后从这些子问题的解得到原问题的解;

不同之处:

(1)适合于用动态规划法求解的问题,经分解得到的子问题往往不是相互独立的。若用分治法解这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要消耗指数时间;

(2)不同子问题的数目常常只有多项式量级,在用分治法求解时,有些子问题被重复计算了许多次。动态规划法保存已解决的子问题的答案,在需要时再找到已得到的答案,可以避免大量重复计算,从而得到多项式时间算法。

动态规划的概念：

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解 决策过程最优化 的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。

动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如 线性规划、非线性规划 )，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。