动态规划法之最优性原理教学.doc

动态规划法之最优性原理教学.doc动态规划法之最优性原理教学摘要:最优性原理是使用动态规划法的必要条件,该原理的理解和证明是算法教学中的难点。理解该原理的关键在于识别由原问题最优解所导出的子问题。原理的证明通常采用反证法,先假设所导出的子问题的解不是最优的,进而说明可构造比原问题最优解更好的解,从而矛盾。关键词:动态规划法;最优性原理;最优子结构;多阶段决策中图分类号:G64文献标识码:A文章编号:1009-3044(2011)31- TheTeachingofOptimizationPrincipleforDynamicProgramming QINDan (ComputerScienceschoolofYangtzeUniversity,Jinzhou434023,China) Abstract:Optimizationprincipleisanecessaryconditionfordynamicprogramming,-problemexportedfromtheoriginalproblem'-problem'ssolutionis'ntthebestone,sowecanconstructabettersolutionfortheoriginalproblem. Keywords:dynamicprogram;optimizationprinciple;optimalsubstructure;multistagedecision 动态规划法由数学家贝尔曼于上世纪50年代提出[1],现已成为一种通用算法技术来求解多阶段决策最优化问题。该算法克服了分治法的缺点。分治法将问题分解成若干较小的子问题分别求解再合并。然而子问题之间往往不相互独立,其重叠部分会被计算多次。动态规划法对每个子问题只求解一次并将结果保存在表中,避免重复计算[2]。使原本用分治法需要指数时间的问题得以在多项式时间内解决。并非所有问题都适用动态规划法。只有满足最优性原理的问题才适应该方法,称最优化问题。这类问题往往在满足约束条件的前提下,通过目标函数的评价寻找最优解。最少硬币数付款问题、矩阵连乘问题、最优三角剖分问题等都是常见的经典最优化问题。0/1背包问题也在对物品价值取值离散化之后也能适用动态规划法[3]。动态规划法是传统算法手段中最有价值的一种,也是教学难度最大的一种。动态规划法是算法课程的重点。而最优性原理则是动态规划法的教学难点,是该算法教学成败的关键。 1正确理解最优性原理最优性原理又称最优子结构性质。具有该性质的问题的特征是:原问题最优解中包含其子问题的最优解。这是适用动态规划法的必要条件。理解这一条件时容易出现偏差。原问题所含的全部子问题的最优解是否都包含于原问题的解之中呢?初学者常常认为原问题的任意分解方式得到的所有子问题的最优解都包含在原问题的解中。这样的解其实不存在。学****的关键在于正确识别原问题最优解所导出的子问题,只有这些子问题的最优解