您好,登錄后才能下訂單哦!
這篇文章主要介紹如何使用python實(shí)現(xiàn)最長(zhǎng)公共子序列,文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
1.找出最優(yōu)解的性質(zhì),并刻劃其結(jié)構(gòu)特征
序列a共有m個(gè)元素,序列b共有n個(gè)元素,如果a[m-1]==b[n-1],那么a[:m]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度就是a[:m-1]和b[:n-1]的最長(zhǎng)公共子序列長(zhǎng)度+1;如果a[m-1]!=b[n-1],那么a[:m]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度就是MAX(a[:m-1]和b[:n]的最長(zhǎng)公共子序列長(zhǎng)度,a[:m]和b[:n-1]的最長(zhǎng)公共子序列長(zhǎng)度)。
2.遞歸定義最優(yōu)值
3.以自底向上大方式計(jì)算出最優(yōu)值
python代碼如下:
def lcs(a,b): lena=len(a) lenb=len(b) c=[[0 for i in range(lenb+1)] for j in range(lena+1)] flag=[[0 for i in range(lenb+1)] for j in range(lena+1)] for i in range(lena): for j in range(lenb): if a[i]==b[j]: c[i+1][j+1]=c[i][j]+1 flag[i+1][j+1]='ok' elif c[i+1][j]>c[i][j+1]: c[i+1][j+1]=c[i+1][j] flag[i+1][j+1]='left' else: c[i+1][j+1]=c[i][j+1] flag[i+1][j+1]='up' return c,flag def printLcs(flag,a,i,j): if i==0 or j==0: return if flag[i][j]=='ok': printLcs(flag,a,i-1,j-1) print(a[i-1],end='') elif flag[i][j]=='left': printLcs(flag,a,i,j-1) else: printLcs(flag,a,i-1,j) a='ABCBDAB' b='BDCABA' c,flag=lcs(a,b) for i in c: print(i) print('') for j in flag: print(j) print('') printLcs(flag,a,len(a),len(b)) print('')
運(yùn)行結(jié)果輸出如下:
4.根據(jù)計(jì)算最優(yōu)值得到的信息,構(gòu)造最優(yōu)解
上圖是運(yùn)行結(jié)果,第一個(gè)矩陣是計(jì)算公共子序列長(zhǎng)度的,可以看到最長(zhǎng)是4;第二個(gè)矩陣是構(gòu)造這個(gè)最優(yōu)解用的;最后輸出一個(gè)最優(yōu)解BCBA。
以上是“如何使用python實(shí)現(xiàn)最長(zhǎng)公共子序列”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對(duì)大家有幫助,更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。