算法设计与分析(霍红卫)_第3章 动态规划.ppt

(4) 构造装配线调度的最优解。  计算出fi［j］、li［j］、f*和l*之后，我们可以构造出最快方式通过哪些站点。过程OUTPUT-STATION按照站点号递增的次序输出。 OUTPUT-STATION(l, i, j) 1 if j=0 then return  2 OUTPUT-STATION(l, li［j］, j-1) 3 print “line” i “, station” j 如要输出所有站点，需调用OUTPUT-STATION (l, l*, n)。 在图3-13的示例中，OUTPUT-STATION将产生如下输出：  line 1, station 1 line 2, station 2 line 1, station 3 line 2, station 4 line 2, station 5 line 1, station 6 3.7 最长公共子序列 (1) 刻画LCS问题的最优子结构。  如果利用穷举法解LCS问题，列举出X的所有子序列，检查每个子序列是否是Y的一个子序列，记录所找到的最长子序列， X的每个子序列与X的下标集{1, 2, …, n}的一个子集对应，X共有2m个子序列，因而，这种方法具有指数级的复杂度。因此，对于长序列， 这种方法不可行。 借助图3-15，定理3.1证明了LCS问题具有最优子结构性质。 给定序列X=〈x1, x2, …, xm〉，定义Xi=〈 x1, x2, …, xi〉为X的第i个前缀，其中i=0, 1, …, m。例如，如果X=〈B, A, C, A, D, A, B〉，X3=〈B, A, C〉，X0为空序列。 图 3-15 LCS问题的最优子结构 定理3.1LCS的最优子结构。设X=〈x1, x2, …, xm〉和Y=〈y1, y2, …, yn〉是两条序列，Z=〈z1, z2, …, zk〉是X和Y的任一LCS。  (i) 如果xm=yn，那么zk=xm=yn，且Zk-1是Xm-1和Yn-1的一条最长公共子序列。  (ii) 如果xm≠yn，那么zk≠xm，蕴含着Z是Xm-1和Y的一条最长公共子序列。  (iii) 如果xm≠yn，那么zk≠yn，蕴含着Z是X和Yn-1的一条最长公共子序列。 证明： (i) 如果zk≠xm，那么，我们可以将xm=yn添加到序列Z后， 得到X和Y的一条长度为k+1的公共子序列，这与Z是X和Y的最长公共子序列矛盾。因此，一定会有zk=xm=yn。现在，前缀Zk-1是Xm-1和Yn-1的长度为k-1的公共子序列。我们要证明，这条子序列是最长公共子序列。假定存在Xm-1和Yn-1的长度大于k-1的公共子序列W，则将xm=yn添加到序列W后，产生X和Y的长度大于k的公共子序列， 这与k是最长公共子序列的长度相矛盾。 (ii) 如果zk≠xm，则Z是Xm-1和Y的一条公共子序列。如果存在Xm-1和Yn-1的长度大于k的公共子序列W，那么W也会是Xm和Y的公共子序列，这与Z是X和Y的LCS的假设相矛盾。  (iii) 如果zk≠yn，则Z是X和Yn-1的一条公共子序列。如果存在Xm-1和Yn-1的长度大于k的公共子序列W，那么W也会是X和Yn的公共子序列，这与Z是X和Y的LCS的假设相矛盾。 证毕。  定理3.1表明，两条序列的LCS包含两条序列前缀的LCS。 因此，LCS问题具有最优子结构性质，其递归解具有重叠子问题性质。 (2) 递归定义LCS问题最优解的值。  定理3.1表明，当求X=〈x1, x2, …, xm〉和Y=〈y1, y2, …, yn〉的一条最长公共子序列时，需要考察一个或两个子问题。如果xm=yn，我们一定要找Xm-1和Yn-1的LCS。将xm=yn添加到这条LCS之后，就得到X和Y的LCS。如果xm≠yn，则必须解两个子问题，这就是求Xm-1和Y以及X和Yn-1这两个子问题的解。这两个子问题中较长的LCS就是X和Y的LCS。因为这些情形已经穷举了所有可能性，我们知道其中的最优子问题一定是X和Y的一条LCS。 我们可以容易地表明，LCS问题具有重叠子问题性质。要求出X和Y的LCS，必须求出Xm-1和Y以及X和Yn-1这两个子问题的LCS。但这两个子问题都以Xm-1和Yn-1的LCS作为子问题。许多其他子问题共享子问题。 