文档介绍：动态规划法之最优性原理教学
摘要:最优性原理是使用动态规划法的必要条件,该原理的理解和证明是算法教学中的难点。理解该原理的关键在于识别由原问题最优解所导出的子问题。原理的证明通常采用反证法,先假设所导出的子问题的解不是最优的,进而说明可构造比原问题最优解更好的解,从而矛盾。
关键词:动态规划法;最优性原理;最优子结构;多阶段决策
中图分类号:G64文献标识码:A文章编号:1009-3044(2011)31-
The Teaching of Optimization Principle for Dynamic Programming
QIN Dan
(Computer Science school of Yangtze University, Jinzhou 434023, China)
Abstract: Optimization principle is a necessary condition for dynamic programming, It is a hard task that understand and prove the principle in algorithm teaching. It is the key that distinguishing the sub-problem exported from the original problem's best solution. It usually proves the principle by reduction to absurdly. Assuming the sub-problem's solution is'nt the best one, so we can construct a better solution for the original problem.
Key words: dynamic program; optimization principle; optimal substructure; multi stage decision
动态规划法由数学家贝尔曼于上世纪50年代提出[1],现已成为一种通用算法技术来求解多阶段决策最优化问题。该算法克服了分治法的缺点。分治法将问题分解成若干较小的子问题分别求解再合并。然而子问题之间往往不相互独立,其重叠部分会被计算多次。动态规划法对每个子问题只求解一次并将结果保存在表中,避免重复计算[2]。使原本用分治法需要指数时间的问题得以在多项式时间内解决。
并非所有问题都适用动态规划法。只有满足最优性原理的问题才适应该方法,称最优化问题。这类问题往往在满足约束条件的前提下,通过目标函数的评价寻找最优解。最少硬币数付款问题、矩阵连乘问题、最优三角剖分问题等都是常见的经典最优化问题。0/1背包问题也在对物品价值取值离散化之后也能适用动态规划法[3]。动态规划法是传统算法手段中最有价值的一种,也是教学难度最大的一种。动态规划法是算法课程的重点。而最优性原理则是动态规划法的教学难点,是该算法教学成败的关键。
1 正确理解最优性原理
最优性原理又称最优子结构性质。具有该性质的问题的特征是:原问题最优解中包含其子问题的最优解。这是适用动态规划法的必