利用極小不可滿(mǎn)足公式的臨界特性,可以將任意一個(gè)3-CNF公式多項(xiàng)式時(shí)間歸約轉(zhuǎn)換為一個(gè)正則（3,4）-CNF公式,從而得到一個(gè)保留NP完全性的正則（3,4）-SAT問(wèn)題。對(duì)于歸約轉(zhuǎn)換后的正則（3,4）-SAT實(shí)例集而言,警示傳播算法（Warning Propagation,WP）在其上高概率收斂,然而難以有效地返回關(guān)于變?cè)囊唤M真值指派（如果該實(shí)例可滿(mǎn)足）。因此,在歸約轉(zhuǎn)換下的正則（3,4）-SAT問(wèn)題上,WP算法求解失效。本文圍繞該問(wèn)題,基于歸約轉(zhuǎn)換下正則（3,4）-CNF公式的結(jié)構(gòu)特征,提出了WP算法的一種修正策略來(lái)專(zhuān)門(mén)用于求解歸約轉(zhuǎn)換下的正則（3,4）-SAT實(shí)例。同時(shí)基于WP算法的信息傳播機(jī)制,引出了WP-可解公式的結(jié)構(gòu)定義,探索了WP算法的收斂性特征條件。主要的研究成果如下:（1）從三個(gè)方面比較了歸約轉(zhuǎn)換后的正則（3,4）-CNF公式與原3-CNF公式在公式的結(jié)構(gòu)特征上所發(fā)生的變化:一是歸約轉(zhuǎn)換后的正則（3,4）-CNF公式中變?cè)?fù)出現(xiàn)次數(shù)之差趨于穩(wěn)定;二是歸約轉(zhuǎn)換后的正則（3,4）-CNF公式中每個(gè)變?cè)辽俦话趦蓚�(gè)圈中;三是一個(gè)歸約轉(zhuǎn)換后且可滿(mǎn)足的正則（3,4）-CNF... 

【文章頁(yè)數(shù)】：55 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景
    1.2 國(guó)內(nèi)外研究現(xiàn)狀
    1.3 論文研究的主要內(nèi)容
    1.4 論文的組織結(jié)構(gòu)
第二章 基礎(chǔ)知識(shí)
    2.1 可滿(mǎn)足性問(wèn)題
    2.2 因子圖
    2.3 警示傳播算法
    2.4 本章小結(jié)
第三章 歸約轉(zhuǎn)換下正則(3,4)-CNF公式的結(jié)構(gòu)特征
    3.1 變換構(gòu)件
    3.2 3-CNF公式轉(zhuǎn)換為正則(3,4)-CNF公式的變換技術(shù)
    3.3 歸約轉(zhuǎn)換下正則(3,4)-CNF公式的結(jié)構(gòu)特征
    3.4 本章小結(jié)
第四章 求解正則(3,4)-SAT實(shí)例集的修正警示傳播算法
    4.1 問(wèn)題描述
    4.2 警示傳播算法的改進(jìn)
    4.3 修正的警示傳播算法求解正則(3,4)-SAT問(wèn)題
    4.4 本章小結(jié)
第五章 WP-可解公式上警示傳播算法的收斂性
    5.1 WP-可解公式的結(jié)構(gòu)定義
    5.2 生成可滿(mǎn)足實(shí)例的隨機(jī)算法
    5.3 WP-可解公式上警示傳播算法的收斂性
    5.4 本章小結(jié)
第六章 結(jié)束語(yǔ)
    6.1 論文主要工作總結(jié)
    6.2 論文中存在的不足
    6.3 研究展望
致謝
參考文獻(xiàn)
附錄
圖版



本文編號(hào)：3660870