算法-动态规划

基本思想

• 将多阶段决策过程划分阶段，恰当的选取状态变量、决策变量及定义最优指标函数，从而把问题化成同一族同类型的子问题，然后逐个求解。
• 求解时从边界条件开始，逆（或顺）过程进行方向，逐段递推寻优。在每一个子问题的求解时，都要使用它前面求出的子问题最优结果，最后一个子问题的最优解，就是真个问题的最优解。
• 动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。

建立动态规划模型的要点

• 识别问题的多阶段特性，按时间或空间的先后顺序适当的划分为满足递推关系的若干阶段，对非时序的静态问题要认为的赋予“时段”概念
• 正确的选择状态变量，使其具备两个必要特征：

1. 可知性：过程演变的各阶段状态变量的取值，能直接或间接的确定
2. 能够确切的描述过程的演变且满足无后效性。即由第k阶段的状态Sk出发的后部子过程，可以看作是一个以Sk为初始状态的独立过程。这一点不是很容易满足，需要尝试把握。

• 根据状态变量与决策变量的含义，正确写出状态转移方程S(k+1) = Tk(Sk, Uk)或转移规则
• 根据题意明确指标函数V(k,n),最优指标函数Fk(Sk)以及k阶段指标Vk(Sk,Uk)的含义，并正确列出最优指标函数的递推关系及边界条件