【算法设计与分析】动态规划-基本概念

【历史延伸】

动态规划(Dynamic Programming)是运筹学的一个分支, 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(Multistep Decision Process)的优化问题时, 提出了著名的最优性原理, 把多阶段过程转

化为一系列单阶段问题, 逐个求解, 创立了解决这类过程优化问题的新方法——动态规划.

多阶段决策问题: 求解的问题可以划分为一系列相互联系的阶段, 在每个阶段都需要做出决策, 且一个阶段决策的选择会影响下一个阶段的决策, 从而影响整个过程的活动路线, 求解的目标是选择各个阶段的决策使整个过程达到最优.

动态规划主要用于求解以时间划分阶段的动态过程的优化问题.

但是对于一些与时间无关的静态规划(如线性规划、非线性规划), 也可以人为地引进时间因素, 把它视为多阶段决策过程,从而可以用动态规划方法方便地求解.

动态规划是考察问题的一种途径, 或是求解某类问题的一种方法.

动态规划问世以来, 在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用.

例如：最短路线、库存管理、资源分配、设备更新、排序、装载等问题, 用动态规划方法比其它方法求解更为方便.

【基本概念】

①状态: 

    表示每个阶段开始时, 问题或系统所处的客观状况. 状态既是该阶段的某个起点, 又是前一个阶段的某个终点. 通常一个阶段有若干个状态.

状态无后效性: 

    如果某个阶段状态给定后, 则该阶段以后过程的发展不受该阶段以前各阶段状态的影响, 也就是说状态具有马尔科夫性.

适于动态规划法求解的问题具有状态的无后效性.

② 策略: 各个阶段决策确定后, 就组成了一个决策

序列, 该序列称之为一个策略.

由某个阶段开始到终止阶段的过程称为子过程, 其对应的某个策略称为子策略.

【最优性原理 – Bellman最优性原理】

求解问题的一个最优策略序列的子策略序列总是最优的，则称该问题满足最优性原理。

注: 对具有最优性原理性质的问题而言, 如果有一决策序列包含有非最优的决策子序列, 则该决策序列一定不是最优的.

【核心思想】

动态规划的思想实质是分治思想和解决冗余.

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题.

但是经分解得到的子问题往往不是互相独立的. 不同子问题的数目常常只有多项式量级. 在用分治法求解时, 有些子问题被重复计算了许多次.

如果能够保存已解决的子问题的答案, 而在需要时再找出已求得的答案, 就可以避免大量重复计算,从而得到多项式时间算法.

【基本步骤】

① 找出最优解的性质, 并刻划其结构特征.

② 递归地划分子问题, 递归地定义最优值, 给出最优解的递归式.

③ 以自底向上的方式计算出最优值.

④ 根据计算最优值时得到的信息, 构造最优解.

ps.

步骤①~③是动态规划算法的基本步骤。如果只需要求出最优值的情形，步骤④可以省略；

若需要求出问题的一个最优解，则必须执行步骤④，步骤③中记录的信息是构造最优解的基础；

【参考文献】

• 2019年广西师范大学计算机与信息工程学院算法设计与分析课件[OL].李志欣教授.2019.01.01