企业官网建设流程全解析

厦门做网站seo,潍坊网站托管,苏州专业建站,卖渔具的亲戚做网站本文内容紧接动态规划#xff08;五#xff09;#xff0c;讨论如何优化序列对齐算法Hirschberg算法上文最后提到的解决方案#xff0c;是维护一个OPT矩阵#xff0c;那么它的空间开销就变成了O(mn)#xff0c;而Hirschberg 算法通过分治策略#xff0c;将序列对齐问题的…本文内容紧接动态规划五讨论如何优化序列对齐算法Hirschberg算法上文最后提到的解决方案是维护一个OPT矩阵那么它的空间开销就变成了O(mn)而Hirschberg 算法通过分治策略将序列对齐问题的空间复杂度从基础动态规划算法的O(mn)m、n 为两个序列的长度降低至 O(mn)。我们先回顾最优得分4是怎么来的其上方的0、右侧的0、和右上的3综合得到的实际上它只用到了自己所在的一列和前一列。下面我们验证一下首先初始化了第一列和第一行这时我们能得到第二列的所有数字吗显然是可以的。每个数字实际上只依赖自己附近的三个数。由此我们可知只需要用两个一维数组存储当前得分和前一列的得分即可将空间复杂度极大的降低了。问题这种方法没有存储之前的路径虽然降低了内存开销但会丢失回溯所需的完整矩阵信息导致无法恢复具体的最优对齐路径仅能得到得分。如何解决这个问题呢后缀对齐替代前缀对齐在解决这个问题前我们先介绍如何后缀对齐替代前缀对齐非常容易理解实际上只是把T和S从尾到头对齐而已这也告诉我们序列对齐不仅可以基于 “前缀prefixes即序列的前 k 个字符” 进行也可以基于 “后缀suffixes即序列的后 k 个字符” 进行且最终能得到与前缀对齐完全一致的最优得分和对齐形式。下面尝试用分治的方法来解决假设已得到最优对齐通过以下步骤拆分问题以恢复对齐路径选取 S 的中间位置第 n/2 位确定该位置对齐到 T 的哪个位置记为 q将 S 拆分为 “前 n/2 位” 和 “后 n/2 位”将 T 拆分为 “前 q 位” 和 “后 m-q 位”最优得分满足线性拆分关系OPT(T,S) OPT(T[1..q], S[1..]) OPT(T[q1..m], S[1..n])文字可能不好理解下面用一个例子来进行演示核心目标确定 S 的中间位置在 T 中对应的最优对齐位置 q为后续分治拆分问题做准备。首先我们确定S的一半向下取整是5根据S将序列对齐分为了两个子问题其中左侧是前缀序列对齐右侧是后缀序列对齐。分别计算得分最终由绿色列可以推出紫色列。由于最优得分满足线性拆分关系OPT(T,S) OPT(T[1..q], S[1..]) OPT(T[q1..m], S[1..n])因此将紫色列相加得到黄色列最大得分用红色标出这个值正是 S 与 T 全局对齐的最优得分 OPT(S,T)对应的位置即为S 中间位置在 T 中的最优对齐点 q。后续可递归执行相同逻辑最终在低空间复杂度下得到全局最优对齐。这样就可以恢复完整的最优对齐路径。下面再通过一个完整的递归过程来展示一下恢复1. 对齐位置对数组 A数组 A [5,4, 3,2, 1,1, 4,3, 7,6, 6,5, 8,7, 9,8]是T记为 X与 S记为 Y的字符对齐位置对每个a,b表示 “T 的第 a 个字符与 S 的第 b 个字符对齐”这些位置对是递归拆分过程中得到的子问题对齐结果。2. 分治递归的树状拆分结构根节点对应完整序列的对齐 ——X{OCCURRENCE}正确序列 T、Y{OCURRANCE}错误序列 S对齐位置对为5,4此前找到的 S 中间位置在 T 中的对齐点。子问题拆分根节点拆分为两个子问题再递归拆分至最小单元左分支X{OCCUR} 与 Y{OCUR} 对齐位置对3,2进一步拆分为 {OCC} 与 {OC}、{UR} 与 {UR} 等子问题右分支X{RENCE} 与 Y{RANCE} 对齐位置对7,6进一步拆分为 {RA} 与 {RE}、{NCE} 与 {NCE} 等子问题。3. 最终最优对齐结果所有子问题的对齐结果拼接后得到完整的最优对齐形式X {OCCURRENCE}\)T正确序列的对齐形式无空格Y {O-CURRANCE}\)S错误序列的对齐形式通过插入空格 “-” 与 T 匹配。这种方法极大的优化了空间复杂度且未改变时间复杂度仍为O(mn)Hirschberg 提出的 “分治技术” 并非仅适用于序列对齐问题而是几乎可以推广到所有动态规划算法中其分治思路具有广泛的适配性。对于任意一个 “能够计算出最优解数值” 的 DP 算法借助 Hirschberg 的分治逻辑通常可以在不增加原算法时间、空间复杂度的前提下进一步构造出最优解的具体形式。改进——J. Ian Munro 算法该算法是对Hirschberg算法的改进相较于之前其额外维护了一个R矩阵实际上每步仍然是只记录两列来帮助快速恢复。基于最优对齐得分 OPT[i,j]的推导来源R_{i,j} 的取值分 4 种情况当时R_{i,j} i此时 j 恰好是 S 的中间列对齐路径经过该列时对应的行号为 i。当且 OPT[i,j] 由 OPT[i-1,j] 推导对应删除操作R_{i,j} R_{i-1,j}当且 OPT[i,j] 由 OPT[i-1,j-1] 推导对应匹配 / 突变操作R_{i,j} R_{i-1,j-1}当且 OPT[i,j] 由 OPT[i,j-1] 推导对应插入操作R_{i,j} R_{i,j-1}下面看一个例子左侧矩阵得分矩阵OPT 矩阵矩阵的行对应正确序列 T字符为O、C、C、U、R…列对应错误序列 S字符为O、C、U、R、R…存储的是 “T 前 i 个字符与 S 前 j 个字符” 的最优对齐得分即 OPT[i,j]其中绿色列是 S 的中间列。右侧矩阵R 矩阵存储的是此前定义的 R_{i,j}“T 前 i 个字符与 S 前 j 个字符的最优对齐路径经过 S 中间列时的行号”。矩阵中绿色部分是计算后的 R_{i,j} 值。确定初始 q对于完整序列的对齐通过 R 矩阵可得到最优对齐路径经过 S 中间列时对应的 T 的行号为 5因此 q 5即 S 中间位置在 T 中的对齐位置。接下来与之前的解决方案一致可以通过不断分治来完成序列对齐的恢复。对于序列对齐任务衍生出非常多的优化算法后续还有Banded DP等将在下文进行介绍