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

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

G 稱為二分圖，記作 ( )1 2G = V , V ,E，E 為 G 的邊集合。式的因子圖實(shí)則是子句變?cè)换D，此交互圖是一個(gè)二是以布爾變?cè)?X 為布爾變?cè)旤c(diǎn)，而另一側(cè)是以子句爾變?cè)霈F(xiàn)在一個(gè)子句中，表示有一條邊連接此變?cè)?中，其頂點(diǎn) v 的度（Degree）是指與頂點(diǎn) v 相關(guān)聯(lián)的邊數(shù)中每個(gè)頂點(diǎn)的度是某一固定整數(shù) k，則稱該圖是 k-正則圖NF 公式的因子圖則是一個(gè)雙正則二分圖，在子句頂點(diǎn)為 k；在布爾變?cè)旤c(diǎn)的一側(cè)，每個(gè)頂點(diǎn)的度都為 2r。對(duì)連接規(guī)則：當(dāng)布爾變?cè)哉淖殖霈F(xiàn)，則以實(shí)邊相連；當(dāng)，則以虛邊相連。圖 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
【學(xué)位授予單位】：貴州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP301.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

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

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

本文編號(hào)：2593155