使用分支定界算法求解帶硬約束的MAX-SAT問題.pdf

1、帶硬約束的MAX—SAT問題又稱為Partial MAX—SAT問題，它是SAT問題和MAX—SAT問題的結(jié)合，比后兩者有著更強(qiáng)的描述問題的能力和更廣泛的應(yīng)用背景。人工智能、電路設(shè)計(jì)、生物信息學(xué)等領(lǐng)域的許多問題都可以轉(zhuǎn)化為Partial MAX—SAT問題。 對(duì)含有硬子句和軟子句的公式，Partial MAX—SAT問題的目標(biāo)是要找到一組賦值，在滿足所有硬子句的情況下，滿足最多的軟子句。Partial MAX—SAT問題是NP難

2、的最優(yōu)化問題，對(duì)它的求解算法分為完備算法和非完備算法，當(dāng)前的研究主要集中在完備算法。 本文首先介紹了MAX—SAT問題的研究現(xiàn)狀。然后設(shè)計(jì)分支定界算法求解Partial MAX—SAT問題。當(dāng)前的大部分求解器都是給硬子句賦予足夠大的權(quán)值，把帶硬約束的MAX—SAT問題轉(zhuǎn)化為帶權(quán)值的MAX—SAT問題，而沒有利用硬子句的特性。本文在下界計(jì)算方面，充分利用硬子句的性質(zhì)，獲得更緊的下界。在推理技術(shù)方面，提出適應(yīng)硬子句的五條推理規(guī)則。針