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

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

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

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