动态规划法之最优性原理教学
2011-12-31 00:00:00秦丹
电脑知识与技术 2011年31期
摘要：最优性原理是使用动态规划法的必要条件，该原理的理解和证明是算法教学中的难点。理解该原理的关键在于识别由原问题最优解所导出的子问题。原理的证明通常采用反证法，先假设所导出的子问题的解不是最优的，进而说明可构造比原问题最优解更好的解，从而矛盾。
关键词：动态规划法；最优性原理；最优子结构；多阶段决策
中图分类号：G64文献标识码：A文章编号：1009-3044(2011)31-
The Teaching of Optimization Principle for Dynamic Programming
QIN Dan
(Computer Science school of Yangtze Univers
