基于集合理論的SAT算法的設計與實現.pdf

1、SAT是理論計算機科學中的一個經典問題，也是被發(fā)現的第一個NP完全問題。SAT問題是對于給定的一個布爾邏輯表達式在SAT問題可滿足的情況下給出一組解，使得該布爾邏輯表達式為“真”；在給定問題不可滿足的情況下給出證明。比較著名的高效SAT求解算法有MiNiSat、zchaff Grasp等。SAT求解算法廣泛應用于實際生活中的各種領域，如電路設計的形式化驗證、人工智能、資源調度等。雖然SAT求解算法的研究已經相當成熟，但它仍然是實際應用領

2、域中必須打破的一個瓶頸。例如在電路設計的形式化驗證中，將電路中的變量轉化為布爾邏輯的合取范式形式(Conjunctive Normal Form簡稱CNF)，再應用SAT求解來檢測電路故障，傳統算法往往要占用很長時間和大量的內存，而最后往往還不能得到滿意的結果。所以到目前為止，眾多國內外學者層出不窮的推出新型算法來提高計算效率，以便高效地應用于各行各業(yè)。 雖然命題邏輯的理論研究已經相當成熟，但是在SAT問題及其算法被越來越多地應

3、用到現實世界的生產和生活中的今天，探尋命題邏輯可滿足性判定的高效算法仍然是一個令人興奮的方向。SAT問題的解決方法一般分為兩類：完備算法和不完備算法，它們的典型代表是Davis-Putnam提出的基于回溯搜索的DPLL算法和本地啟發(fā)式搜索。當今流行的SAT算法主要是完備算法或在DPLL算法基礎上的改進和衍生。 本文在對現有的SAT問題相關理論的研究以及算法分析的基礎上，基于DPLL算法結合集合理論提出了一種新型的SAT算法。具有