合取范式最大不全滿足與最大可滿足問題的局部搜索算法研究.pdf

1、算法是計(jì)算機(jī)科學(xué)中最核心的內(nèi)容，自從有計(jì)算機(jī)以來，它始終是這門學(xué)科的研究熱點(diǎn)內(nèi)容。就在計(jì)算機(jī)科學(xué)分支眾多的今天，每個(gè)分支的基礎(chǔ)還是算法的研究。
　　 合取范式最大可滿足性問題（SAT)是算法中最經(jīng)典的問題之一，也是最早被證明為NPC的問題。其它問題往往以SAT問題做為參照，通過規(guī)約等方法來證明是NP問題。NPC問題的算法復(fù)雜性是指數(shù)級(jí)的，當(dāng)問題規(guī)模達(dá)到一定程度時(shí)，算法的效率不高，那么就很難在有限的時(shí)間里計(jì)算出結(jié)果，這就需要我們尋

2、找一種快速的方法。局部搜索算法由爬山算法改進(jìn)而來，在計(jì)算量和搜索的規(guī)模上都大幅度的減小，使其在NPC這類問題的研究中有了廣泛的應(yīng)用。局部搜索算法也有其局限性，就是把局部最優(yōu)解做為全局最優(yōu)解，而問題中往往全局最優(yōu)解和局部最優(yōu)解不想等，這就必須對設(shè)計(jì)出的局部搜索算法進(jìn)行復(fù)雜性分析，分析其近似性能比。
　　 在本文中，主要是應(yīng)用和設(shè)計(jì)局部搜索算法，分析近似性能比，做出了如下結(jié)果:
　　 1.列舉了Max-SAT問題的幾個(gè)常見的

3、算法，并給出它們在算法執(zhí)行中的最差實(shí)例，通過實(shí)驗(yàn)給出它們的實(shí)際表現(xiàn)情況，供讀者參考對比分析它們的好壞。
　　 2.利用前人的思想，分析一位跳變+全體跳變這個(gè)算法解決Max-3-SAT問題，然后以此為基礎(chǔ)設(shè)計(jì)算法來解決Max-4-SAT問題，希望能夠?qū)⒔票扔?0/9降低到16/15，并通過實(shí)驗(yàn)驗(yàn)證設(shè)計(jì)出的算法的可行性。
　　 3.改變思想，提出了新的局部搜索算法，使其能夠解決MaxNAE-3-SAT問題，證明其近似比為4