1、可滿足問題(SAT)是第一個被證明的NP-完全問題[Cook71],是Johnson等人在上千個NP問題中總結(jié)出的六個最具代表性的問題之一,它在計算復(fù)雜性理論中具有極其重要的地位,其理論研究三十多年來從未停止過?？蓾M足問題在人工智能、集成電路設(shè)計、規(guī)劃、圖論等重要領(lǐng)域中都有所應(yīng)用(存在直接的可滿足問題或者可以轉(zhuǎn)化為可滿足實例高效求解的問題),同時,由于該問題描述和數(shù)據(jù)表示非常簡單,因此是很好的算法試驗田,從這里發(fā)展出的算法技術(shù)可以快速的

2、應(yīng)用于其他問題上。因此,高效實用的可滿足算法設(shè)計與分析同樣是多年來的研究熱點。
　　 本文的研究工作是針對可滿足問題的預(yù)處理問題展開的,預(yù)處理是對求解問題進行簡化,以實現(xiàn)幫助問題求解的目的。本文首先分析和介紹了可滿足問題算法一路走來過程中衍生出的幾種經(jīng)典算法,以及預(yù)處理方面的幾種常見算法。針對其中的預(yù)處理工作提出了改進的方法,并實現(xiàn)提高整個問題解決效率的目的。
　　 本文主要的價值之處在于:(1)使用二元關(guān)系矩陣來構(gòu)建邏