【摘要】：布爾可滿足性問題是理論計算機科學中的核心問題,人們一直致力于尋找CNF公式實例難解的本質,通過限定CNF公式的結構,如子句長度、布爾變元出現(xiàn)次數(shù)等,并以此為基礎,分析CNF公式的結構信息,設計高效的求解算法。本文研究的平衡正則(k,2r)-CNF公式是一類具有規(guī)則結構的CNF公式,通過限定每個子句的長度為k,每個布爾變元的正出現(xiàn)次數(shù)和負出現(xiàn)次數(shù)都為r,其實例求解難度比一般的k-CNF公式實例求解難度大。本文從實例生成模型、結構信息、求解算法、相變性質等方面對平衡正則(k,2r)-CNF公式進行研究,主要研究成果如下:(1)為了便于分析平衡正則(k,2r)-CNF公式的結構信息及相變性質,構建了一個生成平衡正則(k,2r)-CNF公式實例的隨機模型—BR(n,k,2r)模型。該模型可以有效地生成不重復的平衡正則(k,2r)-CNF公式子句。(2)通過將平衡正則(k,2r)-CNF公式分別表示為變元交互圖和因子圖,研究了平衡正則(k,2r)-CNF公式的結構信息。實驗發(fā)現(xiàn):在變元交互圖中,頂點的度與公式的子句變元比正相關;在因子圖中,子句與變元呈現(xiàn)交錯分布。(3)基于平衡正則(k,2r)-CNF公式特殊的結構信息,改進了隨機局部搜索(Stochastic Local Search,SLS)算法的初始賦值方式來求解該類正則公式。實驗結果表明:改進后的SLS算法比原算法能更有效地求解平衡正則(k,2r)-CNF公式。(4)平衡正則(k,2r)-CNF公式實例隨著子句變元比的增大,會出現(xiàn)可滿足性相變現(xiàn)象。通過理論分析,給出了平衡正則(k,2r)-CNF公式可滿足性相變閾值點的一個上界為2~kln 2-kln 2/2,一個下界為2~kln 2-kln 2/2-2ln 2.
【圖文】：

元數(shù) n 的比值 α = m /n，通常稱之為子句變元比，，它是 k-CNF 公式重要的結構參數(shù)，因為其值會影響到k-CNF公式的可滿足性及判定說，隨著α 的不斷增大，存在某個臨界值點sα 。當sα < α時，幾乎 實例都可滿足，并稱之為高概率可滿足；而當sα > α時，幾乎全部的不可滿足，并稱之為高概率不可滿足。這種現(xiàn)象被稱為隨機 k-SAT sα 稱為相變閾值點，以 ( )sα k來表示對 k 不同取值的相變閾值點。[47,48]表明隨機 2-SAT 的相變閾值點 ( 2 )1sα = ，隨機 3-SAT 的相變閾)的值約為 4.267[49]。R. Monasson 與 R. Zecchina 等人[51]于 1999 年發(fā)ture》上的文章指出，求解隨機 k-SAT 問題在計算復雜性上的分布會殊的“Easy-Hard-Easy”模式，即當子句變元比達到臨界值時，k-S滿足突變?yōu)椴豢蓾M足，而實例的求解難度則從易于求解變得難于求得易于求解。圖 2.1 給出了隨機 3-SAT 問題中子句變元比與求解難率的關系示意圖。

G 稱為二分圖，記作 ( )1 2G = V , V ,E，E 為 G 的邊集合。式的因子圖實則是子句變元交互圖，此交互圖是一個二是以布爾變元集 X 為布爾變元頂點，而另一側是以子句爾變元出現(xiàn)在一個子句中，表示有一條邊連接此變元頂 中，其頂點 v 的度（Degree）是指與頂點 v 相關聯(lián)的邊數(shù)中每個頂點的度是某一固定整數(shù) k，則稱該圖是 k-正則圖NF 公式的因子圖則是一個雙正則二分圖，在子句頂點為 k；在布爾變元頂點的一側，每個頂點的度都為 2r。對連接規(guī)則：當布爾變元以正文字出現(xiàn)，則以實邊相連；當，則以虛邊相連。圖 2.2 展現(xiàn)了平衡正則( 3,4 )-CNF公式2 3 4 C C∧ ∧ 的因子圖，其中， ( )1 1 2 3C = x ∨ x ∨ x， 2 C= ( )1 2 3 x ∨ x ∨ x， ( )4 1 2 3C= x ∨ x ∨ x。CCCC
【學位授予單位】：貴州大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP301.6

【參考文獻】

相關期刊論文 前2條

1 許道云;王曉峰;;一個正則NP-完全問題及其不可近似性[J];計算機科學與探索;2013年08期

2 劉吉穎,方思行;AI規(guī)劃的回顧與展望[J];中山大學學報論叢;2000年05期

本文編號：2593155