基于回答集(或穩(wěn)定模型)語義的邏輯程序(Answer Set Program,簡稱ASP),是一種描述性問題求解的范例。由于其非單調(diào)的本質(zhì)特征和各種有效的回答集求解系統(tǒng)的出現(xiàn),而被廣泛應(yīng)用于智能規(guī)劃、診斷、調(diào)度等領(lǐng)域。相變(phase transition)是研究復(fù)雜系統(tǒng)性質(zhì)的一種重要方法,在可滿足性問題(SAT)和正規(guī)邏輯程序等方面獲得了深刻的理論結(jié)果。析取邏輯程序回答集存在性等問題的復(fù)雜性在多項(xiàng)式分層上比正規(guī)邏輯程序高一層,本文研究析取邏輯程序的相變性質(zhì),主要包括:(1)證明了任何析取邏輯程序模等價(jià)于句法簡單的析取邏輯程序,即對任何析取邏輯程序P,存在一個析取邏輯程序Q,其中的所有規(guī)則頭中(至多)含有2個原子,規(guī)則體中(至多)含有兩個文字,使得在限制到P中出現(xiàn)的原子集上時(shí)P和Q有相同的回答集。(2)證明了規(guī)則頭中(至多)含有2個原子的最大析取邏輯程序回答集的存在性問題,規(guī)則體中文字?jǐn)?shù)大于1時(shí),最大邏輯程序沒有回答集;規(guī)則體文字?jǐn)?shù)為1時(shí),最大邏輯程序有n個大小為n)1(-的回答集,其中n為程序中的原子數(shù)。(3)借用圖的kernel性質(zhì),將判斷邏輯程序是否具有回答集用能量函數(shù)表示出來,...

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

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

【部分圖文】：

圖2-2ASP求解過程

圖2-2ASP求解過程兩個實(shí)例來進(jìn)行說明：：基于回答集邏輯程序比較直觀的應(yīng)用就是排課系統(tǒng)。雖然排課

圖2-3析取邏輯程序編寫圖著色用gringo基化器和claspD求解器求解程序，能夠很容易得到圖中可能的著色方案，如

條規(guī)則就能把問題表述清楚。規(guī)則r1表示每一個節(jié)點(diǎn)可以有三的節(jié)點(diǎn)之間不能是相同的顏色，規(guī)則r3表示一個節(jié)點(diǎn)只能有一事實(shí)的集合F表示。F{r1,r2,r3}有回答集當(dāng)且僅當(dāng)圖G是可有6個節(jié)點(diǎn)，11條邊。我們可以得到下面的程序，如圖2-3：

圖2-4求解圖可著色方案

圖2-4求解圖可著色方案解相關(guān)概念

圖5-4隨著m/n值的增加，不同ratio，對應(yīng)求解邏輯程序需要的loop

(b)n=15(a)n=10圖5-4隨著m/n值的增加，不同ratio，對應(yīng)求解邏輯程序需要的loop為了增加實(shí)驗(yàn)數(shù)據(jù)的可信度，我們對n15、ratio0.5的22DLP(n,m)類程序在

本文編號：3972839