文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 动态规划解最长公共子序列
侵权投诉

动态规划解最长公共子序列

函数及其图像纯手工打,用表格及其公式编辑器写作。动态规划解最长公共子序列,C语言实现,算法核心在,

系如下:

0 =0,j=0

C = c 1 1 +1 ,j>0; =

c 1 ,c 1 ,j>0; ≠

3. 例子:求两字符序列的最长公共字符子序列

问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X= 1, 2,…, ,序列Y= 1, 2,…, 是X的子序列,存在X的一个严格递增下标序列 0, 1,…, 1 ,使得对所有的j= 0,1,…,k 1 ,有 = 。例如,X=“BACDCA”,Y=“ABDCA”是X的一个子序列。

考虑最长公共子序列问题如何分解成子问题,设A= 0, 1,…, 1 ,B= 0, 1,…, 1 ,并Z= 0, 1,…, 1 为它们的最长公共子序列。不难证明有以下性质:

1) 如果 1= 1,则若 1= 1= 1,得 0, 1,…, 1 是

0, 1,…, 1 和 0, 1,…, 1 的一个最长公共子序列;

2) 如果 1≠ 1,则若 1≠ 1,得 0, 1,…, 1 是 0, 1,…, 2

和 0, 1,…, 1 的一个最长公共子序列;

3) 如果 1≠ 1,则若 1≠ 1,得 0, 1,…, 1 是 0, 1,…, 1

和 0, 1,…, 2 的一个最长公共子序列。

这样,在找A和B的公共子序列时,如有 1= 1,则进一步解决一个子问题,找 0, 1,…, 1 和 0, 1,…, 1 的一个最长公共子序列;如果 1≠ 1,则要解决两个子问题,找出 0, 1,…, 2 和 0, 1,…, 1 的一个最长公共子序列和找出 0, 1,…, 1 和 0, 1,…, 2 的一个最长公共子序列,再取两者中较长者作为A和B的最长公共子序列。

引进一个二维数组c ,用c 记录 与 的LCS 的长度,b 记录 c ,是通过哪一个子问题的值求得的,以决定搜索的方向。

我们是自底向上进行递推计算,那么在计算c 之前,c 1 1 ,c 与c 1 均已计算出来。此时我们根据 = 还是 ≠ ,就可以计算出c 。

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email