关于动态规划（Dynamic Programming）的一些进阶知识

最近讨论问题时总结的一些内容，写出来分享一下..

1. 三大规划与形式系统

三大规划是指在解决组合优化问题时常用的线性规划（Linear Programming）、整数规划（Integer Programming）以及动态规划 —— 除此以外还有其他的数学规划分支，这里就不提了。而我们最早见到的应该是线性规划，高中数学中就有所涉及。

这类规划方法的特点是将现实中的问题（应用题）抽象为一组数学表达式，然后我们可以脱离应用题本身的“语义”而只针对数学表达式本身进行求解。

而每种规划所对应的数学表达式及求解方法其本质是一个数学意义上的“系统”，更本质地说是一个形式系统（Formal System），所使用的变量以及运算符及其组合方式即为该系统的形式语言（Formal Language），而求解过程可以理解为形式系统中定理的证明过程。

除了上述规划之外，多数人之前可能接触过的数学系统还有：
a) 线性方程组 —— 小学数学课程
b) (偏)微分方程组 —— 大学数学/物理课程
c) 差分方程(组) —— 数字信号处理/信号与系统课程
d) 命题逻辑/一阶谓词逻辑 —— 数理逻辑课程

这些全部都是很实用的数学系统，大量用于解决实际的工程问题。而不管是用哪种系统，解题步骤一般是两步：
(1) 设定变量，列方程
(2) 使用某种方法机械求解

而多数工程场景下，机械求解这个步骤一般由计算机完成，例如：
a) 线性方程组 —— 高斯消元法
b) 微分/差分方程组 —— 很多符号计算工具（例如Mathematica/Maple）部分可解，不过我也不知道是什么方法..
c) 一阶谓词逻辑 —— 部分可解，例如逻辑式语言Prolog所使用的SLD (Selective Linear Definite clause) resolution
d) 线性规划 —— 单纯形法
e) 整数(线性)规划 —— 总体上是NP-Hard，部分可解，有很多Solver工具

回到动态规划这个主题，那么对于可以用动态规划求解的问题，宏观上仍是上述的两步：
(1) 设定变量（用于描述状态空间），列方程（也就是状态转移方程）
(2) 机械求解

而状态转移方程本质上是一类recursive formula，其机械求解大方向上分为自底向上(Bottom-Up)和自顶向下(Top-Down)两类方法，其在学术界对应的研究领域与Datalog（逻辑式语言Prolog的近亲）关系很大。

就如同Mathematica非常适合用于表达线性方程组、微分方程等问题 —— 你只要写进去对应的数学表达式，然后按Shift+Enter就可以得到答案，并不需要自己去想具体的运算步骤 —— 也有对应的工具（语言）使我们可以很方便地描述出状态转移方程，然后具体的计算由工具自己完成，而不需要我们去写中间的运算步骤。这方面内容在下面的第3部分写。


2. 状态转移方程、(stratified) recursive formula与最优子结构

上一部分中提到了动态规划的关键步骤就是根据“应用题”写出状态转移方程，剩下的就是机械求解的搬砖活。

而状态转移方程顾名思义就是定义一个递归函数H(s)，其定义会依赖H在其他不定数量(设最大值为k)个状态d1(s), ..., dk(s)上的取值。举个最简单的斐波那契数列的例子，H(s) = H(s-1) + H(s-2)（边界条件略），那么k = 2, 其中d1(s) = s - 1，d2(s) = s - 2


现在，先不考虑时间复杂度的问题，是不是所有的可以写成递归函数的问题都可以求出解呢？当然并不是。首先状态s的取值空间必须是一个可数集(更准确地说应当是一个递归集合）—— 所以可以是高维的整数但不可以是实数类型。

然后，注意到H(s)的计算依赖于H在d1(s), ..., dk(s)上的取值。根据这一依赖关系可以构建一个有向图G，每个可能的状态s对应图中一个节点，s到每个d(s)的依赖关系对应图中一条有向边。

对于有向图来说，其一个关键的性质就是图中有没有环：
(1) 如果递归方程的参数依赖图中没有环，那么这个递归方程称作Stratified Recursive Formula，对应我们常说的状态转移方程，其具有最优子结构（Optimal Substructure)，用中文土话说叫做“无后效性”。

而要理清一个有向无环图（DAG, Directed Cyclic Graph）的依赖关系，常用方法是拓扑排序（Topology Sort）—— 而大家去观察一下自己手写动态规划求解程序时的“自顶向下”方法（也即DFS + Memoization），是不是本质上就是针对状态空间依赖图的DFS拓扑排序加上一些traverse时的额外处理。

(2) 如果有环，那么就比较麻烦了，该递归方程并没有描述最优子结构，可能有稳定解（Fixed Point Solution）、也可能有非稳态解、也可能有无穷解或者无解（类比电路中的闭环系统）。

例如最短路径问题，其实是可以描述为一个递归方程的：
ShortestPath(X, Y) = min { Edge(X, Y), ShortestPath(X, Z) + Edge(Z, Y) for all Z }

但是这个方程中有循环依赖关系，求解时并不能“一遍”就算出来，而是要反复迭代。幸运的是这个方程具有单调性(Monotonic)，也就是说一直迭代下去最后会收敛到一个不动点，就是最优解。


3. 状态转移方程的机械求解以及适合描述动态规划问题的编程语言

如果动态规划的题目多写一点的话就会发现给定状态转移方程后，“自顶向下”的机械求解其实是很套路的，如上一部分所说就是对状态依赖关系进行DFS，并Memorize中间结果就可以了。

稍微增加一点难度的话就是空间上的优化。本质上来说，对于一个中间状态节点s，我们计算完所有依赖于s的节点的值就可以“忘记“s的值了——因为以后都不会用到它了（除非要backtracking打印路径之类的）。而最早在什么时候可以忘记s取决于状态依赖图的结构。如果图的节点的依赖关系非常有规律，例如斐波那契数列、edit distance这类，我们可以通过人的domain knowledge直接用for loop来自底向上的编码出状态依赖图的拓扑序，那么就比较易于优化。如果图本质上非常随机或者sparse，那么一般是采用Top-Down的方法并很难进行有效的空间优化。

最后是动态规划的Solver。很明显C++/Java/Python这类语言并不最适合用于描述递归方程，它们也没有内置的求解引擎。与动态规划相性最符合的是上古三大范式之一的“逻辑式语言”，也即Prolog/Datalog体系。
比如Google内部就做过这么一个系统：https://pub-tools-public-publica ... s.com/pdf/43462.pdf
其主要基于这篇文章：http://www.cs.jhu.edu/~nwf/datalog20-paper.pdf

另外一个学术界的系统是XSB：https://arxiv.org/pdf/1012.5123.pdf
XSB的Tabling机制也可以很方便地描述并自动求解状态转移方程。

感谢楼主分享！

楼主实力很强劲，支持一下，让更多人看到。

其实状态转移方程就是控制理论的贝尔曼方程。

这个写的有点高深呀。