使用度量與分治方法分析和設(shè)計精確算法.pdf

1、申請上海交通大學(xué)碩士學(xué)位論文使用度量與分治方法分析和設(shè)計精確算法論文作者石磊學(xué)號1070339063指導(dǎo)教師傅育熙教授專業(yè)答辯日期計算機軟件與理論2010年1月19日使用度量與分治方法分析和設(shè)計精確算法摘要對于NP難問題來說，精確的指數(shù)時間算法是算法領(lǐng)域一個重要的研究課題，特別是在某些情況下近似算法難以滿足計算的需求。在設(shè)計這一類算法的時候，最常見的是DavisPutnam所提出的搜索樹算法，即分支約減算法。該方法通過將問題分解為子問題

2、并遞歸求解最終得到計算結(jié)果。為了提高算法的速度，研究者在設(shè)計分支約減算法的時候加入越來越復(fù)雜的約減規(guī)則，以使問題實例在分解前能夠盡量簡化，這導(dǎo)致算法的實現(xiàn)常常變得冗繁和困難。而與此同時，分支約減算法的分析方法卻并沒有大的改進，問題實例規(guī)模的測度往往比較簡單，這使得對算法時間復(fù)雜度的分析不夠精確，從而無法得到比較緊的算法運行時間上界。Fomin等人最近提出了一種稱為度量與分治(measureconquer)的技術(shù)，通過對問題實例規(guī)模的不同

3、組成部分加權(quán)來更精確的刻畫問題實例，以獲得對分支約減算法更準確的分析。本文以此為切入點，以最小支配集問題為例，全面介紹了度量與分治方法的概念、方法和算法分析過程。除此之外，本文還將度量與分治方法應(yīng)用在了分支約減算法的設(shè)計當中。論文的主要內(nèi)容包括:本文以最小集合覆蓋的分支約減算法為例，基于Fomin的分析系統(tǒng)闡釋了使用度量與分治方法設(shè)計加權(quán)度量、分析子問題規(guī)模、優(yōu)化權(quán)值以及獲得算法時間復(fù)雜度的具體過程，并證明了Groni的算法在使用多項式