文档介绍：《算法设计与分析》结课作业- 1- 动态规划和分治算法一样,动态规划(dynamic programming) 是通过组合子问题的解而解决整个问题的。从第 2章已经知道,分治算法是指将整个问题划分成一些独立的子问题,递归地求解各子问题,然后合并子问题的解而得到原问题的解。与此不同,动态规划使用于子问题不是独立的情况,也就是各子问题包含公共的子子问题。在这种情况下,若用分治法则会做许多不必要的工作,及重复的求解公共的子子问题。动态规划算法对每个子子问题只求解一次,将其结果保存在一张表中,从而避免每次遇到各个子问题时重新计算答案。动态规划通常应用于最优化问题。此类问题可能有很多种可行解。每个解有一个值, 而我们希望找出一个具有最优( 最大或最小) 值的解。称这样的解为该问题的“一个”最优解(而不是“确定”的最优解),因为可能存在多个取最优值的解。动态规划算法的设计可以分为如下 4个步骤: 1)描述最优解的结构。 2)递归定义最优解的值。 3)按自底向上的方式计算最优解的值。 4)由计算出的结果构造一个最优解。第 1~3 步构成问题的动态规划解的基础。第 4步在只要求计算最优解的值时可以略去。如果的确做了第 4步,则有时要在第 3步的计算中记录一些最优化问题,使构造一个最优解变得容易。接下来的各节利用动态规划方法来求解一些最优化问题。 节分析包括两个汽车装配线的调度问题,在经过每个装配站后,组装中的汽车可以留在同一条装配线上,或者移动到另外一条装配线。 节讨论如何做一连串的矩阵乘法,使得所作的标量乘法总次数最少。在给出这些动态规划的例子之后, 节讨论为使动态规划成为可行的求解技术,一个问题必须具备的两个关键特征。然后, 节介绍如何找出两个序列的最长公共子序列。最后, 节介绍在已知待搜索的关键字分布的情况下,如何利用动态规划构造最优的二叉查找树。 装配线调度第一个动态规划的例子是求解一个制造问题。 Colonel 汽车公司在有两条装配线的工厂内生产汽车,如图 15-1 所示。一个汽车底盘在进入每一条装配线后,在一些装配站中会在底盘上安装部件,然后,完成的汽车在装配线的末端离开。每一条装配线上有 n 个装配站,编号为 j =1 ,2,…,n 。将装配线 i(i为1或2)的第 j 个装配站表示为 jiS ,。装配线 1的第 j个站( jS ,1)和装配线 2的第 j个站( jS ,2)执行相同的功能。然而,这些装配站是在不同的时间建造的,并且采用了不同的技术。因此,每个站上所需的时间是不同的, 即使是在两条不同装配线相同位置的装配站上也是这样。我们把在装配站 jiS , 上所需的《算法设计与分析》结课作业- 2- 装配时间记为 jia ,。如图 所示,一个汽车底盘进入其中一条装配线,然后从每一站进行到下一站。底盘进入装配线 i 的进入时间为 ie ,装配完的汽车离开装配线 i 的离开时间为 ix 。在正常情况下,一旦一个底盘进入一条装配线后,它只会经过该条装配线。在相同的装配线中,从一个装配站到下一个装配站所花的时间可以忽略。偶尔会来一个特别急的订单,客户要求尽可能快地制造这些汽车。对这些加急的订单,底盘仍然依序经过 n 个装配站,但是工厂经理可以将部分完成的汽车在任何装配站上从一条装配线移到另一条装配线上。把已经通过装配站 jiS ,的一个底盘从装配线 i移走所花的时间为 ji,t ,其中 i =1,2 ,而j =1,2 ,…,n -1(因为在第 n个装配后,装配已经完成)。问题是要确定在装配线 1 内选择哪些站以及在装配线 2 内选择哪些站,以使汽车通过工厂的总时间最小。在图 15-2a 所示的例子中,最快的总时间是选择装配线 1 的装配站 1, 3和 6 ,以及装配线 2 的装配站 2,4和5。图 15-1 一个找出通过工厂装配线的最快方式的制造问题。共有两条装配线,每条有 n 个装配站;装配线 i 的第 j 个装配站表示为 jiS , ,在该站的装配时间是 jia , 。一个汽车底盘进入工厂,然后进入装配线 i(i为l或 2) ,花费时间 ie 。在通过一条线的第 j 个装配站后,这个底盘来到任一条线的第(j +1) 个装配站。如果它留在相同的装配线,则没有移动的开销;但是,如果在装配站 jiS , 后,它移动到了另一条线上. 则花费时间 jit , 。在离开一条线的第 n 个装配站后, 完成的汽车花费时间 ix 离开工厂。待求解的问题是确定应该在装配线 1 内选择哪些站、在装配线 2 内选择些站,才能使汽车通过工厂的总时间量小显然, 当有很多个装配站时,用强力法( brute force ) 来极小化通过工厂装配线的时间是不可行的。如果给定一个序列,在装配线 1上使