開(kāi)題報(bào)告(王曉峰).ppt

《開(kāi)題報(bào)告(王曉峰).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、基于WP的啟發(fā)式極性決策算法解SAT問(wèn)題研究生：王曉峰導(dǎo)　師:許道云教授選題意義12研究方案3可行性分析匯報(bào)提綱任務(wù)安排及預(yù)期結(jié)果5研究?jī)?nèi)容4選題意義研究意義(1)可滿足性問(wèn)題(SAT問(wèn)題)是計(jì)算機(jī)科學(xué)中的核心問(wèn)題。SAT問(wèn)題是一類(lèi)有名的NP-完全問(wèn)題，直觀上它超出了現(xiàn)代計(jì)算機(jī)的計(jì)算能力，從理論上講，SAT問(wèn)題不能在多項(xiàng)式時(shí)間內(nèi)解決。然而，在實(shí)際應(yīng)用中不可回避這一問(wèn)題。因此，高效適用的SAT算法是目前研究的熱點(diǎn)。(2)根據(jù)能否證明一個(gè)實(shí)例的不可滿足性，SAT算法可分為完全算法和不完全算法兩大類(lèi)。盡管不完全算法對(duì)大多數(shù)可滿足性實(shí)例很快能夠找到一個(gè)解。但不能證明一個(gè)SAT

2、實(shí)例是不可滿足的。完全算法能夠驗(yàn)證一個(gè)SAT實(shí)例滿足或者不滿足，但在滿足實(shí)例上的整體效果不如不完全算法。而在許多應(yīng)用領(lǐng)域，如EDA的等價(jià)性驗(yàn)證或者屬性檢驗(yàn)需要證明一個(gè)實(shí)例不滿足，因此，DPLL完全算法受到更為廣泛的關(guān)注。選題意義國(guó)外研究現(xiàn)狀：幾個(gè)優(yōu)秀算法——Zchaff、MiniSat信息傳播算法——WP、BP、SP國(guó)內(nèi)研究現(xiàn)狀：荊明娥,周電等.啟發(fā)式極性決策算法解SAT問(wèn)題;邵明,李光輝,李曉維.求解可滿足問(wèn)題的調(diào)查傳播算法以及步長(zhǎng)的影響規(guī)律；李韶華，張健.一種求解SAT的高效算法；研究?jī)?nèi)容WP算法簡(jiǎn)單介紹警示傳播(WarningPropagation,WP)算法是

3、源于物理學(xué)的一個(gè)不完全算法，它在解決變?cè)獢?shù)很多的實(shí)例上表現(xiàn)不錯(cuò)。WP算法是在因子圖上通過(guò)某種警示信息的迭代，算法收斂時(shí)得到一組穩(wěn)定的警示信息，并利用局部腔域得到公式變?cè)馁x值，通常能夠?qū)υ瓎?wèn)題進(jìn)行簡(jiǎn)化。實(shí)驗(yàn)表明，這種算法在變量數(shù)目很大的難解區(qū)域，有不錯(cuò)的表現(xiàn)，并且在SAT/UNSAT的相變區(qū)域也有優(yōu)越的表現(xiàn)，能固定10%-50%的變量賦值。但遺憾的是，WP算法常常在相變區(qū)域不收斂，在這種情況下，得到的子公式往往是UNSAT的，或者用其它解決器在短時(shí)間內(nèi)難以求解。特別是在RB模型產(chǎn)生的實(shí)例集上，WP算法在相變區(qū)域基本不收斂。研究?jī)?nèi)容研究WP算法的基本原理，分析WP算法的

4、收斂性研究WP算法在不收斂時(shí)的改進(jìn)策略，使之更有效的解決難解區(qū)域?qū)嵗拖嘧儏^(qū)域?qū)嵗芯考铀賅P算法收斂的改進(jìn)策略設(shè)計(jì)出一個(gè)有效的求解SAT問(wèn)題的完全算法研究方案1）掌握WP算法和DPLL算法的基本原理2）掌握Z(yǔ)chaff算法基本思想，并進(jìn)行實(shí)驗(yàn)驗(yàn)證3）分析WP算法的收斂性，并給出算法的改進(jìn)策略，進(jìn)行實(shí)驗(yàn)驗(yàn)證4）設(shè)計(jì)出一個(gè)求解SAT問(wèn)題的完全算法5）給出新算法的實(shí)驗(yàn)驗(yàn)證6）對(duì)算法進(jìn)行評(píng)價(jià)，與已有算法進(jìn)行比較，給出評(píng)價(jià)參數(shù)指標(biāo)可行性分析可滿足性問(wèn)題算法研究，國(guó)內(nèi)外的專(zhuān)家學(xué)者已經(jīng)做了大量的研究，大量的參考資料可以獲取。我們?cè)陂喿x大量的參考資料的同時(shí)，收集了大量的實(shí)例集，進(jìn)行

5、了大量的科學(xué)實(shí)驗(yàn)，取得較好的實(shí)驗(yàn)結(jié)果。本研究有望達(dá)到預(yù)期結(jié)果。此外，本課題在導(dǎo)師的指導(dǎo)下，已經(jīng)完了初步設(shè)計(jì)，確保該課題的可行性。預(yù)期結(jié)果設(shè)計(jì)基于WP的啟發(fā)式極性決策算法搭建實(shí)驗(yàn)平臺(tái)，對(duì)算法進(jìn)行實(shí)驗(yàn)驗(yàn)證任務(wù)安排該課題研究的起止年限是2009年4月至2010年5月。任務(wù)安排如下：2009年4月—2009年6月：查閱相關(guān)文獻(xiàn)；收集資料，掌握本領(lǐng)域的研究現(xiàn)狀，并掌握一些工具的使用。2009年6月—2009年10月：研究問(wèn)題；對(duì)課題進(jìn)行詳細(xì)分析，給出粗略的設(shè)計(jì)方案。2009年10月—2010年1月：解決問(wèn)題；給出詳細(xì)的設(shè)計(jì)方案，并設(shè)計(jì)出算法。寫(xiě)出相應(yīng)的程序，進(jìn)行實(shí)驗(yàn)驗(yàn)證，對(duì)算法

6、進(jìn)行復(fù)雜性分析，給出算法的有效性。2010年1月—2010年5月：論文修整，整理稿件成文。謝謝