本文關(guān)鍵詞：一種改進的回答集邏輯程序分割方法及程序化簡研究

  更多相關(guān)文章： 非單調(diào)邏輯 回答集編程 分割集 程序分割 程序化簡

【摘要】：人工智能是計算機科學(xué)中的一個重要分支,其中的知識表示與推理則是一門通過刻畫知識和理解邏輯,以計算機為載體實現(xiàn)人類智能為目的的學(xué)科。非單調(diào)邏輯是進行知識表示與推理的主要手段。本文研究的回答集編程(ASP:Answer Set Programming)則是非單調(diào)邏輯的研究熱點。隨著回答集編程領(lǐng)域多年以來的發(fā)展,其求解器已比較成熟。然而,回答集編程求解器的效率問題依舊是該領(lǐng)域的研究重點。在ASP求解器提速的發(fā)展過程中,Lifschitz和Turner在1994年提出了分割集(Splitting Set)和程序分割(Program Splitting)的概念,并從理論上證明了一個ASP邏輯程序可以通過分割集被劃分為底部(bottom)和頂部(top)兩部分,并根據(jù)這兩部分的回答集可以計算得到原程序的回答集。分割集和程序分割的提出,為ASP求解器的提速帶來了新思路。在后續(xù)的時間里,分割集和程序分割得到了不斷的推廣。然而,Lifschitz和Turner當(dāng)初定義的分割集需要滿足較為苛刻的條件,在實際情況中往往會出現(xiàn)一個ASP邏輯程序的分割集就只有空集和程序中全部原子構(gòu)成的集合,而這樣的分割集對于分割程序是沒有任何意義的。本文對Lifschitz和Turner提出的分割集和程序分割方法進行了探討和研究,所獲得的主要成果具體如下:首先,把Lifschitz和Turner原來定義的分割集擴展為任意原子集,同時為正規(guī)邏輯程序提出了新程序分割方法,及把新程序分割方法擴展到了析取邏輯程序,和提出強程序分割方法。在分割集可以為任意原子集的情況下,程序分割方法的適用范圍得到了擴展。其次,本文分析了任意原子集構(gòu)成的分割集對新程序分割的性能影響,找出主要性能瓶頸所在并給出了改進的方案。同時,通過實驗數(shù)據(jù)驗證了使用新分割集和新程序分割方法求解一個ASP邏輯程序的回答集比直接求解更快,提速效果大致維持在2到3倍。最后,在分析新分割集對新程序分割方法的性能影響之時,得到結(jié)論:如果分割集中原子都被原程序的每個回答集所滿足,那么使用這樣的分割集來分割程序可以有效降低原程序回答集的計算復(fù)雜性�；谶@個發(fā)現(xiàn),本文把分割集的應(yīng)用擴展到了程序化簡當(dāng)中,即通過程序結(jié)論(Consequence)去化簡ASP邏輯程序。程序化簡的目的依舊是為了讓回答集程序的求解提速。本文提出的新分割集與新程序分割給求解回答集程序的提速帶來了實質(zhì)性的效果,并由此推廣分割集的思想到程序化簡這樣的實際應(yīng)用當(dāng)中,為回答集程序的求解提速帶來了新思路。
【學(xué)位授予單位】：中山大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP18

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 柴振榮;邏輯程序的操作優(yōu)化問題[J];管理科學(xué)文摘;1995年03期

2 王克文,周立柱,陳火旺;擴充析取邏輯程序的爭論語義(英文)[J];軟件學(xué)報;2000年03期

3 張永剛,孫吉貴;約束邏輯程序的一個新語義研究[J];廣西師范大學(xué)學(xué)報(自然科學(xué)版);2003年01期

4 謝紅梅,王建東,周勇;含有文字序邏輯程序的一種辯論語義[J];南京航空航天大學(xué)學(xué)報;2005年01期

5 譚成予;董紅斌;梁意文;錢立進;;邏輯程序的事實維護[J];計算機工程與應(yīng)用;2006年09期

6 周勇;朱梧i，

本文編號：1152676