文档介绍：本科生学年论文(设计) 题目: 比对算法论文学院生命科学学院学科门类理学专业生物信息学号 2012447014 姓名岳海川指导教师刘建国 201 5年7月 19日标准动态规划与懒惰动态规划岳海川 2012447014 生物信息一、标准动态规划 Standard DPA 是生物信息学中最流行的解决方法,其基本思想可简述为:使用迭代方法计算出两个序列的相似分值, 存于一个得分矩阵中; 根据这个得分矩阵, 回溯寻找最优的比对序列。标准动态规划算法求解过程是从两个比对序列前端开始, 逐步推进, 直到两个序列的末端。标准动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用标准动态规划方法比用其它方法求解更为方便。虽然标准动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用标准动态规划方法方便地求解。标准动态规划程序设计是对解最优化问题的一种途径、一种方法,而不是一种特殊算法。不像搜索或数值计算那样,具有一个标准的数学表达式和明确清晰的解题方法。标准动态规划程序设计往往是针对一种最优化问题,由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的解题方法,而不存在一种万能的动态规划算法,可以解决各类最优化问题。因此在学****时,除了要对基本概念和方法正确理解外,必须具体问题具体分析处理,以丰富的想象力去建立模型,用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论,逐渐学会并掌握这一设计方法。标准动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中, 可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是, 适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样, 但它们具有相同的填表格式。标准动态规划的基本模型如下: (1) 确定问题的决策对象。(2) 对决策过程划分阶段。(3) 对各阶段确定状态变量。(4) 根据状态变量确定费用函数和目标函数。(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[U1] ;结果: f[Un] 。倒推: f[Uk]=opt{f[Uk+1]+L[Uk,Xk]} L[Uk,Xk] :状态 Uk 通过策略