SAT求解局部搜索行為分析與概率控制策略.pdf

1、SAT問題(Satisfiability problem)，是第一個被證明的NPC(Non-deterministic Polynomial Complete)問題，在計算機科學(xué)理論和應(yīng)用中具有重要的意義。對于理論研究，它是計算復(fù)雜性理論的奠基石，所有的NPC問題都可以在多項式時間內(nèi)轉(zhuǎn)化為SAT問題。對于工業(yè)應(yīng)用，SAT可用于解決等價性驗證、有界模型檢測、電子設(shè)計自動化、統(tǒng)計物理學(xué)等多方面問題。因此，高效實用的SAT算法和技術(shù)是目前研究

2、的熱點。
　　局部搜索算法是目前求解SAT問題比較有效的算法，Sattime算法是典型的局部搜索算法，曾在2011年的SAT問題國際求解大賽中獲得隨機類型算例組的銀牌。它是基于Novelty系列的算法，在選擇翻轉(zhuǎn)變元時它利用了子句滿足的歷史信息，對其求解過程進行行為分析與模式挖掘可以發(fā)現(xiàn)變元與子句間蘊含的因果關(guān)系。建立數(shù)據(jù)庫記錄局部搜索算法的求解行為，對翻轉(zhuǎn)事件進行數(shù)據(jù)挖掘，包括關(guān)聯(lián)規(guī)則模式挖掘和頻繁序列模式挖掘。通過對挖掘結(jié)果進

3、行分析，發(fā)現(xiàn)Sattime算法有時會出現(xiàn)先后選擇同一個變元的現(xiàn)象，這種現(xiàn)象可能使搜索過程產(chǎn)生回環(huán)。從而提出兩種概率控制策略：加強子句選擇策略和加強變元選擇策略。將這兩種策略應(yīng)用到Sattime算法中，形成新的局部搜索算法Sattime-P。
　　使用Sattime算法和Sattime-P算法對不同類型的算例進行求解，對比它們的平均翻轉(zhuǎn)次數(shù)、平均求解時間。實驗結(jié)果表明使用改進策略的Sattime-P算法在大多數(shù)情況下減少了平均翻轉(zhuǎn)次