摘要
最优性原理是使用动态规划法的必要条件,该原理的理解和证明是算法教学中的难点。理解该原理的关键在于识别由原问题最优解所导出的子问题。原理的证明通常采用反证法,先假设所导出的子问题的解不是最优的,进而说明可构造比原问题最优解更好的解,从而矛盾。
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.
作者
秦丹
QIN Dan (Computer Science School of Yangtze University, Jinzhou 434023, China)
出处
《电脑知识与技术》
2011年第11期7819-7820,共2页
Computer Knowledge and Technology
关键词
动态规划法
最优性原理
最优子结构
多阶段决策
dynamic program
optimization principle
optimal substructure
multi stage decision