最小公共字符串劃分問題的算法研究.pdf

1、字符串對比是計(jì)算機(jī)科學(xué)的一個基本問題，在基因組比較、文本處理與壓縮等實(shí)踐中有著廣泛應(yīng)用。近幾年，最小公共字符串劃分(MCSP)問題得到越來越多算法與復(fù)雜性研究者的關(guān)注。MCSP問題要求將字符串A與B劃分為公共子串，使劃分后A中的每一段都與B中某一段相對應(yīng)，且劃分得到的公共子串?dāng)?shù)目最少。在基因組比較研究中，須將兩個基因組分別看作字符串，計(jì)算兩個字符串的最小公共字符串劃分，從而建立兩個基因組中基因的對應(yīng)關(guān)系。
　　 要將字符串A和B

2、劃分為公共子串，A中每個字符出現(xiàn)的次數(shù)必須與B中此字符的出現(xiàn)次數(shù)相同。如果每個輸入字符串中的字符最多出現(xiàn)K次，就稱此問題為K-最小公共字符串劃分（k-MC SP）問題。2-MCSP問題已經(jīng)被證明是NP-hard，并且是APX-hard。目前最好的2-MCSP問題近似算法的近似度為1.1037，3-MCSP問題的近似度為4，k-MCSP問題近似度為（K）。
　　 本文首先討論以往MCSP問題研究結(jié)果，編程實(shí)現(xiàn)已有的貪心算法、Nov

3、el貪心算法、Educated貪心算法以及碰集算法，并進(jìn)行測試實(shí)驗(yàn)。在此基礎(chǔ)上，分析評測各個算法的優(yōu)缺點(diǎn)。
　　 然后針對K-最小公共字符串劃分問題，設(shè)計(jì)實(shí)現(xiàn)了一個新算法：定界貪心近似算法。定界貪心算法是在碰集算法的基礎(chǔ)上改進(jìn)而成，算法具有O（K）的算法近似度以及O（n）的時間復(fù)雜度。同時大量實(shí)驗(yàn)數(shù)據(jù)表明，定界貪心算法與碰集算法相比具有更好的計(jì)算性能。在實(shí)際測試實(shí)驗(yàn)中，未曾遇到定界貪心算法性能不如碰集算法性能好的實(shí)例。
　

4、　 最后設(shè)計(jì)實(shí)現(xiàn)了MCSP問題的最優(yōu)解算法與隨機(jī)回溯算法。令m代表輸入字符串中不同元素的個數(shù)，n代表字符串的長度，最優(yōu)解算法可以在O((k!)mn)的時間內(nèi)計(jì)算出K-最小公共字符串劃分問題的一個或者所有最優(yōu)解，對評估其他近似算法的實(shí)際運(yùn)行效果有著重要作用。隨機(jī)回溯算法具有很高的靈活性，既可以求出最優(yōu)解，也可以根據(jù)實(shí)際要求在短時間內(nèi)求出較好的解，兩種算法都具有較高的實(shí)用價值。最后，對最小公共字符串劃分問題進(jìn)行了總結(jié)與展望。本文主要創(chuàng)新工