多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

國(guó)內(nèi)最全I(xiàn)T社區(qū)平臺(tái) 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁(yè) > php開(kāi)源 > 綜合技術(shù) > 動(dòng)態(tài)規(guī)劃 最長(zhǎng)公共子序列 過(guò)程圖解

動(dòng)態(tài)規(guī)劃 最長(zhǎng)公共子序列 過(guò)程圖解

來(lái)源:程序員人生   發(fā)布時(shí)間:2016-06-29 09:42:00 閱讀次數(shù):7658次

1.基本概念

      首先需要科普1下,最長(zhǎng)公共子序列(longest common sequence)和最長(zhǎng)公共子串(longest common substring)不是1回事兒。甚么是子序列呢?即1個(gè)給定的序列的子序列,就是將給定序列中零個(gè)或多個(gè)元素去掉以后得到的結(jié)果。甚么是子串呢?給定串中任意個(gè)連續(xù)的字符組成的子序列稱(chēng)為該串的子串。給1個(gè)圖再解釋1下:


       如上圖,給定的字符序列: {a,b,c,d,e,f,g,h},它的子序列示例: {a,c,e,f} 即元素b,d,g,h被去掉后,保持原本的元素序列所得到的結(jié)果就是子序列。同理,{a,h},{c,d,e}等都是它的子序列。
       它的字串示例:{c,d,e,f} 即連續(xù)元素c,d,e,f組成的串是給定序列的字串。同理,{a,b,c,d},{g,h}等都是它的字串。

        這個(gè)問(wèn)題說(shuō)明白后,最長(zhǎng)公共子序列(以下都簡(jiǎn)稱(chēng)LCS)就很好理解了。
給定序列s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2},s1和s2的相同子序列,且該子序列的長(zhǎng)度最長(zhǎng),即是LCS。
s1和s2的其中1個(gè)最長(zhǎng)公共子序列是 {3,4,6,7,8}

2.動(dòng)態(tài)計(jì)劃

       求解LCS問(wèn)題,不能使用暴力搜索方法。1個(gè)長(zhǎng)度為n的序列具有 2的n次方個(gè)子序列,它的時(shí)間復(fù)雜度是指數(shù)階,太恐怖了。解決LCS問(wèn)題,需要借助動(dòng)態(tài)計(jì)劃的思想。
       動(dòng)態(tài)計(jì)劃算法通經(jīng)常使用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類(lèi)問(wèn)題中,可能會(huì)有許多可行解。每個(gè)解都對(duì)應(yīng)于1個(gè)值,我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)計(jì)劃算法與分治法類(lèi)似,其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題,先求解子問(wèn)題,然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是,合適于用動(dòng)態(tài)計(jì)劃求解的問(wèn)題,經(jīng)分解得到子問(wèn)題常常不是相互獨(dú)立的。若用分治法來(lái)解這類(lèi)問(wèn)題,則分解得到的子問(wèn)題數(shù)目太多,有些子問(wèn)題被重復(fù)計(jì)算了很屢次。如果我們能夠保存已解決的子問(wèn)題的答案,而在需要時(shí)再找出已求得的答案,這樣就能夠避免大量的重復(fù)計(jì)算,節(jié)省時(shí)間。我們可以用1個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案。不管該子問(wèn)題以后是不是被用到,只要它被計(jì)算過(guò),就將其結(jié)果填入表中。這就是動(dòng)態(tài)計(jì)劃法的基本思路。

3.特點(diǎn)分析

       解決LCS問(wèn)題,需要把原問(wèn)題分解成若干個(gè)子問(wèn)題,所以需要刻畫(huà)LCS的特點(diǎn)。

       設(shè)A=“a0,a1,…,am”,B=“b0,b1,…,bn”,且Z=“z0,z1,…,zk”為它們的最長(zhǎng)公共子序列。不難證明有以下性質(zhì):
       如果am=bn,則zk=am=bn,且“z0,z1,…,z(k⑴)”是“a0,a1,…,a(m⑴)”和“b0,b1,…,b(n⑴)”的1個(gè)最長(zhǎng)公共子序列;
       如果am!=bn,則若zk!=am,蘊(yùn)涵“z0,z1,…,zk”是“a0,a1,…,a(m⑴)”和“b0,b1,…,bn”的1個(gè)最長(zhǎng)公共子序列;
       如果am!=bn,則若zk!=bn,蘊(yùn)涵“z0,z1,…,zk”是“a0,a1,…,am”和“b0,b1,…,b(n⑴)”的1個(gè)最長(zhǎng)公共子序列。

       有些同學(xué),1看性質(zhì)就容易暈菜,所以我給出1個(gè)圖來(lái)讓這些同學(xué)理解1下:


       以我在第1小節(jié)舉的例子(S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}),并結(jié)合上圖來(lái)講:

       假設(shè)S1的最后1個(gè)元素 與 S2的最后1個(gè)元素相等,那末S1和S2的LCS就等于 {S1減去最后1個(gè)元素} 與 {S2減去最后1個(gè)元素} 的 LCS  再加上 S1和S2相等的最后1個(gè)元素。

       假設(shè)S1的最后1個(gè)元素 與 S2的最后1個(gè)元素不等(本例子就是屬于這類(lèi)情況),那末S1和S2的LCS就等于 : {S1減去最后1個(gè)元素} 與 S2 的LCS, {S2減去最后1個(gè)元素} 與 S1 的LCS 中的最大的那個(gè)序列。

4.遞歸公式

        第3節(jié)說(shuō)了LCS的特點(diǎn),我們可以發(fā)現(xiàn),假定我需要求 a1 ... am 和 b1 .. b(n⑴)的LCS 和 a1 ... a(m⑴) 和 b1 .. bn的LCS,1定會(huì)遞歸地并且重復(fù)地把如a1... a(m⑴) 與 b1 ... b(n⑴) 的 LCS 計(jì)算幾次。所以我們需要1個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄中間結(jié)果,避免重復(fù)計(jì)算。

        假定我們用c[i,j]表示Xi 和 Yj 的LCS的長(zhǎng)度(直接保存最長(zhǎng)公共子序列的中間結(jié)果不現(xiàn)實(shí),需要先借助LCS的長(zhǎng)度)。其中X = {x1 ... xm},Y ={y1...yn},Xi = {x1 ... xi},Yj={y1... yj}。可得遞歸公式以下:

         

5.計(jì)算LCS的長(zhǎng)度

       這里我不打算貼出相應(yīng)的代碼,只想把這個(gè)進(jìn)程說(shuō)明白。還是以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}為例。我們借用《算法導(dǎo)論》中的推導(dǎo)圖:


         圖中的空白格子需要填上相應(yīng)的數(shù)字(這個(gè)數(shù)字就是c[i,j]的定義,記錄的LCS的長(zhǎng)度值)。填的規(guī)則根據(jù)遞歸公式,簡(jiǎn)單來(lái)講:如果橫豎(i,j)對(duì)應(yīng)的兩個(gè)元素相等,該格子的值 = c[i⑴,j⑴] + 1。如果不等,取c[i⑴,j] 和 c[i,j⑴]的最大值。首先初始化該表:

         

          然后,1行1行地從上往下填:

         

          S1的元素3 與 S2的元素3 相等,所以 c[2,1] = c[1,0] + 1。繼續(xù)填充:

          

            S1的元素3 與 S2的元素5 不等,c[2,2] =max(c[1,2],c[2,1]),圖中c[1,2] 和 c[2,1] 背風(fēng)景為淺黃色。

            繼續(xù)填充:

            

            

             

               中間幾行填寫(xiě)規(guī)則不變,直接跳到最后1行:

              

                至此,該表填完。根據(jù)性質(zhì),c[8,9] = S1 和 S2 的 LCS的長(zhǎng)度,即為5。

6.構(gòu)造LCS

       本文S1和S2的最LCS其實(shí)不是只有1個(gè),本文其實(shí)不是側(cè)重講輸出兩個(gè)序列的所有LCS,只是介紹如何通過(guò)上表,輸出其中1個(gè)LCS。

       我們根據(jù)遞歸公式構(gòu)建了上表,我們將從最后1個(gè)元素c[8][9]倒推出S1和S2的LCS。

       c[8][9] = 5,且S1[8] != S2[9],所以倒推回去,c[8][9]的值來(lái)源于c[8][8]的值(由于c[8][8] > c[7][9])。

       c[8][8] = 5,  且S1[8] = S2[8], 所以倒推回去,c[8][8]的值來(lái)源于 c[7][7]。

       以此類(lèi)推,如果遇到S1[i] != S2[j] ,且c[i⑴][j] = c[i][j⑴] 這類(lèi)存在分支的情況,這里請(qǐng)都選擇1個(gè)方向(以后遇到這樣的情況,也選擇相同的方向)。

       第1種結(jié)果為:

       

          這就是倒推回去的路徑,棕色方格為相等元素,即LCS = {3,4,6,7,8},這是其中1個(gè)結(jié)果。

          如果如果遇到S1[i] != S2[j] ,且c[i⑴][j] = c[i][j⑴] 這類(lèi)存在分支的情況,選擇另外一個(gè)方向,會(huì)得到另外一個(gè)結(jié)果。

          

           即LCS ={3,5,7,7,8}。

7.關(guān)于時(shí)間復(fù)雜度

        構(gòu)建c[i][j]表需要Θ(mn),輸出1個(gè)LCS的序列需要Θ(m+n)。


          本文內(nèi)容參考以下:

        【1】http://baike.baidu.com/link?url=iKrtEZXAQ3LeQLL7Z0HQWpy7EO7BZInUR17C63lAIDFBJ_COm8e3KmKVxQCD6DlOvji2F9W6achz49Z_anZCfa

        【2】《算法導(dǎo)論》第3版 15.4節(jié)


        注意:
        如您發(fā)現(xiàn)本文檔中有明顯毛病的地方,
        或您發(fā)現(xiàn)本文檔中援用了他人的資料而未進(jìn)行說(shuō)明時(shí),請(qǐng)聯(lián)系我進(jìn)行更正。
        轉(zhuǎn)載或使用本文檔時(shí),請(qǐng)作醒目說(shuō)明。
        必要時(shí)請(qǐng)聯(lián)系作者,否則將追究相應(yīng)的法律責(zé)任。

        note:
        If you find this document with any error ,
        Or if you find any illegal citations , please contact me correct.
        Reprint or use of this document,Please explain for striking. 
        Please contact the author if necessary, or they will pursue the corresponding legal responsibility.



生活不易,碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 爱爱www在线观看视频高清 | 国内精品视频九九九九 | 国产亚洲欧美日韩在线一区 | 一区二区视频在线观看 | 三级不卡视频 | 精品国产一区二区三区19 | 岛国视频在线播放 | 亚洲精品成人a在线观看 | 特一级黄色毛片 | 国产日韩欧美精品一区二区三区 | 日本韩国一区二区三区 | 免费观看又污又黄网站日本 | 国产成人精品一区二区 | 国内交换一区二区三区 | 97精品国产综合久久久久久欧美 | 午夜男人网 | 中文字幕一区二区三区久久网站 | 欧美性另类高清 | 末发育娇小性色xxxxx视频 | 91精品一区二区三区在线播放 | 偷自视频区视频真实在线 | 国产福利一区二区在线观看 | 国产精品免费一区二区区 | 国产乱辈通伦影片在线播放 | 天堂网男人| 国产欧美成人不卡视频 | 久久成人视 | 尤物在线看 | 羞羞免费网站 | 久久免费精品一区二区 | 波多野结衣一区免费作品 | 色操网 | 欧美另类视频一区二区三区 | 国产精品日韩欧美亚洲另类 | 欧美成人性色 | 国产亚洲欧美成人久久片 | 麻豆国产96在线 | 日韩 | 亚洲精品中文字幕一区在线 | 91丨九色丨首页在线观看 | 欧美一区二区三区精品国产 | 三级视频在线 |