《动态规划法.ppt》由会员分享，可在线阅读，更多相关《动态规划法.ppt（67页珍藏版）》请在三一文库上搜索。
1、第6章 动态规划法,6.1 概 述,6.2 图问题中的动态规划法,6.3 组合问题中的动态规划法,6.4 查找问题中的动态规划法,6.5 实验项目最大子段和问题,6.1 概 述,6.1.1 最优化问题,6.1.2 最优性原理,6.1.3 动态规划法的设计思想,最优化问题：有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值（极大或极小）的可行解称为最优解，这
2、类问题就称为最优化问题。,6.1.1 最优化问题,例：付款问题： 超市的自动柜员机（POS机）要找给顾客数量最少的现金。 假定POS机中有n张面值为pi(1in)的货币，用集合P=p1, p2, , pn表示，如果POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得 （式6.1）,如果用向量X=( x1, x2, , xn)表示S中所选取的货币，则 （式6.2）,那么，POS机支付的现金必须满足 （式6.3）,并且 （式6.4）,在付款问题中，集合P是该问题的输入，满足式6.1的解称为可行解，式6.2是解的表现形式，因为向量X中有n个元素，每个元素的取值为0或1，所以，可以有2
3、n个不同的向量，所有这些向量的全体构成该问题的解空间，式6.3是该问题的约束条件，式6.4是该问题的目标函数，使式6.4取得极小值的解称为该问题的最优解。,6.1.2 最优性原理,对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。,在每一阶段的决策中有一个赖以决策的策略或目标，这种策略或目标是由问题的性质和特点所确定，通常以函数的形式表示并具有递推关系，称为动态规划函数。,多阶段决策过程满足最优性
4、原理（Optimal Principle）：无论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。 如果一个问题满足最优性原理通常称此问题具有最优子结构性质。,6.1.3 动态规划法的设计思想,动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。,动态规划法的求解过程,n=5时分治法计算斐波那契数的过
5、程。,例：计算斐波那契数：,动态规划法求解斐波那契数F(9)的填表过程 ：,注意到，计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。,用动态规划法求解的问题具有特征： 能够分解为相互重叠的若干子问题； 满足最优性原理（也称最优子结构性质）：该问题的最优解中也包含着其子问题的最优解。 （用反证法）分析问题是否满足最优性原理： 先假设由问题的最优解导出的子问题的解不是最优的; 然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,动态规划法设计算法一般分成三个阶段： （1）分段：将原问题分解为若干个相互
6、重叠的子问题； （2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式； （3）求解：利用递推式自底向上计算，实现动态规划过程。 动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。,6.2 图问题中的动态规划法,6.2.1 TSP问题,6.2.2 多段图的最短路径问题,6.2.1 TSP问题,TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。 各个城市间的距离可以用代价矩阵来表示。,设s, s1, s2, , sp, s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求
7、出，则问题转化为求从s1到s的最短路径，显然s1, s2, , sp, s一定构成一条从s1到s的最短路径。 如若不然，设s1, r1, r2, , rq, s是一条从s1到s的最短路径且经过n-1个不同城市，则s, s1, r1, r2, , rq, s将是一条从s出发的路径长度最短的简单回路且比s, s1, s2, , sp, s要短，从而导致矛盾。所以，TSP问题满足最优性原理。,证明TSP问题满足最优性原理,假设从顶点i出发，令d(i, V)表示从顶点i出发经过V中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，VVi，于是，TSP问题的动态规划函数为： d(i,V)=m
8、incik+d(k,Vk)(kV) （式6.5） d(k,)=cki(ki) （式6.6）,这是最后一个阶段的决策，而： d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2) d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1) d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1) 这一阶段的决策又依赖于下面的计算结果： d(1, 2)= c12+d(2, ) d(2, 3)=c23+d(3, ) d(3, 2)= c32+d(2, ) d(1, 3)= c13+d(3, ) d(2, 1)=c21+d(1, ) d
9、(3, 1)=c31+d(1, ),从城市0出发经城市1、2、3然后回到城市0的最短路径长度是： d(0,1, 2, 3)=minc01+d(1, 2, 3), c02+d(2, 1, 3), c03+d(3, 1, 2),而下式可以直接获得（括号中是该决策引起的状态转移）： d(1, )=c10=5(10) d(2, )=c20=6(20) d(3, )=c30=3(30),再向前倒推，有： d(1, 2)= c12+d(2, )=2+6=8(12) d(1, 3)= c13+d(3, )=3+3=6(13) d(2, 3)= c23+d(3, )=2+3=5(23) d(2, 1)= c2
10、1+d(1, )=4+5=9(21) d(3, 1)= c31+d(1, )=7+5=12(31) d(3, 2)= c32+d(2, )=5+6=11(32) 再向前倒退，有： d(1, 2, 3)=minc12+d(2, 3), c13+ d(3, 2)=min2+5, 3+11=7(12) d(2, 1, 3)=minc21+d(1, 3), c23+ d(3, 1)=min4+6, 2+12=10(21),d(3, 1, 2)=minc31+d(1, 2), c32+ d(2, 1)=min7+8, 5+9=14(32) 最后有： d(0, 1, 2, 3)=minc01+ d(1,
11、2, 3), c02+ d(2, 1, 3), c03+ d(3, 1, 2) =min3+7, 6+10, 7+14=10(01) 所以，从顶点0出发的TSP问题的最短路径长度为10，路径是01230。,假设n个顶点用0n-1的数字编号，首先生成1n-1个元素的子集存放在数组V2n-1中，设数组dn2n-1存放迭代结果，其中dij表示从顶点i经过子集Vj中的顶点一次且仅一次，最后回到出发点0的最短路径长度。,动态规划法求解TSP问题的填表过程,显然，算法6.1的时间复杂性为O(2n)。和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了
12、算法的时间复杂性，但它仍需要指数时间。,设顶点之间的代价存放在数组cnn中，动态规划法求解TSP问题的算法如下：,6.2.2 多段图的最短路径问题,设图G=(V, E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2kn, 1ik），使得E中的任何一条边(u, v)，必有uVi，vVi+m（1ik, 1i+mk），则称图G为多段图，称sV1为源点，tVk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。,由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺
13、序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u, v)，顶点u的编号小于顶点v的编号。,设s, s1, s2, , sp, t是从s到t的一条最短路径，从源点s开始，设从s到下一段的顶点s1已经求出，则问题转化为求从s1到t的最短路径，显然s1, s2, , sp, t一定构成一条从s1到t的最短路径，如若不然，设s1, r1, r2, , rq, t是一条从s1到t的最短路径，则s, s1, r1, r2, , rq, t将是一条从s到t的路径且比s, s1, s2, , sp, t的路径长度要短，从而导致矛盾。所以，多段图的最短路
14、径问题满足最优性原理。,证明多段图问题满足最优性原理,对多段图的边(u, v)，用cuv表示边上的权值，将从源点s到终点t的最短路径记为d(s, t)，则从源点0到终点9的最短路径d(0, 9)由下式确定： d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9) 这是最后一个阶段的决策，它依赖于d(1, 9)、d(2, 9)和d(3, 9)的计算结果，而 d(1, 9)=minc14+d(4, 9), c15+d(5, 9) d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9) d(3, 9)=minc35+
15、d(5, 9), c36+d(6, 9) 这一阶段的决策又依赖于d(4, 9)、d(5, 9)和d(6, 9)的计算结果：,d(4, 9)=minc47+d(7, 9), c48+d(8, 9) d(5, 9)=minc57+d(7, 9), c58+d(8, 9) d(6, 9)=minc67+d(7, 9), c68+d(8, 9) 这一阶段的决策依赖于d(7, 9)和d(8, 9)的计算，而d(7, 9)和d(8, 9)可以直接获得（括号中给出了决策产生的状态转移）： d(7, 9)=c797(79) d(8, 9)=c893(89) 再向前推导，有： d(6, 9)=minc67+d(
16、7, 9), c68+d(8, 9)=min6+7, 5+3=8(68) d(5, 9)=minc57+d(7, 9), c58+d(8, 9)=min8+7, 6+3=9(58) d(4, 9)=minc47+d(7, 9), c48+d(8, 9)=min5+7, 6+3=9(48),d(3, 9)=minc35+d(5, 9), c36+d(6, 9)=min4+9, 7+8=13(35) d(2, 9)=minc24+d(4, 9), c25+d(5, 9), c26+d(6, 9)=min6+9, 7+9, 8+8=15(24) d(1, 9)=minc14+d(4, 9), c15
17、+d(5, 9)=min9+9, 8+9=17(15) d(0, 9)=minc01+d(1, 9), c02+d(2, 9), c03+d(3, 9)=min4+17, 2+15, 3+13=16(03) 最后，得到最短路径为03589，长度为16。,下面考虑多段图的最短路径问题的填表形式。 用一个数组costn作为存储子问题解的表格，costi表示从顶点i到终点n-1的最短路径，数组pathn存储状态，pathi表示从顶点i到终点n-1的路径上顶点i的下一个顶点。则： costi=mincij+costj (ijn且顶点j是顶点i的邻接点) （式6.7） pathi=使cij+costj最
18、小的j （式6.8）,算法6.2主要由三部分组成：第一部分是初始化部分，其时间性能为O(n)；第二部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有出边进行计算，并且在所有循环中，每条出边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第三部分是输出最短路径经过的顶点，其时间性能是O(n)。所以，算法6.2的时间复杂性为O(n+m)。,6.3 组合问题中的动态规划法,6.3.1 0/1背包问题,6.3.2 最长公共子序列问题,6.3.1 0/1背包问题,在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背
19、包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：,（式6.9）,（式6.10）,于是，问题归结为寻找一个满足约束条件式6.9，并使目标函数式6.10达到最大的解向量X=(x1, x2, , xn)。,证明0/1背包问题满足最优性原理。 设(x1, x2, , xn)是所给0/1背包问题的一个最优解，则( x2, , xn)是下面一个子问题的最优解：,如若不然，设(y2, , yn)是上述子问题的一个最优解，则 因此， 这说明(x1, y2, , yn)是所给0/1背包问题比(x1, x2, , xn)更优的解，从而
20、导致矛盾。,0/1背包问题可以看作是决策一个序列(x1, x2, , xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1, , xi-1)，在决策xi时，问题处于下列两种状态之一： （1）背包容量不足以装入物品i，则xi=0，背包不增加价值； （2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi。 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i, j)表示在前i(1in)个物品中能够装入容量为j（1jC）的背包中的物品的最大值，则可以得到如下动态规划函数： V(i, 0)= V(0, j)=0 （式6.11）,（式6.12）
21、,式6.11表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式6.12的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前
22、i个物品装入容量为j的背包中的最优解。,根据动态规划函数，用一个(n+1)(C+1)的二维表V，Vij表示把前i个物品装入容量为j的背包中获得的最大价值。,0,例如，有5个物品，其重量分别是2, 2, 6, 5, 4，价值分别为6, 3, 5, 4, 6，背包的容量为10。,按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,
23、C)V(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：,（式6.13）,设n个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：,在算法6.3中，第一个for循环的时间性能是O(n)，第二个for循环的时间性能是O(C)，第三个循环是两层嵌套的fo
24、r循环，其时间性能是O(nC)，第四个for循环的时间性能是O(n)，所以，算法6.3的时间复杂性为O(nC)。,6.3.2 最长公共子序列问题,对给定序列X=(x1, x2, xm)和序列Z=(z1, z2, zk)，Z是X的子序列当且仅当存在一个严格递增下标序列(i1, i2, ik)，使得对于所有j=1, 2, , k，有zj=xij（1ijm）。 给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列问题就是在序列X和Y的公共子序列中查找长度最长的公共子序列。,证明最长公共子序列问题满足最优性原理。 设序列X=x1, x2, xm
25、和Y=y1, y2, yn的最长公共子序列为Z=z1, z2, zk，记Xk为序列X中前k个连续字符组成的子序列，Yk为序列Y中前k个连续字符组成的子序列，Zk为序列Z中前k个连续字符组成的子序列，显然有下式成立： （1）若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列； （2）若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列； （3）若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。 可见，两个序列的最长公共子序列包含了这两个序列的前缀序列的最长公共子序列。,要找出序列X=x1, x2, xm和Y=y1, y2, yn的最长公共子序列，可按下述
26、递推方式计算：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列；当xmyn时，必须求解两个子问题：找出Xm-1和Y的最长公共子序列以及Xm和Yn-1的最长公共子序列，这两个公共子序列中的较长者即为X和Y的最长公共子序列。用Lij表示子序列Xi和Yj的最长公共子序列的长度，可得如下动态规划函数： L00=Li0=L0j=0(1im,1jn) （式6.14） （式6.15）,由此，把序列X=x1, x2, xm和Y=y1, y2, yn的最长公共子序列的搜索分为m个阶段，第1阶段，按照式6.15计算X1和Yj的最长公共子序列长度L1j（1j
27、n），第2阶段，按照式6.15计算X2和Yj的最长公共子序列长度L2j（1jn），依此类推，最后在第m阶段，计算Xm和Yj的最长公共子序列长度Lmj（1jn），则Lmn就是序列Xm和Yn的最长公共子序列的长度。,为了得到序列Xm和Yn具体的最长公共子序列，设二维表Sm+1n+1，其中Sij表示在计算Lij的过程中的搜索状态，并且有：,（式6.16）,若Sij=1，表明ai=bj，则下一个搜索方向是Si-1j-1；若Sij=2，表明aibj且Lij-1Li-1j，则下一个搜索方向是Sij-1；若Sij=3，表明aibj且Lij-1Li-1j，则下一个搜索方向是Si-1j。,(a) 长度矩阵L (
28、b) 状态矩阵S,例：序列X=(a, b, c, b, d, b)，Y=(a, c, b, b, a, b, d, b, b)，建立两个(m+1)(n+1)的二维表L和表S，分别存放搜索过程中得到的子序列的长度和状态。,在算法6.4中， 第一个for循环的时间性能是O(n)； 第二个for循环的时间性能是O(m)； 第三个循环是两层嵌套的for循环，其时间性能是O(mn)； 第四个for循环的时间性能是O(k)，而kminm, n，所以，算法6.4的时间复杂性是O(mn)。,6.4 查找问题中的动态规划法,6.4.1 最优二叉查找树,6.4.2 近似串匹配问题,设r1, r2, , rn是n个
29、记录的集合，其查找概率分别是p1, p2, , pn，最优二叉查找树（Optimal Binary Search Trees）是以这n个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树，即 最小，其中pi是记录ri的查找概率，ci是在二叉查找树中查找ri的比较次数。,6.4.1 最优二叉查找树,例如，集合A, B, C, D的查找概率是0.1, 0.2, 0.4, 0.3， (a)的平均比较次数是0.110.22+0.43+0.34=2.9， (b)的平均比较次数是0.120.21+0.42+0.33=2.1， (c)的平均比较次数是0.130.22+0.41+0.32=1.7。,将由r
30、1, r2, , rn构成的二叉查找树记为T(1, n)，其中rk（1kn）是T(1, n)的根结点，则其左子树T(1, k-1)由r1, , rk-1构成，其右子树T(k+1, n)由rk+1, , rn构成。,证明最优二叉查找树满足最优性原理,若T(1, n)是最优二叉查找树，则其左子树T(1, k-1)和右子树T(k+1, n)也是最优二叉查找树，如若不然，假设T(1, k-1)是比T(1, k-1)更优的二叉查找树，则T(1, k-1)的平均比较次数小于T(1, k-1)的平均比较次数，从而由T(1, k-1)、rk和T(k+1, n)构成的二叉查找树T(1, n)的平均比较次数小于T
31、(1, n)的平均比较次数，这与T(1, n)是最优二叉查找树的假设相矛盾。,设T(i, j)是由记录ri, , rj(1ijn)构成的二叉查找树，C(i, j)是这棵二叉查找树的平均比较次数。虽然最后的结果是C(1, n)，但遵循动态规划法的求解方法,需要求出所有较小子问题C(i, j)的值，考虑从ri, , rj中选择一个记录rk作为二叉查找树的根结点，可以得到如下关系：,因此，得到如下动态规划函数： C(i, i-1)=0 (1in+1) （式6.17） C(i, i)=pi (1in) （式6.18） C(i, j)=minC(i, k-1)+C(k+1, j)+ (1ijn, ikj
32、) （式6.19） 设一个二维表Cn+1n+1，其中Cij表示二叉查找树T(i, j)的平均比较次数。注意到在式6.19中，当k=1时，求Cij需要用到Ci0，当k=n时，求Cij需要用到Cn+1j，所以，二维表Cn+1n+1行下标的范围为1n+1，列下标的范围为0n。 为了在求出由r1, r2, , rn构成的二叉查找树的平均比较次数的同时得到最优二叉查找树，设一个二维表Rn+1n+1，其下标范围与二维表C相同，Rij表示二叉查找树T(i, j)的根结点的序号。,例如，集合A, B, C, D的查找概率是0.1, 0.2, 0.4, 0.3，二维表C和R的初始情况如图6.13所示。,在二维表
33、C和R中只需计算主对角线以上的元素。 首先计算C(1, 2)：,在前两个记录构成的最优二叉查找树的根结点的序号是2。,按对角线逐条计算每一个C(i, j)和R(i, j)，得到最终表。,设n个字符的查找概率存储在数组pn中，动态规划法求解最优二叉查找树的算法如下：,for (d=1; dn; d+) /按对角线逐条计算 for (i=1; i=n-d; i+) j=i+d; min=; mink=i; sum=0; for (k=i; k=j; k+) sum=sum+pk; if (Cik-1+Ck+1jmin) min=Cik-1+Ck+1j; mink=k; Cij=min+sum; R
34、ij=mink; return C1n; ,6.4.2 近似串匹配问题,设样本P=p1p2pm，文本T=t1t2tn，对于一个非负整数K，样本P在文本T中的K-近似匹配（K-approximate Match）是指P在T中包含至多K个差别的匹配（一般情况下，假设样本是正确的）。这里的差别是指下列三种情况之一： （1）修改：P与T中对应字符不同； （2）删去：T中含有一个未出现在P中的字符； （3）插入：T中不含有出现在P中的一个字符。,样本P和文本T为K-近似匹配包含两层含义： （1）二者的差别数至多为K； （2）差别数是指二者在所有匹配对应方式下的最小编辑错误总数。,证明近似串匹配问题满足最
35、优性原理。 如果样本p1p2pm在文本T的某一位置上有最优（差别数最小）的对应关系，则样本P的任意一个子串pipj（1ijm）与文本T的对应关系也必然是最优的。 动态规划函数： 定义一个代价函数D(i, j)(0im,0jn)表示样本前缀子串p1pi与文本前缀子串t1tj之间的最小差别数，则D(m, n)表示样本P与文本T 的最小差别数。 根据近似匹配的定义，容易确定代价函数的初始值： （1）D(0, j)=0，因为空样本与文本t1tj有0处差别； （2）D(i, 0)=i，因为样本p1pi与空文本t1tj有i 处差别。,当样本p1pi与文本t1tj对应时，D(i, j)有四种可能的情况： （
36、1）字符pi与tj相对应且pi=tj，则总差别数为D(i-1, j-1)； （2）字符pi与tj相对应且pitj，则总差别数为D(i-1, j-1)1； （3）字符pi为多余，即字符pi对应于tj后的空格，则总差别数为D(i-1, j)1； （4）字符tj为多余，即字符tj对应于pi后的空格，则总差别数为D(i, j-1)1。,例：已知样本P=“happy“，K=1，T=“Have a hsppy day“是一个可能有编辑错误的文本，在T中求1-近似匹配的过程如下：,由于D(5, 12)=1且m=5，所以，在t12处找到了差别数为1的近似匹配，此时的对应关系如下：,算法6.6的时间复杂性为O(mn)。,6.5 实验项目最大子段和问题,1. 实验题目 给定由n个整数组成的序列(a1, a2, , an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。,2. 实验目的 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。,3. 实验要求 （1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； （2）比较不同算法的时间性能； （3）给出测试数据，写出程序文档。,