动态规划

动态规划（也称为动态优化），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划将复杂的问题分解成一系列相对简单的子问题，只解决一次子问题并存储它的解决方案（solution），下一次遇到同样的子问题时无需重新计算它的解决方案，而是简单地查找先前计算的解决方案，从而节省计算时间。动态规划适用于有最优子结构（Optimal Substructure）和重叠子问题（Overlapping Subproblems）性质的问题。

最优子结构是指可以通过将最优解与子问题相结合来获得给定优化问题的解，这种最优子结构通常通过递归（recursion）来描述。例如，使用最优子结构在图中找出从start到goal的最短路径，一条直线表示一条边，波浪线表示它所连接的两个顶点之间的最短路径（这些路径上的其他节点未示出），粗线是从开始到目标的整体最短路径。

重叠子问题意味着子问题的空间必须很小，即任何给出问题解的递归算法都应该一次又一次地解决同样的子问题，而不是产生新的子问题。常见的斐波那契数列（Fibonacci Series）就属于重叠子问题范畴。

来源：

Wikipedia: https://en.wikipedia.org/wiki/Dynamic_programming

发展历史

动态规划这个术语最早是在1940s由理查德·贝尔曼（Richard Bellman）提出，用来描述解决多级决策问题（multistage decision process problems）的一个过程，在这个过程中，人们需要一次接一次地找出最佳的决策。到1953年，Bellman改进了动态规划地定义，特别指在较大的决策中嵌套较小的决策问题，此后该领域被IEEE认定为系统分析（systems analysis）和工程主题（engineering topic）。动态一词被Bellman选中用来捕捉问题的时间变化方面， 而规划一词指的是使用这种方法来寻找一个最佳方案。人们通过命名贝尔曼方程（Bellman Equation）的方式来纪念Bellman的贡献，贝尔曼方程是动态规划的核心算法，它以递归形式重新描述了优化问题。

起初，动态规划（dynamic programming）中的programming一词与计算机编程没有任何关系，而是来自于术语数学规划（mathematical programming），是优化的代名词。而现在许多优化问题是通过编写一个计算机程序来实现动态规划算法从而求出问题的解，而不是单纯地进行繁琐的计算。

就数学优化（mathematical optimization）而言，动态规划通常是指通过将决策分解为一系列子决策步骤来简化决策。这是通过定义一系列值函数V1，V2，...，Vn来完成的，参数y代表系统在时间i从1到n的状态。 Vn（y）的定义是在状态y在最后时刻n获得的值。在时间i = n-1，n-2，...，2，1中的值Vi可以通过使用称为Bellman方程的递归关系向后运算得到。对于i = 2，...，n，在任意状态y下的Vi-1是通过最大化在时间i-1处决策获得的增益，以及如果做出这个决策系统达到的新的状态Vi的简单函数（通常是求和）。由于Vi是已计算数值，所以上述操作可计算出Vi-1。一直迭代下去，系统初始状态下的V1是最优解的值。通过跟踪已经执行的计算，可以逐个恢复决策变量的最优值。

动态规划在生物信息学（bioinformatics）中被广泛用于序列比对（sequence alignment），蛋白质折叠（protein folding），RNA结构预测（RNA structure prediction）和蛋白质-DNA结合（protein-DNA binding）等任务。20世纪70年代，来自美国的Charles Delisi和来自前苏联的Georgi Gurskii与Alexander Zasedatelev最早将动态规划算法用于蛋白质-DNA结合的研究中，近些年来，这些算法在生物信息学和计算生物学中变得非常流行，特别是在核小体定位（nucleosome positioning）和转录因子结合（transcription factor binding）的研究中。

主要事件

发展分析

瓶颈

-动态规划算法适用于任何满足最优性原则（principle of optimality）的问题，但受限于维度诅咒，只适用于低维度的优化问题。

未来发展方向

-由于动态规划算法的收敛性，随着计算机运算力的不断提高，动态规划将更多地应用在需要实时决策的智能设备上。

Contributor: Yufeng XIong