动态规划算法的基本步骤

pk_001

动态规划算法的基本步骤

设计一个标准的动态规划算法，通常可按以下几个步骤进行：

划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。
动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：

标准动态规划的基本框架

1. 对fn+1(xn+1)初始化; {边界条件}
2. for k:=n downto 1 do
3. for 每一个xk∈Xk do
4. for 每一个uk∈Uk(xk) do
begin
5. fk(xk):=一个极值; {∞或－∞}
6. xk+1:=Tk(xk,uk); {状态转移方程}
7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}
8. if t比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值}
end;
9. t:=一个极值; {∞或－∞}
10. for 每一个x1∈X1 do
11. if f1(x1)比t更优 then t:=f1(x1); {按照10式求出最优指标}
12. 输出t;
但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：

分析最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
根据计算最优值时得到的信息，构造一个最优解。
步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。