自从DeepMind使用增强学习(Reincorcement Learning)方法使得人工智能不需要知道游戏规则，只需要根据游戏屏幕画面的截图的大量训练数据就能玩各种游戏，特别是ALphGO战胜世界围棋冠军李世石、柯后，吸引了世界目光，从国家政府到企业界都开始对人工智能投入巨资，希望尽快占领人工智能研究和应用的制高点。
我们将不定期介绍增强学习的一些基础关键技术的原理、算法。
动态规划(Dynamic programming)既是一个数学优化(mathematical optimization)也是一个计算机编程(computer programming)方法。它指的是将一个复杂的文件以递归方式简化为一系列更简单的子问题。跨越多个时间点的决策问题通常都可以这样递归地分解。 Bellman称之为”最优化原理”(Principle of Optimality)。而在计算机科学中，一个优化问题的求解能被递归的分解为一系列优化子问题的求解，被称之为”优化子结构”(optimal substructure).
数学优化(mathematical optimization)观点
动态规划(Dynamic programming)是指将一个决策问题分解为时间上的一系列决策步骤. 通过定义时间上的一系列值函数(value functions): V1, V2, …, Vn,其中vi表示对应时间i的状态(State)值函数。早期时间上的值函数可通过后续时间的状态值函数根据一个叫做“Bellman方程(Bellman equation)”递归关系，用“反向传导”(backward induction)方式进行更新。比如状态Vi-1通过状态Vi来更新。
计算机编程(computer programming)观点
能够用动态规划(Dynamic programming)求解的问题通常有2个属性：优化子结构(optimal substructure)和重叠子问题(overlapping sub-problems).如果一个问题的解是通过组合“不重叠”子问题(non-overlapping sub-problems)的解得到的，这叫做“分治法”(divide and conquer)而不是动态规划。如快速排序(merge sort)和合并排序(quick sort)。
优化子结构(Optimal substructure)就是说一个问题的最优解可以通过子问题的最优解组合得到。这种“优化子结构”一般用递归形式描述。例如，给定一个图G(V,E)，其中任意两个顶点u,v的最短路径p上有一定顶点w,如果p是最短路径，那么它分解的2个从u到w的路径p1和w到v的路径p2也必定分别是u到w的最短路径和w到v的最短路径。 也就是说求u到v的最短路径问题就归结为求u到w的最短路径和求w到v的最短路径。这种递归求解最短路径的方法就是著名的 Bellman–Ford 算法或 Floyd–Warshall算法。
重叠子问题(Overlapping sub-problems)意味着子问题的空间是小的，递归算法是通过不断的一遍又一遍地求解这些子问题得到原问题的最优解，而不是不断产生新的子问题。比如计算Fibonacci 序列: Fi = Fi−1 + Fi−2。其基情形(base case F1 = F2 = 1.) .那么我们可以这样来计算：F43 = F42 + F41, F42 = F41 + F40.在计算F43,F42时都会用到F41。
即使子问题的数目是少的，但如果采用普通的递归算法，就会不断重新计算子问题如F41。动态规划可以充分利用这种特点，使得每个子问题只计算1次。 如图所示：
-
自顶向下方法Top-down approach
用递归方式将一个大问题分解为子问题，如果一个子问题的解已经存在在一个表里，则直接拿来用，如果没有则继续递归。一个问题一旦求解就存储起来（比如放在一个表里）
-
自底向上方法Bottom-up approach
先求解子问题，然后求解更大的问题，例如先求解F41 和 F40, 然后求F42
例1： Dynamic Programming – From Novice to Advanced
更多视频课程讲解请关注后续博客通知
支付宝打赏
微信打赏
您的打赏是对我最大的鼓励！
