可滿足性問題的研究綜述
2009-12-29 00:00:00王建新管利娜江國紅
計算技術與自動化 2009年4期
摘要：對SAT問題及其各種約束子問題進行分類并給出具體定義，著重介紹常規SAT問題、最大可滿足性問題(MAX-SAT)和參數化SAT問題的相關算法，并對參數算法中運用的技術進行分析和比較，提出一些SAT問題研究中值得關注的幾個方面。
關鍵詞：可滿足性問題；NP完全問題；參數計算
中圖分類號：TP301.6 文獻標識碼：A
摘要：對SAT問題及其各種約束子問題進行分類并給出具體定義，著重介紹常規SAT問題、最大可滿足性問題(MAX-SAT)和參數化SAT問題的相關算法，并對參數算法中運用的技術進行分析和比較，提出一些SAT問題研究中值得關注的幾個方面。
關鍵詞：可滿足性問題；NP完全問題；參數計算
中圖分類號：TP301.6 文獻標識碼：A
