亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        最長(zhǎng)遞增子序列問(wèn)題研究

        2019-10-08 08:34:58喬明澤宋傳鳴
        軟件 2019年7期
        關(guān)鍵詞:動(dòng)態(tài)規(guī)劃算法

        喬明澤 宋傳鳴

        摘? 要: 本文采用分治策略和動(dòng)態(tài)規(guī)劃策略探討了最長(zhǎng)遞增子序列問(wèn)題的兩種解法,并分析了算法的計(jì)算復(fù)雜度。結(jié)果表明,本文算法的時(shí)間復(fù)雜度和空間復(fù)雜度分別為O(nlogn)和O(n)。

        關(guān)鍵詞: 最長(zhǎng)遞增子序列;分治;動(dòng)態(tài)規(guī)劃;算法

        中圖分類(lèi)號(hào): TP391? ? 文獻(xiàn)標(biāo)識(shí)碼: A? ? DOI:10.3969/j.issn.1003-6970.2019.07.005

        本文著錄格式:?jiǎn)堂鳚?,宋傳鳴. 最長(zhǎng)遞增子序列問(wèn)題研究[J]. 軟件,2019,40(7):3134

        【Abstract】: By employing the divide-and-conquer and dynamic programming strategies, this paper discusses two algorithms of the longest increasing subsequence problem. The computational complexity of two algorithms was subsequently analyzed. The analysis results show that the time complexity and spatial complexity of two proposed algorithms achieve O(nlogn) and O(n), respectively.

        【Key words】: Longest increasing subsequence; Divide-and-conquer; Dynamic programming; Algorithm

        0? 引言

        最長(zhǎng)遞增子序列(Longest Increasing Subsequence, LIS)問(wèn)題是計(jì)算機(jī)算法學(xué)、隨機(jī)矩陣?yán)碚?、表示理論、組合數(shù)學(xué)和生物信息學(xué)領(lǐng)域的典型問(wèn)題之一[1],其問(wèn)題描述如下:設(shè)L是一個(gè)有n個(gè)元素的序列 。若L存在某子序列? ? 滿(mǎn)足? ?,則稱(chēng)l是L的一個(gè)遞增子序列,并稱(chēng)m為遞增子序列l(wèi)的長(zhǎng)度。最長(zhǎng)遞增子序列問(wèn)題就是要求序列L的一個(gè)長(zhǎng)度最長(zhǎng)的遞增子序列。

        目前,最長(zhǎng)遞增子序列問(wèn)題已經(jīng)被廣泛研究。文獻(xiàn)[2,3]分別給出了該問(wèn)題的動(dòng)態(tài)規(guī)劃解法;文獻(xiàn)[1]首先將LIS問(wèn)題轉(zhuǎn)化為最長(zhǎng)公共子序列問(wèn)題,再利用動(dòng)態(tài)規(guī)劃算法求解;文獻(xiàn)[4]則將LIS問(wèn)題轉(zhuǎn)化為圖的最長(zhǎng)路徑問(wèn)題進(jìn)行動(dòng)態(tài)規(guī)劃求解。上述算法的計(jì)算時(shí)間復(fù)雜度均為O(n2)。在總結(jié)和分析現(xiàn)有算法不足之后,文獻(xiàn)[1]利用數(shù)組鏈表和二分查找改進(jìn)了典型動(dòng)態(tài)規(guī)劃算法中的查找操作,從而將算法的時(shí)間復(fù)雜度降低到O(nlogn),但是其輔助空間較大,且算法較為復(fù)雜。另外,國(guó)內(nèi)尚鮮見(jiàn)關(guān)于最長(zhǎng)遞增子序列問(wèn)題的詳細(xì)實(shí)現(xiàn)過(guò)程且其時(shí)間復(fù)雜度達(dá)到O(nlogn)的研究資料。

        本文利用分治策略和動(dòng)態(tài)規(guī)劃策略[5]設(shè)計(jì)了兩種最長(zhǎng)遞增子序列問(wèn)題的O(nlogn)復(fù)雜度算法。分治解法的基本思路是將長(zhǎng)度為n的序列分解為長(zhǎng)度較短的子序列,再遞歸求解這些子序列的LIS,最后將各個(gè)子序列的解合并成原序列的解;動(dòng)態(tài)規(guī)劃解法的基本思路與分治法類(lèi)似,不同之處在于前者用一個(gè)數(shù)組來(lái)記錄那些已解決的子問(wèn)題的答案,從而避免重復(fù)子問(wèn)題的計(jì)算,降低時(shí)間復(fù)雜度。

        本文內(nèi)容安排如下:第1節(jié)討論最長(zhǎng)遞增子序列問(wèn)題的分治解法;第2節(jié)首先證明最長(zhǎng)遞增子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì),然后詳細(xì)論述其動(dòng)態(tài)規(guī)劃解法;第3節(jié)總結(jié)全文。

        1? 最長(zhǎng)遞增子序列的分治解法

        分治是一種簡(jiǎn)單、直接的算法設(shè)計(jì)策略,其基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的、互相獨(dú)立的子問(wèn)題且與原問(wèn)題相同。遞歸計(jì)算每個(gè)子問(wèn)題,然后將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解[5]。依據(jù)此思想,下面討論本文的求解思路。

        1.1? LIS問(wèn)題分治解法的主要思路

        首先,將序列L大致平均分成左、右兩個(gè)子序列L1和L2,遞歸求這兩個(gè)子序列的最長(zhǎng)遞增子序列。

        其次,以L(fǎng)1的最長(zhǎng)遞增子序列為基礎(chǔ)向L2序列擴(kuò)展,得到一個(gè)遞增子序列a。

        再次,以L(fǎng)2的最長(zhǎng)遞增子序列為基礎(chǔ)向L1序列擴(kuò)展,得到一個(gè)遞增子序列b。

        最后,序列L的最長(zhǎng)遞增子序列即為a、b中的較長(zhǎng)者。

        對(duì)于L1和L2的最長(zhǎng)遞增子序列求解,由于其形式與原問(wèn)題完全相同,解法與L的最長(zhǎng)遞增子序列解法一致。故此,為了保證分治算法具有較低的時(shí)間復(fù)雜度,關(guān)鍵環(huán)節(jié)是如何高效地將L1和L2的解合并為L(zhǎng)的解。

        1.2? 子問(wèn)題解的合并

        將原序列 劃分成兩個(gè)相互獨(dú)立的子序列, 、? ?,然后遞歸求得BL和BR的最長(zhǎng)遞增子序列bl和br,然后將bl和br擴(kuò)展為L(zhǎng)的最長(zhǎng)遞增子序列sub。

        顯然,這里劃分的兩個(gè)子序列BL和BR沒(méi)有重疊部分,是相互獨(dú)立的,即具有子問(wèn)題不重疊性質(zhì)。對(duì)于子問(wèn)題解的合并,給出下列合并思路。

        1: bl←new int[(last-first)/2+1]

        2: br←new int[(last-first)/2+1]

        3: l ←LIS_DC(first,mid,bl)

        4: r ←LIS_DC(mid,last,br)

        //以左子數(shù)組的最長(zhǎng)遞增子序列為基礎(chǔ),向右子數(shù)組擴(kuò)展,得到一個(gè)遞增子序列

        5: for i←0 to l

        6: sub[i]←bl[i]

        7: end for

        8: i←l-1 ,? p←i+1 ,? sub[p]←MAX

        9:? for k←mid to last? ? ? //向右擴(kuò)展的區(qū)域[mid,last)

        10:? ? if sub[i]

        11:? ? ++i ,? p←i+1 ,? sub[p]←a[k]

        12:? ? else if sub[i]a[k] && sub[i]

        13:? ? sub[p]←a[k]

        14: else if sub[i]a[k] && sub[i]>a[k] && sub[i-1]

        15:? ? sub[i]←a[k] ,? sub[p]←MAX

        16:? end if

        17:? end for

        18:? if sub[p]=MAX then

        19:? --p

        //以右子數(shù)組的最長(zhǎng)遞增子序列為基礎(chǔ),向左子數(shù)組擴(kuò)展,得到一個(gè)遞增子序列

        20:? subr←new int[(last-first)/2+1]

        21:? j←0,? subr[j]←br[0],? q←j+1,? subr[q]←-MAX

        22:? for k←mid-1 to first? //向左擴(kuò)展的區(qū)域[first,mid)

        23:? ? ?if subr[j]>subr[q] && subr[q]>a[k] then

        24:? ? ++j ,? q←j+1 ,? subr[q]←a[k]

        25:? ? ?else if subr[j]>subr[q]&&subr[q]a[k]

        26:? ? ? ? ?subr[q]←a[k]

        27:? ? ?end if

        28:? end for

        29:? if subr[q]= -MAX then

        30:? --q

        //合并,數(shù)組sub即為求得的L的最長(zhǎng)遞增子序列

        31:? if p+1>=q+r then

        32:? s←p+1

        33:? else s←q+r

        34:? for k←q to 0

        35: ? ? sub[i++]←subr[k]

        36: for k←0 to r

        37: ? ? sub[i++]←br[k]

        1.3? LIS問(wèn)題的分治解法步驟

        根據(jù)上文的分析,下面給出本文提出的LIS問(wèn)題的分治解法步驟。

        算法輸入:數(shù)組a,數(shù)組sub,起始下標(biāo)first和終止下標(biāo)last

        算法輸出:最長(zhǎng)遞增子序列及其長(zhǎng)度

        算法LIS_DC (a,sub,first,last)

        1:? ?if last-first=2 then? ? //遞歸結(jié)束的基準(zhǔn)條件

        2: ? if a[first]>a[first+1] then

        3: ? ? ?sub[0]←a[first+1],? return 1

        4: ? else

        5: ? ? ?sub[0]←a[first],? sub[1]←a[first+1],? return 2

        6: end if

        7: else if last-first=1 then

        8: ? sub[0]←a[first],? return 1

        9: end if

        10: mid←(first+last)/2

        11: l←LIS_DC(first,mid,bl)

        12: r←LIS_DC(mid,last,br)

        1.4? ?計(jì)算復(fù)雜度分析

        由于采用了二分法遞歸且遞歸函數(shù)中只存在一層循環(huán),所以該算法的時(shí)間復(fù)雜度T(n)=O(nlogn)。

        每次遞歸,當(dāng)前函數(shù)都大致開(kāi)辟i+2個(gè)sizeof(int)空間 ,所以總共大致開(kāi)辟了2(n-1)+2logn個(gè)sizeof(int)空間,即空間復(fù)雜度S(n)=O(n)。

        2? 最長(zhǎng)遞增子序列的動(dòng)態(tài)規(guī)劃解法

        動(dòng)態(tài)規(guī)劃是求解具有最優(yōu)子結(jié)構(gòu)性質(zhì)的最優(yōu)化問(wèn)題的有效算法設(shè)計(jì)策略之一,其基本思想是將規(guī)模為n的問(wèn)題分解成若干個(gè)子問(wèn)題,這些子問(wèn)題往往不是互相獨(dú)立的、而是重疊的,且滿(mǎn)足最優(yōu)子結(jié)構(gòu);每求解出一個(gè)子問(wèn)題,就將其答案保存到數(shù)組中,從而避免重疊子問(wèn)題的多次計(jì)算;最后以自底向上的方式從子問(wèn)題的解得到原問(wèn)題的解[5]。

        2.1? 最長(zhǎng)遞增子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)

        定理1 設(shè)序列L的最長(zhǎng)遞增子序列為? ? (1

        證明? 假設(shè)b不是subL在 條件下的最長(zhǎng)遞增子序列,則存在另一個(gè)subL的遞增子序列? 1i,? ?,那么可以構(gòu)造 ,因?yàn)閖>i,所以l2子序列的長(zhǎng)度大于l1子序列的長(zhǎng)度,l2才是L的最長(zhǎng)遞增子序列。這與l1是L的最長(zhǎng)遞增子序列相矛盾。因此,假設(shè)不成立,即b是 subL在 條件下的最長(zhǎng)遞增子序列。證畢。

        由上述定理可知,最長(zhǎng)遞增子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

        2.2? 一般解法

        依據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì),可以得到最長(zhǎng)遞增子序列問(wèn)題的解的遞歸表達(dá)式為:

        (1)

        由此即可獲得下文的最長(zhǎng)遞增子序列問(wèn)題的動(dòng)態(tài)規(guī)劃解法。

        每個(gè)數(shù)據(jù)元素采用的數(shù)據(jù)結(jié)構(gòu)為:

        struct node

        {

        DataType data; //結(jié)點(diǎn)的值

        int pre; //結(jié)點(diǎn)的前序

        unsigned int count; //以該結(jié)點(diǎn)為結(jié)尾的遞增子序列的長(zhǎng)度

        };

        算法輸入:保存在node a[M]數(shù)組中的n個(gè)元素

        算法輸出:最長(zhǎng)遞增子序列及其長(zhǎng)度

        算法LIS_DM1 (a)

        0:? ? 初始化數(shù)組a,t←0

        1:? ? for i←1 to n

        2:? ? ? max←0

        3:? ? ? for j←0 to i-1

        4: ? ? ?if a[j].data

        5: ? ? ? ? ?max←a[j].count, k←j? ?//max記錄著a[0,..,i-1]中count最大的值;

        //k記錄著max對(duì)應(yīng)a[0,..,i-1]的下標(biāo);

        6: ? ? ?end if

        7: ? ? end for

        8: ? ? if max=0 then

        9: ? ? ? goto 1

        10:? ? ?end if

        11:? ? ?a[i].count←max+1, a[i].pre←k

        12:? ? ?if a[i].count>t then

        13: ? t=a[i].count? ?//t記錄a[0,…,n-1]中count最大的值

        14:? ? ?end if

        15:? ?end for

        16:? ?for i←0 to n

        17:? ? ?if a[i].count=t then

        18: ? output 以a[i]結(jié)尾的最長(zhǎng)遞增子序列

        19:? ? ?end if

        20:? ?end for

        2.3? 基于二分查找和鏈棧的動(dòng)態(tài)規(guī)劃解法

        由公式⑴和算法LIS_DM1可知,計(jì)算每個(gè)l(i)時(shí)都需要尋找滿(mǎn)足 條件的最大的l(j)。由于是l(j)無(wú)序的,順序查找需耗費(fèi)O(n)的時(shí)間復(fù)雜度。若能利用特殊的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)有序的l(j),即可用二分查找方法完成最大l(j) 的搜索,從而將時(shí)間復(fù)雜度從O(n)降低到O(logn)?;谶@種思路,本文設(shè)計(jì)了一種基于二分查找和鏈棧的動(dòng)態(tài)規(guī)劃解法。

        每個(gè)數(shù)據(jù)元素采用的數(shù)據(jù)結(jié)構(gòu)為:

        struct Element

        {

        DataType d;? ? ?//結(jié)點(diǎn)的值

        Element* pre;? ?//d的前續(xù)坐標(biāo),即在上一層鏈表中某節(jié)點(diǎn)

        Element* next;

        };

        Element? *s;? ? ? //s作棧

        int Top=0;? //棧頂 棧中元素在s[0,Top)中

        算法輸入:保存在node a[M]數(shù)組中的n個(gè)元素

        算法輸出:最長(zhǎng)遞增子序列及其長(zhǎng)度

        算法LIS_DM2(a)

        0:? 初始化棧s,棧頂Top←0

        1:? for i←0 to n-1

        2:? ? s[i].q←NULL

        3:? end for

        4:? for i←0 to n-1

        5:? ? l←0,mm←Top,h←Top,flag←false

        6:? ? do while l<=h

        7:? ? ? ?m←(l+h)/2

        8:? ? ? ?if s[m].q=NULL then ? //s[m].q指向的鏈表無(wú)元素

        9:? ? ? ? ? break

        10:? ? ? end if

        11:? ? ? if s[m].q→d>a[i] then? ? //s[m].qt→d是s[m].q鏈表中的最小元素

        12:? ? ? ? mm←m,h←m-1? ? ? //mm保存著最近一次s[m].q→d>a[i] 時(shí)m的值

        13:? ? ? else if s[m].q→d

        14:? ? ? ? ?l←m+1

        15:? ? ? else

        16:? ? ? ? ?flag←true,break

        17:? ? ? end if

        18:? ?end do

        19:? ?if flag=true

        20:? ? ?goto Step 7

        21:? ?end if

        22:? ?將a[i]加入到s[mm].q指向的鏈表中

        23:? end for

        24:? rprint(s[Top-1].q);? //輸出最長(zhǎng)遞增子序列

        2.4? 計(jì)算復(fù)雜度分析

        一般解法中,LIS_DM1算法的計(jì)算量主要集中在二重循環(huán)階段,其時(shí)間復(fù)雜度為T(mén)(n)=O(n2);另外,上述算法采用了1個(gè)包含n個(gè)元素的一維數(shù)組,故其空間復(fù)雜度為S(n)=O(n)。

        改進(jìn)動(dòng)態(tài)規(guī)劃解法,相對(duì)于上述的一般解法而言,在內(nèi)層循環(huán)中采用二分查找法,這樣時(shí)間復(fù)雜度就從O(n2)降到O(nlogn)。但是需要多消耗些空間用于保存數(shù)據(jù),LIS_DM2算法運(yùn)用棧和鏈表輔助存儲(chǔ),棧中元素有序,所以能使用二分查找,提高效率。具體分析如下。

        因?yàn)閟[0].q→d,s[1].q→d,s[2].q→d,s[3].q→d,...,s[Top-2].q→d,s[Top-1].q→d是遞增有序的,所以可以采用二分查找法查找mm,使得s[0].q→d,s[1].q→d,s[2].q→d,s[3].q→d,...,s[mm-2].q→d,s[mm-1].q→d都小于a[i],而從s[mm].q→d開(kāi)始到s[Top-1].q→d都大于a[i]。這樣a[i]用頭插法添加到s[mm].q指向的鏈表中。

        故其時(shí)間復(fù)雜度為T(mén)(n)=O(nlogn),空間復(fù)雜度為S(n)=O(n)。

        3? 結(jié)束語(yǔ)

        最長(zhǎng)遞增子序列問(wèn)題是計(jì)算機(jī)算法設(shè)計(jì)與分析中的典型問(wèn)題,在數(shù)學(xué)、物理等學(xué)科中亦有廣泛應(yīng)用。本文采用分治和動(dòng)態(tài)規(guī)劃策略設(shè)計(jì)了兩種最長(zhǎng)遞增子序列求解算法,并給出了詳細(xì)的實(shí)現(xiàn)步驟,其時(shí)間復(fù)雜度均為O(nlogn),空間復(fù)雜度為O(n)。

        參考文獻(xiàn)

        [1] 嚴(yán)華云, 李剛, 張建宏. 生物信息挖掘中LIS算法研究[J].計(jì)算機(jī)應(yīng)用研究, 2009, 26(1): 62-63, 6.

        [2] SKIENA Steven S. The algorithm design manual[M]. 第2版 北京:清華大學(xué)出版社, 2009.

        [3] 《編程之美》小組. 編程之美——微軟技術(shù)面試心得[M]. 北京: 電子工業(yè)出版社, 2012: 194-198.

        [4] DASGUPTA S., PAPADIMITRIOU C., VAZIRANI U..算法概論[M]. 錢(qián)楓, 鄒恒明, 譯. 北京: 機(jī)械工作出版社, 2012: 157-159.

        [5] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M]. 第4版. 北京: 電子工業(yè)出版社, 2012.

        猜你喜歡
        動(dòng)態(tài)規(guī)劃算法
        基于MapReduce的改進(jìn)Eclat算法
        Travellng thg World Full—time for Rree
        進(jìn)位加法的兩種算法
        算法初步兩點(diǎn)追蹤
        基于增強(qiáng)隨機(jī)搜索的OECI-ELM算法
        ACM—ICPC競(jìng)賽趣味學(xué)習(xí)系統(tǒng)設(shè)計(jì)
        大學(xué)生經(jīng)濟(jì)旅游優(yōu)化設(shè)計(jì)模型研究
        一種改進(jìn)的整周模糊度去相關(guān)算法
        動(dòng)態(tài)規(guī)劃最優(yōu)控制在非線(xiàn)性系統(tǒng)中的應(yīng)用
        動(dòng)態(tài)規(guī)劃案例教學(xué)設(shè)計(jì)
        国产风骚主播视频一区二区| 免费无码av片在线观看| 国产精品一区二区电影| AV无码专区亚洲AVL在线观看| 手机av在线播放网站| 国产猛男猛女超爽免费视频| 麻豆精品传媒一二三区| 综合无码综合网站| 综合人妻久久一区二区精品| 爆操丝袜美女在线观看| 日本最大色倩网站www| 99er视频| 女同久久精品国产99国产精| 麻豆精品一区二区av白丝在线| 一本无码av中文出轨人妻| 不卡视频一区二区三区| 综合人妻久久一区二区精品 | 国产精品性色av麻豆| 国产精品精品自在线拍| 乱中年女人伦av| 性色av成人精品久久| 日本系列中文字幕99| 伊人久久大香线蕉亚洲五月天| 国产午夜无码视频免费网站| 一区二区三区人妻在线| 红桃av一区二区三区在线无码av | 久久久久久av无码免费网站下载| 天天摸日日摸狠狠添| avtt一区| 三上悠亚亚洲精品一区| 在线成人爽a毛片免费软件| 中文字幕第1页中文字幕在| 久久精品成人一区二区三区蜜臀| 久久久久亚洲av无码a片| 人人狠狠综合久久亚洲| 国产精品福利久久香蕉中文| 国产精品成人一区二区在线不卡| 99精品国产一区二区三区不卡| 欧美视频在线观看一区二区| 少妇激情一区二区三区| av无码国产精品色午夜|