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

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

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