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

摘要：最优性原理是使用动态规划法的必要条件，该原理的理解和证明是算法教学中的难点。理解该原理的关键在于识别由原问题最优解所导出的子问题。原理的证明通常采用反证法，先假设所导出的子问题的解不是最优的，进而说明可构造比原问题最优解更好的解，从而矛盾。

关键词：动态规划法；最优性原理；最优子结构；多阶段决策

中图分类号：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 正确理解最优性原理

最优性原理又称最优子结构性质。具有该性质的问题的特征是：原问题最优解中包含其子问题的最优解。这是适用动态规划法的必要条件。理解这一条件时容易出现偏差。原问题所含的全部子问题的最优解是否都包含于原问题的解之中呢？初学者常常认为原问题的任意分解方式得到的所有子问题的最优解都包含在原问题的解中。这样的解其实不存在。学习的关键在于正确识别原问题最优解所导出的子问题，只有这些子问题的最优解才包含在原问题最优解之中。以下用矩阵连乘问题[4]为例分析。

x行y列的矩阵与y行z列矩阵相乘，需进行x*y*z次乘法运算。给定n个矩阵M1 M2 … Mn，其中相邻矩阵可乘。矩阵乘法满足结合律，所以n个矩阵连乘有多种运算次序，希望找到一种最佳次序，使总计算量最小。设有四个矩阵A，B，C，D连乘。

错误的理解方式为：原问题是ABCD，其子问题有九个，分别是A、B、C、D、AB、BC、CD、ABC、BCD、ABCD。

其实特定运算次序只包含部分子问题，而不是包含所有潜在的子问题。初学者按照错误的方式去分析将不能识别最优化问题。正确的理解方式为：由原问题最优解导出若干子问题，只有这些子问题的最优解包含在原问题的最优解之中。原问题为ABCD，运算次序不同则该问题包含的子问题不同。用括弧确定运算次序。如A((BC)D)表示先由BC相乘，结果再与D相乘，最后由A与之相乘。这一过程仅有六个子问题，它们是A、B、C、BC、BCD、ABCD。若这一运算次序是原问题的最优解，那么其中BCD的最优解为(BC)D，而不是B(CD)。

学生常陷入错误理解。既然连最优性原理都不能理解，就更谈不上其证明，所以会感到动态规划法特别难。即使通过模仿掌握少量特定问题的动态规划法求解过程，也难举一反三。需要经过很长时间才能学会动态规划法。教学中教师应注意及时引导学生采取正确的理解方式，从而提高学习效率，也能帮助学生减少畏难情绪。

2 最优性原理的证明

矩阵连乘问题有着大量不同的运算次序，穷举检验各次序所包含的子问题是否取得最优解是不现实的。而证明某问题符合最优性原理是运用动态规划法的关键。其证明常用反证法[5]。先假设由问题的最优解导出的子问题的解不是最优的，然后设法说明此时可以构造比原问题最优解更好的解，从而矛盾。

将矩阵连乘积Mi Mi+1 … Mk简记为M[i:k]，i≤k。设M[i:k]的最优计算次序在j处断开，i≤j

证明：用反证法。假设原问题最优解所包含的(M1M2Mj)和(Mj+1Mj+2Mk)的计算次序并非它们的最优次序。那么必有更优的M[i:j]或M[j+1:k]。以二者合并可得M[i:k]，使得新解优于所谓的原问题最优解。矛盾。原理得证。

3 自底向上的递推求解

最优性原理保证了能够通过合并子小问题最优解得到更大问题的最优解。因此可以用自底向上的方式求解。先求解最小的各种子问题的最优解，再逐步将小问题合并为更大的问题，直到求解出待解问题为止。为了能实现解的合并，常需建立递推式。矩阵连乘例子中设Ai有Wi-1行Wi列。计算A[i:k]（1≤i≤k≤n）所需要的最少数乘次数c[i,k]，则原问题的最优值为c[1,n]。i=k时，A[i:k]=Aj，c[i,i]=0，i

最优化问题常常是从子问题的组合中选优作为更大规模问题的解，这就是所谓的合并过程。但是也特殊情况下，合并过程无需选优。例如自底向上求解斐波那契数列F(n)。F(n)= F(n-1)+ F(n-2)。教学时应向学生解释这些合并方式的特点。并举出多个例子来强化，斐波那契数列、还有三角剖分、TSP等问题都是鲜明的例子。

设有4个矩阵其维数分别为A1=4*2，A2=2*3，A3=3*5，A4=5*1。利用表格记录各子问题的最优解，避免重复计算。该问题的的最优解为A1(A2(A3A4))，共需29次乘法运算。

图1 计算次序

表1 c[i,k]

表2 M[i,k]的断开位置

4 教学效果分析

教学中注重发现学生对最优性原理的错误认识，及时引导其正确思考，加快了学生对动态规划法的掌握，在有限时间内能学习更多的例子，掌握的程度也比改进教学之前大为提高。

参考文献：

[1] 秦裕瑗.Bellman最优性原理[J].应用数学,1994(7).

[2] 王红梅.算法设计与分析[M].北京:清华大学出版社,2006.

[3] 孙红丽.背包问题的算法设计与分析研究[J].电脑知识与技术,2008(9).

[4] 王晓东.算法设计与分析(第3版)[M].北京:清华大学出版社,2010.

[5] 赵鹏起,姜春艳.最优性原理及方法的进一步研究[J].佳木斯大学学报,2002(6).

收稿日期：2011-09-21

作者简介：秦丹，长江大学计算机学院讲师，硕士，研究方向为数据挖掘。