資源描述：
《開題報告(王曉峰).ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、基于WP的啟發(fā)式極性決策算法解SAT問題研究生：王曉峰導(dǎo) 師:許道云教授選題意義12研究方案3可行性分析匯報提綱任務(wù)安排及預(yù)期結(jié)果5研究內(nèi)容4選題意義研究意義(1)可滿足性問題(SAT問題)是計算機科學(xué)中的核心問題。SAT問題是一類有名的NP-完全問題，直觀上它超出了現(xiàn)代計算機的計算能力，從理論上講，SAT問題不能在多項式時間內(nèi)解決。然而，在實際應(yīng)用中不可回避這一問題。因此，高效適用的SAT算法是目前研究的熱點。(2)根據(jù)能否證明一個實例的不可滿足性，SAT算法可分為完全算法和不完全算法兩大類。盡管不完全算法對大多數(shù)可滿足性實例很快能夠找到一個解。但不能證明一個SAT
2、實例是不可滿足的。完全算法能夠驗證一個SAT實例滿足或者不滿足，但在滿足實例上的整體效果不如不完全算法。而在許多應(yīng)用領(lǐng)域，如EDA的等價性驗證或者屬性檢驗需要證明一個實例不滿足，因此，DPLL完全算法受到更為廣泛的關(guān)注。選題意義國外研究現(xiàn)狀：幾個優(yōu)秀算法——Zchaff、MiniSat信息傳播算法——WP、BP、SP國內(nèi)研究現(xiàn)狀：荊明娥,周電等.啟發(fā)式極性決策算法解SAT問題;邵明,李光輝,李曉維.求解可滿足問題的調(diào)查傳播算法以及步長的影響規(guī)律；李韶華，張健.一種求解SAT的高效算法；研究內(nèi)容WP算法簡單介紹警示傳播(WarningPropagation,WP)算法是
3、源于物理學(xué)的一個不完全算法，它在解決變元數(shù)很多的實例上表現(xiàn)不錯。WP算法是在因子圖上通過某種警示信息的迭代，算法收斂時得到一組穩(wěn)定的警示信息，并利用局部腔域得到公式變元的賦值，通常能夠?qū)υ瓎栴}進(jìn)行簡化。實驗表明，這種算法在變量數(shù)目很大的難解區(qū)域，有不錯的表現(xiàn)，并且在SAT/UNSAT的相變區(qū)域也有優(yōu)越的表現(xiàn)，能固定10%-50%的變量賦值。但遺憾的是，WP算法常常在相變區(qū)域不收斂，在這種情況下，得到的子公式往往是UNSAT的，或者用其它解決器在短時間內(nèi)難以求解。特別是在RB模型產(chǎn)生的實例集上，WP算法在相變區(qū)域基本不收斂。研究內(nèi)容研究WP算法的基本原理，分析WP算法的
4、收斂性研究WP算法在不收斂時的改進(jìn)策略，使之更有效的解決難解區(qū)域?qū)嵗拖嘧儏^(qū)域?qū)嵗芯考铀賅P算法收斂的改進(jìn)策略設(shè)計出一個有效的求解SAT問題的完全算法研究方案1）掌握WP算法和DPLL算法的基本原理2）掌握Zchaff算法基本思想，并進(jìn)行實驗驗證3）分析WP算法的收斂性，并給出算法的改進(jìn)策略，進(jìn)行實驗驗證4）設(shè)計出一個求解SAT問題的完全算法5）給出新算法的實驗驗證6）對算法進(jìn)行評價，與已有算法進(jìn)行比較，給出評價參數(shù)指標(biāo)可行性分析可滿足性問題算法研究，國內(nèi)外的專家學(xué)者已經(jīng)做了大量的研究，大量的參考資料可以獲取。我們在閱讀大量的參考資料的同時，收集了大量的實例集，進(jìn)行
5、了大量的科學(xué)實驗，取得較好的實驗結(jié)果。本研究有望達(dá)到預(yù)期結(jié)果。此外，本課題在導(dǎo)師的指導(dǎo)下，已經(jīng)完了初步設(shè)計，確保該課題的可行性。預(yù)期結(jié)果設(shè)計基于WP的啟發(fā)式極性決策算法搭建實驗平臺，對算法進(jìn)行實驗驗證任務(wù)安排該課題研究的起止年限是2009年4月至2010年5月。任務(wù)安排如下：2009年4月—2009年6月：查閱相關(guān)文獻(xiàn)；收集資料，掌握本領(lǐng)域的研究現(xiàn)狀，并掌握一些工具的使用。2009年6月—2009年10月：研究問題；對課題進(jìn)行詳細(xì)分析，給出粗略的設(shè)計方案。2009年10月—2010年1月：解決問題；給出詳細(xì)的設(shè)計方案，并設(shè)計出算法。寫出相應(yīng)的程序，進(jìn)行實驗驗證，對算法
6、進(jìn)行復(fù)雜性分析，給出算法的有效性。2010年1月—2010年5月：論文修整，整理稿件成文。謝謝
