怎么样在服务器上建设网站,2012年网站设计方法,专业建站源码,成都学习网站建设一、最长公共子序列问题 1、问题概念 一个序列的子序列是在该序列中删去若干元素后得 到的序列。 例如#xff1a;ABCD”和“BDF”都是“ABCDEFG”的子序列。 最长公共子序列(LCS) 问题: 给定两个序列X和Y#xff0c;求X和Y长度最大的公共子字列。 例:XABBCBDE”… 一、最长公共子序列问题 1、问题概念 一个序列的子序列是在该序列中删去若干元素后得 到的序列。 例如ABCD”和“BDF”都是“ABCDEFG”的子序列。 最长公共子序列(LCS) 问题: 给定两个序列X和Y求X和Y长度最大的公共子字列。 例:XABBCBDE”YDBBCDB”LCS(XY)BBCD 应用场景:字符串相似度比对 2、问题求解思路 1问题思考 思考: 暴力穷举法的时间复杂度是多少? 序列中的每一个值都有两种选择被选择或者不被选择因此一个长度为n的序列其子序列为种。求解长度为n和长度为m的序列的公共子序列对比和个子序列之间的关系是否相同因此时间复杂度为O()。 思考: 最长公共子序列是否具有最优子结构性质? 有见解最优子结构 2最优子结构 LCS的最优子结构令X(......和Y(......)为两个序列Z(......)为X和Y的任意 LCS。 如果 则 且是和的一个LCS。 例如序列ABCD和ABD其LCS为ABD此时 D可见AB是ABC和AB的LCS。 如果且意味着Z是和Y的一个LCS。 例如序列ABCD和ABC其LCS为ABC此时即D与C不相等则为ABC可见ABC是ABC和ABC的LCS。 如果且意味着Z是X和的一个LCS。 例如序列ABC和ACD其LCS为AC此时即D与C不相等则为AC可见AC是ABC和AC的LCS。 示例如下 要求aABCBDAB与bBDCABA的LCS 由于最后一位B“≠A” 因此LCS(a,b)应该来源于LCS(a[:-1],b)与LCS(a,b[:-1])中更大的那一个 3问题递推式 1递推式推理说明 结合最优子结构的定理可以得到以上的图。 举例解析 x0都是空列表y0也是空列表因此与x0或者y0的LCS一定是0。 序列BDC和序列AC ! A则LCS来源与LCS([BDC],[ ])和LCS([BD],[A])中图中可看出两者都为0即LCS([BDC], [A])的左边和上边的位置。 序列BDCA和序列AA A则A一定是两个序列的LCS中的一个元素且LCS([BDC], [A])加上元素A就是LCS([BDCA], [A])。查看可知LCS([BDC], [A]) 0所以LCS([BDCA], [A]) 0 1(元素A)。 剩余的同理。 2递推式 c[i,j]表示和的LCS长度 二、最长公共子序问题代码实现 1、最长公共子序长度求解
def lcs_length(x,y): # 公共子序列长度xy: 字符串、列表等序列m len(x) # x序列长度n len(y) # y序列长度c [[0 for i in range(n 1)] for _ in range(m1)] # 创建m行n列二维数组初始值为0 for i in range(1, m1): # 按数组的行求x0都为0不用求所以从1开始for j in range(1, n1): # 数组每行中的遍历y0都为0不用求if x[i - 1] y[j - 1]: # x[i-1]其实是字符串的i因为i0在二维列表中都是0不求解但是在字符串中仍需要从索引0遍历c[i][j] c[i-1][j-1] 1 # 递推式else: # xiyic[i][j] max(c[i-1][j],c[i][j-1]) # 递推式return c[m][n] # x和y的最后一个元素对比完二维数组的最后一位print(lcs_length(ABCBDAB, BDCABA)) 输出结果 4 2、最长公共子序的序列求解 动态规划 回溯算法搭配使用动态规划求解最优值回溯法推算出过程的解。 1动态规划求解并存储解-代码实现 # 动态规划求解存储解及解的计算过程
def lcs(x,y): # 求解并存储箭头方向xy为字符串、列表等序列m len(x) # x的长度n len(y) # y的长度c [[0 for i in range(n1)] for _ in range(m1)] # 二维数组初始值为0用于存储长度结果d [[0 for i in range(n1)] for _ in range(m1)] # 二维数组初始值为0用于存储箭头方向,1表示左上2表示上3表示左for i in range(1,m1): # 按行遍历二维数组for j in range(1,n1): # 每行的各数值遍历 c0j和ci0相关的值都为0所以均从1开始if x[i - 1] y[j - 1]: # xiyi的情况二维数组中ij0时都为0已经确定但字符串xy仍需从0开始遍历c[i][j] c[i - 1][j - 1] 1 # 递推式d[i][j] 1 # 箭头方向左上方elif c[i][j - 1] c[i - 1][j]: # 递推式选择更大的c[i][j] c[i][j - 1]d[i][j] 3 # 箭头左边else: # c[i-1][j] c[i][j-1]c[i][j] c[i - 1][j]d[i][j] 2 # 箭头上方return c[m][n], dc, d lcs(ABCBDAB, BDCABA)
for _ in d:print(_) 输出结果 [0, 0, 0, 0, 0, 0, 0]
[0, 2, 2, 2, 1, 3, 1]
[0, 1, 3, 3, 2, 1, 3]
[0, 2, 2, 1, 3, 2, 2]
[0, 1, 2, 2, 2, 1, 3]
[0, 2, 1, 2, 2, 2, 2]
[0, 2, 2, 2, 1, 2, 1]
[0, 1, 2, 2, 2, 1, 2] 2回溯算法的应用-代码实现 # 动态规划求解存储解及解的计算过程
def lcs(x,y): # 求解并存储箭头方向xy为字符串、列表等序列m len(x) # x的长度n len(y) # y的长度c [[0 for i in range(n1)] for _ in range(m1)] # 二维数组初始值为0用于存储长度结果d [[0 for i in range(n1)] for _ in range(m1)] # 二维数组初始值为0用于存储箭头方向,1表示左上2表示上3表示左for i in range(1,m1): # 按行遍历二维数组for j in range(1,n1): # 每行的各数值遍历 c0j和ci0相关的值都为0所以均从1开始if x[i - 1] y[j - 1]: # xiyi的情况二维数组中ij0时都为0已经确定但字符串xy仍需从0开始遍历c[i][j] c[i - 1][j - 1] 1 # 递推式d[i][j] 1 # 箭头方向左上方elif c[i][j - 1] c[i - 1][j]: # 递推式选择更大的c[i][j] c[i][j - 1]d[i][j] 3 # 箭头左边else: # c[i-1][j] c[i][j-1]c[i][j] c[i - 1][j]d[i][j] 2 # 箭头上方return c[m][n], d# 回溯算法
def lcs_trackback(x,y): # 最长公共子序列的序列c, d lcs(x, y) # c长度d箭头方向i len(x) # x的长度j len(y) # y的长度res [] # 结果列表while i 0 and j 0 : # 序列x和y还有值未比对任何一个序列为0了都不再继续if d[i][j] 1: # 箭头左上方 —— 匹配res.append(x[i - 1]) # 二维列表中i0时值为0但是序列x的值是从0开始遍历的i i - 1 # 位置移到左上位置j j - 1elif d[i][j] 2: # 箭头上方-不匹配i i - 1 # 位置往上移一格else: # dij 3 箭头左向j j - 1 # 位置往左移一格return .join(reversed(res)) # 列表翻转并将列表用连接成字符串print(lcs_trackback(ABCBDAB, BDCABA)) 结果输出 BCBA
