利用極小不可滿足公式的臨界特性,可以將任意一個3-CNF公式多項式時間歸約轉換為一個正則（3,4）-CNF公式,從而得到一個保留NP完全性的正則（3,4）-SAT問題。對于歸約轉換后的正則（3,4）-SAT實例集而言,警示傳播算法（Warning Propagation,WP）在其上高概率收斂,然而難以有效地返回關于變元的一組真值指派（如果該實例可滿足）。因此,在歸約轉換下的正則（3,4）-SAT問題上,WP算法求解失效。本文圍繞該問題,基于歸約轉換下正則（3,4）-CNF公式的結構特征,提出了WP算法的一種修正策略來專門用于求解歸約轉換下的正則（3,4）-SAT實例。同時基于WP算法的信息傳播機制,引出了WP-可解公式的結構定義,探索了WP算法的收斂性特征條件。主要的研究成果如下:（1）從三個方面比較了歸約轉換后的正則（3,4）-CNF公式與原3-CNF公式在公式的結構特征上所發(fā)生的變化:一是歸約轉換后的正則（3,4）-CNF公式中變元正負出現(xiàn)次數(shù)之差趨于穩(wěn)定;二是歸約轉換后的正則（3,4）-CNF公式中每個變元至少被包含在兩個圈中;三是一個歸約轉換后且可滿足的正則（3,4）-CNF... 

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

【學位級別】：碩士

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



本文編號：3660870