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

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

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