动态规划（Dynamic Programming）

[hiyouga]

前情提要：动态规划是个大坑…当时学C++算法时候就因为这个特别头疼…在C++里动态规划主要是实现时空权衡(Space–time tradeoff)，用来以空间复杂度换取时间复杂度上的优化，不过动态规划是在任何领域上都可以用得上的算法，而且常常比较有效。下面开始正文：

动态规划简介

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20 世纪 50 年代初 R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。

P.S.：这个创造性的技巧很重要！关键是要能考虑到如何分解问题，建立递推式，是非常关键的。

决策过程的分类

• 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程(discrete-timedecision progress)和连续时间决策过程(continuous-time decision process)。
• 根据过程的演变是确定的还是随机的，分为确定性决策过程(deterministic decision process)和随机性决策过程(stochastic decision process)，其中应用最广的是确定性多阶段决策过程。

基本概念、基本方程和计算方法

动态规划的基本概念和基本方程

一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素。

阶段

阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1, 2, … , n表示。

状态

状态(state)表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性，即当某阶段的状态变量给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。通常还要求状态是直接或间接可以观测的。
描述状态的变量称状态变量(state variable)。变量允许取值的范围称允许状态集合(set of admissible states)。用\(x_k\)表示第k阶段的状态变量，它可以是一个数或一个向量。用\(X_k\)表示第k阶段的允许状态集合。
n个阶段的决策过程有n+1个状态变量，\(x_{n+1}\)表示\(x_n\)演变的结果。根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算方便有时将连续变量离散化，为了分析的方便有时又将离散变量视为连续的。
状态变量简称为状态。

决策

当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision)，在最优控制问题中也称为控制(control)。
描述决策的变量称为决策变量(decision variable)，变量允许取值的范围称允许决策集合(set of admissible decisions)。用\(u_k(x_k)\)表示第k阶段处于状态\(x_k\)时的决策变量，它是\(x_k\)的函数，用\(U_k(x_k)\)表示\(x_k\)的允许决策集合。
决策变量简称为决策。

策略

决策组成的序列称为策略(policy)。由初始状态\(x_1\)开始的全过程的策略记作\(p_{1n}(x_1)\)，即：
$$p_{1n}(x_1)=\{u_1(x_1), u_2(x_2), \cdots, u_n(x_n)\}$$
由第k阶段的状态\(x_k\)开始到终止状态的后部子过程的策略记作\(p_{kn}(x_k)\)，即：
$$p_{kn}(x_k)=\{u_k(x_k), \cdots, u_n(x_n)\}, k=1, 2, \cdots, n-1$$
类似地，由第k到第j阶段的子过程的策略记作：
$$p_{kj}(x_k)=\{u_k(x_k), \cdots, u_j(x_j)\}$$
可供选择的策略有一定的范围，称为允许策略集合(set of admissible policies)，用\(P_{1n}(x_1), P_{kn}(x_k), P_{kj}(x_k)\)表示。

状态转移方程

在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equation of state transition)表示这种演变规律，写作：
$$x_{k+1}=T_k(x_k, u_k), k=1, 2, \cdots, n$$

指标函数和最优值函数

指标函数(objective function)是衡量过程优劣的数量指标，它是定义在全过程和所有后部子过程上的数量函数，用\(V_{k,n}(x_k, u_k, x_{k+1}, \cdots, x_{n+1})\)表示，k=1, 2, … , n。指标函数应具有可分离性

[Myriad-Dreamin]

太强了，看都看不懂。果然大佬始终是大佬。

[hiyouga]

@Myriad-Dreamin
DP大佬说笑了= =看大佬卖弱真好玩