动态规划算法设计

IT商界

PALADIN

　　上期的有奖问答是关于求最长公共子序列题目的解答，用到了动态规划的思想。本期我想结合最长子序列问题和大家探讨一下动态规划算法的设计思想。

　　动态规划的基本思想就是将求解的问题一层一层地分解成一级一级的，把子问题的求解由繁到简分解而逐步缩小，直到可以直接求出子问题的解为止。原问题的解依赖于所有子问题的解。实际求解过程中，子问题会有大量的重复，而动态规划相应的特点就是对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

　　动态规划算法通常用于求一个问题在某种条件下的最优解。它主要应用于如上期的最长公共子序列问题，还有图像压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等问题。

　　那么我们怎么判断是否可以使用动态规划来解决问题呢？一般来说，只要某个问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理)，则可以考虑用动态规划解决。举个最简单的例子来说明一下什么是最优子化原理。如有三个城市A、B、C，其中A和B之间只有一条路I1，B、C间有两条路I2、I3，A、C间没有直接连接的路。如果A到C最短的路径是(I1、I2)，那么I2一定首先是B、C间的最短路径。而求最长公共子序列的问题时，我们经过分析得出了“两个序列的最长公共子序列包含了这两个序列的前缀的两个序列的最长公共子序列”的结论，这也就是满足了最优化的原理，所以可以用动态规划算法来解决问题。

　　设计一个动态规划算法，通常可以按以下几个步骤来进行：

　　1.分析最优解的性质，并刻划其结构特征。

　　2.递归的定义最优值。

　　3.以自底向上的方式的记忆化方法(备忘录法)计算出最优值。

　　4.根据计算最优值时得到的信息，构造一个最优解。

　　步骤1～3是动态规划算法的基本步骤。在只需要求出最优值的情形下，步骤4可以省略，若需要求出问题的一个最优解，则必须执行步骤4。此时，在步骤3中计算最优值时，通常须记录更多的信息，以便在步骤4中，根据所记录的信息，快速地构造出一个最优解。

　　下面不细说了，你可以结合我们提供的上期问题的精选解答，来细细体味动态规划的方法。(http://paladin.nease.net/cpcw/lcs.zip)

　　本期有奖问答的题目是：

　　若由两个人A、B承担N个作业的任务。设第i个作业交给A处理时需要的时间为ai，而交给B处理，则需要时间bi。由于各作业的特点和各人擅长的技能不同的关系，很可能对于某些i，有ai≥bi，而对于某些j，j≠i，有aj＜bj。既不能将一个作业分开由两个人处理，也没有一个人能同时处理两个作业。设计一个算法，使得这两个人处理完这N个作业的时间最短(从任何一个人开工到最后一个人停工的总时间)。研究一个实例：(a1,a2,a3,a4,a5,a6,a7)=(2,8,9,11,4,5,7)；(b1,b2,b3,b4,b5,b6,b7)=(4,5,12,10,3,4,8)。

　　读者朋友可以用你最擅长的语言和编程工具来完成这道题，答题方式为：把你的答案发送到software@cpcw.com，邮件主题写上“算法演义答题”。我们会从中选取答题最好的参赛者，并发送精美奖品。