第四章动的态规划法.ppt

算法设计与分析 * 多边形游戏的动态规划算法 依据上述讨论以及所得的递归式，不难写出多边形游戏动态规划算法。请同学们自己编写。 算法的主程序应包含一个子程序MIN_MAX。子程序MIN_MAX负责对确定s的minf (i, j, s)和maxf (i, j, s)的计算。而对任意链的最大值m[i, j, 1]和最小值m[i, j, 0]的计算则是在主程序中进行的。 算法的时间复杂性显然仍为O(n3)。 算法设计与分析 * DNA序列的相似性 将序列A、B表示为对偶(a, b)的序列。其中若： 1、a?A和b?B称为替换，a = b称为匹配，否则称为不匹配，其得分为σ (a, b)； 2、a?A，b是空位为删除空白； 3、a是空位，b?B为插入空白； 对于长度为k的空位，其得分为–(q + k ? r)。 这里，参数σ (a, b)、q和r由用户确定。 两个序列A、B的相似性为所有这样的对偶序列中最高的得分。 算法设计与分析 * DNA序列的相似性 若给定两个DNA序列： AGCTACGTACACTACC AGCTATCGTACTAGC 下面是其一个相似性序列： AGCTA–CGTACACTACC AGCTATCGTAC– –TAGC 其中有13个匹配、1个不匹配、一个长度为1的插入空白和一个长度为2的删除空白。 若a = b时σ(a, b) = 10；a ? b时σ(a, b) = –20； q = 40；r = 2。该相似性序列的得分为 10 * 13 – 20 – (40 + 2) – (40 + 2 * 2) = 24 算法设计与分析 * 递归求序列相似性 设A = a1a2…am，B = b1b2…bn。令S(m, n)为A和B的相似性，即各种对偶序列最大的得分。 为了采用递归方法来求解此问题，我们从序列尾部来考虑，那么有三种方案： ①尾部用替换，即最后一个对偶为(am, bn)； ②尾部用删除空白，即最后一个对偶为(am, –)； ③尾部用插入空白，即最后一个对偶为(–, bn)。 令S(m, n)、D(m, n)和I(m, n)分别为三种方案的得分，则其相似性应为三种方案的最大得分。 算法设计与分析 * 递归求序列相似性 S(m, n) = S(m – 1, n – 1) + σ(am, bn)。 若用方案①，即尾部用替换，则 D(m, n) = S(m – 1, n) – q – r 或者，D(m, n) = D(m – 1, n) – r 若用方案②，即尾部用删除空白，则 I(m, n) = S(m, n – 1) – q – r 或者，I(m, n) = I(m, n – 1) – r 若用方案③，即尾部用插入空白，则 算法设计与分析 * 递归求序列相似性 现在考虑非递归分支： S(0, 0) = 0、S(m, 0) = D(m, 0)、S(0, n) = I(0, n)。 对方案①，有 D(m, 0) = D(m – 1, 0) – r、D(0, n) = S(0, n) – q。 对方案②，有 I(m, 0) = S(m, 0) – q、I(0, n) = S(0, n – 1) – q。 对方案③，有 算法设计与分析 * 递归求序列相似性 S(m,n) = 0 m = 0, n = 0 D(m, 0) for n ? 0 I(0, n) for m ? 0 max{S(m–1,n–1)+σ(am,bn), D(m,n), I(m,n)} D(m,n) = S(0, n) – q for n ? 0 D(m – 1, 0) – r for m ? 0 max{S(m–1,n) – q - r, D(m – 1,n) – r} I(m,n) = S(m, 0) – q for m ? 0 I(0, n – 1) – r for n ? 0 max{S(m,n–1) – q - r, I(m – 1,n) – r} 算法设计与分析 * 动态规划求序列相似性 如果用递归算法求序列的相似性，其时间复杂性显然是指数级的。 考虑采用动态规划法。为此，需要 ⑴用矩阵S[0:m, 0:n]、D[0:m, 0:n]和I[0:m, 0: n]来分别记载对应于子序列Ai和Bj的得分S(i, j)、D(i, j)和I(i, j)，0 ? i ? m，0 ?