可滿足性問題的預處理策略研究與分析.pdf

1、可滿足性問題（即SAT問題）是第一個被證明的經典NP問題。人們一直致力于如何在有限的時間求解可滿足性問題。隨著現實世界中可滿足性問題的規(guī)模逐漸增長，預處理技術已經逐漸受到重視。由于其良好的簡化效果，變量消除算法已經應用于多種預處理器中。作為一種輕量級預處理技術，變量消除算法的簡化效果與其消除過程中的約束條件有著直接聯(lián)系。
　　為了進一步提高和優(yōu)化變量消除算法的預處理性能，本文對比研究了在不同的約束條件下變量消除算法的簡化性能以及簡

2、化后的CNF實例的求解效果，同時設計了一種基于子句文字長度動態(tài)約束的變量消除算法。與分解前的子句文字長度相比，只有當分解后的子句集合的文字長度減少時，該算法完成變量消除替換過程。為了減少變量消除算法中無價值計算，該算法引入了動態(tài)約束機制，大大縮短了預處理時間，進一步提高簡化性能。本文在該算法的基礎上，基于MiniSat的開源代碼實現了一個可滿足性問題的預處理器 MiniSat BFS。除了通過常規(guī)的性能指標來對比分析兩種不同約束條件下變