最优化方法在计算机专业的应用.docx

PAGE

PAGE10/10

动态规划方法在计算机专业的应用

科目：最优化方法姓名：***

专业：计算机科学与技术学号：201320405

指导老师：***日期：2014/1/9

动态规划方法在计算机专业的应用

摘要：最优化方法是一门很有用的学科，本文结合计算机专业，讨论了用动态规划方法解决计算最长公共子序列、最大字段和、背包问题的过程，并对比其它算法以说明动态规划方法的高效、实用。

关键词：动态规划，最优化，算法分析

Abstract:Theoptimizationmethodisausefuldiscipline,thispaper,acomputerprofessional,discussestheprocessusedtocalculatethedynamicprogrammingmethodtosolvethelongestcommonsubsequence,themaximumfieldand,knapsackproblem,andcomparedtootheralgorithmstoillustratethedynamicprogrammingmethodefficientandpractical.

Keywords:dynamicprogramming,optimization,algorithmanalysis

动态规划（dynamicprogramming）是通过结合子问题的解而解决整个问题的。（此处“programming”是指一种规划，而不是指写计算机代码。）动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做很多不必要的工作，即重复地求解公共的子子问题。动态规划算法对每个公共的子子问题只求解一次，将其结果保存在一张表中，从而避免了每次遇到各个子问题时重新计算答案。

一、算法设计与优化

动态规划通常应用于最优化问题。此类问题可能有很多可行解。

每个解有一个值，而我们希望找出一个具有最优（最大或最小）值的解。称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优值的解。 动态规划算法的设计可以分为如下4个步骤：

描述最优解的结构。

递归定义最优解的值。

按自底向上的方式计算最优解的值。

由计算出的结果构造一个最优解。

第1~3步构成问题的动态规划解的基础。第4步在只要求计算最优解的值时可以略去。如果的确做了第4步，则有时要在第3步的计算中记录一些附加信息，使构造一个最优解变得容易。

接下来的各节利用动态规划方法来求解一些最优化问题。比如包括两个汽车装配线的调度问题，在经过每个装配站后，组装中的汽车可以留在同一条装配线上，或者移动到另外一条装配线。如何通过做一连串的矩阵乘法，使得所做的标量乘法总次数最少。此外，例如如何在已知待有哪些信誉好的足球投注网站的关键字分布的情况下，如何利用动态规划构造最优的二叉查找树，这些算法问题都可利用动态规划方法来解决。

（一）最长公共子序列

1、具体问题

、若给定序列X={x,x,…,x}，则另一序列Z={z,z,…,z}，

1 2 m 1 2 k

是X的子序列是指存在一个严格递增下标序列{i,i,…,i}使得对于所

12 k

有j=1,2,…,k有：z=x。例如，序列Z={B，C，D，B}是序列X={A，

j ij

B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。

、给定2个序列X和Y，当另一序列Z既是X的子序列又是

Y的子序列时，称Z是序列X和Y的公共子序列。

、给定2个序列X={x

,x,…,x

}和Y={y

,y,…,y

}，找出X和

Y的最长公共子序列。

2、分析

1 2 m

1 2 n

设序列X={x,x,…,x}和Y={y,y,…,y}的最长公共子序列为

1 2 m 1 2 n

Z={z,z

1

,…,z

2

} ，则

k

若x

=y，则z=x=y，且z 是x

和y 的最长公共子序列。

m n k m n

k-1

m-1

n-1

若x≠y且z≠x，则Z是x

和Y的最长公共子序列。

m n k m m-1

若x≠y且z≠y，则Z是X和y

的最长公共子序列。

m n k n n-1

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。3、子问题的递归结构

由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[