可滿足性問題的約束規(guī)劃算法研究.pdf

1、可滿足性問題(簡稱SAT問題)是NP-hard問題，它是當(dāng)前運籌學(xué)、人工智能和計算機科學(xué)的熱點領(lǐng)域，解決SAT問題具有突出的理論價值和應(yīng)用價值。解決SAT問題的傳統(tǒng)算法往往要占用很長時間和大量的內(nèi)存，而最后往往還不能得到滿意的結(jié)果。為了提高SAT問題解決算法的性能，本文對于SAT問題做了對已有算法的分析研究、約束規(guī)劃算法分析、約束規(guī)劃算法的UML建模和約束規(guī)劃算法來求解SAT問題的實驗分析等方面的探討，主要的內(nèi)容有：
　　 對S

2、AT問題已有的主要算法及存在的問題進行了研究，總結(jié)了提高算法性能和跳出局部陷井所用的策略或機制。對局部搜索算法的實驗分析，針對局部搜索算法的靈活性、隨機性和參數(shù)化等特點，深入探討了相應(yīng)的算法實驗分析所涉及的算法性能度量、性能比較和參數(shù)調(diào)優(yōu)等基本問題。提出了綜合人工智能中一致性算法和啟發(fā)式搜索算法，采用約束推理的方法的約束規(guī)劃算法。本文通過對約束規(guī)劃算法事件觸發(fā)機制的分析和UML的建模，從而提高了搜索效率，提出了解決SAT問題。