最长公共子序列（动态规划）报告.doc_动态规划最长公共子序列实验报告,最长公共子序列动态规划实验报告资源-CSDN文库

算法设计与分析实验报告

需积分: 10 9 浏览量 2019-12-26 16:33:49 上传评论收藏 226KB DOC 举报

资源推荐

资源详情

资源评论

实验六：最长公共子数列（动态规划）报告

2017061111 李静娴

1．问题描述

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定

序列

X={ }

，则另一序列

Z={

1 2

, ,...,

m

z z z

}

是

X

的子序列是指存在一个严格递增

的下标序列

{ }

，使得对于所有

j=1,2,

…

,k

有

=

。例如，序列

Z={B,C,D,B}

是序列

X={A,B,C,B,D,A,B}

的子序列，相应的递增下标序列为

{2,3,5,7}

。给定两个序列

X

和

Y

，当另一

序列

Z

既是

X

的子序列又是

Y

的子序列时，称

Z

是序列

X

和

Y

的公共子序列。例如，若

X={

A,B,C,B,D,A,B}

和

Y={B,D,C,A,B,A}

，则序列

{B,C,A}

是

X

和

Y

的一个公共子序列，序列

{B,C,B,A}

也是

X

和

Y

的一个公共子序列。而且，后者是

X

和

Y

的一个最长公共子序列，因为

X

和

Y

没有长度大于

4

的公共子序列。给定两个序列

X={ }

和

Y={ }

，

要求找出

X

和

Y

的一个最长公共子序列。

2．实验目的

（1）熟悉动态规划算法，并学以致用

（2）熟练掌握最长公共子序列算法

3．实验原理

1.

问题解析：设

X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A}

。求

X

，

Y

的最长公共子序列最容易

想到的方法是穷举法。对

X

的多有子序列，检查它是否也是

Y

的子序列，从而确定它是否

为

X

和

Y

的公共子序列。由集合的性质知，元素为

m

的集合共有

2^m

个不同子序列，因此，

穷举法需要指数级别的运算时间。进一步分解问题特性，最长公共子序列问题实际上具有

最优子结构性质。



设序列

X={ }

和

Y={ }

的最长公共子序列为

Z={

1 2

, ,...,

m

z z z

}

。则有：



(1)

若，则，且是和的最长公共子序列。

(2)

若且，则

Z

是和

y

的最长公共子序列。

(3)

若且，则

Z

是

x

和的最长公共子序列。



其中，

={ }

，

={ }

，

Zk-1={ }

。

2.

递推关系：用

c[i][j]

记录序列

Xi

和

Yj

的最长公共子序列的长度。其中

={ }

，

={ }

。当

i=0

或

j=0

时，空序列是和的最长公共子序列。此时，

c[i]

[j]=0

；当

i,j>0

，

=

时，

c[i][j]=c[i-1][j-1]+1

；当

i,j>0

，

!=

时，

c[i][j]=max{c[i][j-1],c[i-1]

[j]}

，由此建立递推关系如下：

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

内容反馈

qq_42236488

粉丝: 4
资源: 17

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip