基于擴(kuò)展規(guī)則的＃SAT近似求解器的研究.pdf

1、智能規(guī)劃是20世紀(jì)50年代后期迅速發(fā)展起來的一個(gè)前沿研究領(lǐng)域，近年來對該領(lǐng)域的研究取得了革命性的進(jìn)展。其中，把規(guī)劃問題編譯為SAT問題，然后利用高效的SAT求解器進(jìn)行求解的方法是目前規(guī)劃求解的主流方法之一。研究表明，這種間接求解有時(shí)比直接求解更方便更快捷。＃SAT問題是由SAT問題引出的更具有挑戰(zhàn)性的問題，許多概率推理問題如置信度分析、貝葉斯網(wǎng)絡(luò)推理、概率規(guī)劃問題等都可以轉(zhuǎn)化成＃SAT問題進(jìn)行求解。這是因?yàn)椋AT問題是＃P完全問題的原

2、型，幾乎所有的＃P完全問題都能在多項(xiàng)式時(shí)間內(nèi)歸約為＃SAT問題。因此，研究＃SAT求解技術(shù)不僅對規(guī)劃領(lǐng)域而且對其他許多領(lǐng)域有著重要的理論價(jià)值和現(xiàn)實(shí)意義。 許多＃SAT求解器都利用了歸結(jié)方法，擴(kuò)展規(guī)則方法是一種與歸結(jié)方法對稱的SAT求解方法，目前該方法已被進(jìn)一步推廣到＃SAT問題求解中，但是它的時(shí)間復(fù)雜度是指數(shù)級的，效率比較低。 本文在擴(kuò)展規(guī)則的基礎(chǔ)上提出了兩種＃SAT問題的近似求解算法：上下界近似(Up-DownAppr

3、ox)和采樣近似(SampleApprox)。上下界近似是從計(jì)算不可滿足賦值的近似個(gè)數(shù)出發(fā)，最終計(jì)算出近似模型個(gè)數(shù)。其基本思想是：對于容斥原理，將每個(gè)累加和視為一項(xiàng)，它的前奇數(shù)項(xiàng)之和是一個(gè)上界，前偶數(shù)項(xiàng)之和是一個(gè)下界，文中分析了在什么情況下能使某個(gè)上界或下界與精確不可滿足賦值個(gè)數(shù)的近似偏量在某個(gè)范圍內(nèi)(如≤0.01或更小)，這樣可以將該上界或下界視為不可滿足賦值個(gè)數(shù)的近似值，從而得出近似模型個(gè)數(shù)。采樣近似是將采樣方法與改進(jìn)的擴(kuò)展規(guī)則方法

4、MCIER相結(jié)合來得到近似模型個(gè)數(shù)。其基本思想是：首先選擇若干個(gè)變量并賦值，這樣可以限定一個(gè)子空間，然后利用采樣方法計(jì)算出總的模型個(gè)數(shù)與被限定子空間的模型個(gè)數(shù)的近似倍率，并利用MCIER計(jì)算出被限定子空間的模型個(gè)數(shù)，將近似倍率乘以被限定子空間的模型個(gè)數(shù)就可以得到近似模型個(gè)數(shù)。 根據(jù)以上兩種算法，本文設(shè)計(jì)了兩個(gè)＃SAT近似求解器：UDApp和SamApp，為了與精確求解器進(jìn)行比較，我們實(shí)現(xiàn)了精確模型計(jì)數(shù)算法MCER。實(shí)驗(yàn)結(jié)果表明兩