标准动态规划与懒惰动态规划

《标准动态规划与懒惰动态规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本科生学年论丈f设计J比对算学晚生命科学学晚学科门类理学专止生物信息学号2012447014M名岳海川指导教师到建国2015年7月19g标准动态规划与懒惰动态规划岳海川2012447014生物信息一、标准动态规划StandardDPA是生物信息学屮最流行的解决方法，其基本思想可简述为：使川迭代方法计算出两个序列的相似分值，存于一个得分矩阵中；根裾这个得分矩阵，回溯寻找最优的比对序列。标准动态规划算法求解过程是从两个比对序列前端7T•始，逐步推进，直到两个序列的末端。标准动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到Y广泛的应用。例如最短路线、库存管理

2、、资源分配、设备更新、排序、装载等问题，用标准动态规划方法比用其它方法求解更为方便。虽然标准动态规划主耍用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用标准动态规划方法方便地求解。标准动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具冇一个标准的数学表达式和明确清晰的解题方法。标准动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特

3、色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。冈此在学习吋，除了要对基木概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干宥代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。标准动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解W题分解成若干个子问题，先求解子问题，然盾从这些子问题的解得到原问题的解。与分治法不同的是，适合丁•用动态规

4、划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要吋再找山已求将•的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所冇已解的了问题的答案。不管该子问题以盾是否被用到，只要它被计算过，就将其结果填入表屮。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有和同的填表格式。标准动态规划的基木模型如下：⑴确定问题的决策对象。(2)对决策过程划分阶段。(3)对各阶段确定状态变量。(4)根据状态变量确定费用函数和目标函数

5、。(5)建立各阶段状态变量的转移过程，确定状态转移方程。状态转移方程的一般形式：一般形式：U：状态；X：策略顺推：f[Uk]=opt{f[Uk-1]+L[Uk-1,Xk-1]}其中,L[Uk-1,Xk-1]：状态Uk-1通过策略Xk-1到达状态Uk的费用初始f[Ul];结果：f[Un]o倒推：f[Uk]=opt{f[Uk+1]+L[Uk，Xk]}L[Uk,Xk]：状态Uk通过策略Xk到达状态Uk+1的费用初始f[Un];结果:f(Ul)序列A=acgtacgtacgtB=acatacttgtact经StandardDPA比对结果如图：ThisisUkkonensalgor

6、ithmforcostsasfortheLinearDFAcasStandardDPA▼acgtacgtacgtacatacttgtactGoStopStatus:Pause100msDPAdone.Cost=4acgtac一一gtacgtacatacttgtac-tCellscomputed=182ac:atacttgtacta01234567891011121310123456189101112C2101234561891011g321123456618910ta4322123456618954322123456618c65433212345667g了65443223

7、34567ta8165443223345698165443334345c109816544444434g1110981655545544t12111098765554554标准动态规划算法的优点：冈其准确性高而得到广泛应用，适用于字符数量不大的序列，易于理解。缺点：时间和空间复杂度为O(n2)，而在实际的生物信息处理中，进行比对的生物序列通常宥上万个以上的字符，因此标准动态规划方法不是很实用。二、懒惰动态规划LazyDPA是动态规划算法的~个特例，懒惰的评价是在编程屮动态规划算法编辑距离问题快速运行的描述。其基本思路：从M题的