【摘要】：自動(dòng)推理是人工智能領(lǐng)域的重要研究內(nèi)容之一,推理方法的設(shè)計(jì)與實(shí)現(xiàn)是核心。作為與歸結(jié)推理方法互補(bǔ)的推理方法,擴(kuò)展規(guī)則推理方法得到了國內(nèi)外眾多學(xué)者的認(rèn)可。擴(kuò)展規(guī)則作為自動(dòng)推理領(lǐng)域一種新的推理規(guī)則,在特定測試用例上有著獨(dú)有的特性和優(yōu)勢。目前擴(kuò)展規(guī)則推理方法的研究主要集中在命題邏輯領(lǐng)域完備推理算法,在命題邏輯領(lǐng)域不完備推理算法以及非經(jīng)典邏輯領(lǐng)域推理算法上目前仍處于起步階段。本文針對命題邏輯,設(shè)計(jì)并實(shí)現(xiàn)了基于擴(kuò)展規(guī)則的不完備推理框架。并且在此基礎(chǔ)上,將擴(kuò)展規(guī)則引入非經(jīng)典邏輯,設(shè)計(jì)并實(shí)現(xiàn)了典型非經(jīng)典邏輯——命題模態(tài)邏輯的擴(kuò)展規(guī)則推理方法。眾多推理問題在求解過程中均可轉(zhuǎn)化為SAT問題的求解,局部搜索由于貪心模式的收斂性和隨機(jī)模式的多元性能夠很大程度地加快SAT求解算法的速度,本文將該思想和擴(kuò)展規(guī)則深入結(jié)合。由于極大項(xiàng)的變換方式過于機(jī)械,導(dǎo)致擴(kuò)展規(guī)則方法處理公式的規(guī)模比較局限。本文針對擴(kuò)展規(guī)則推理求解問題的特性,利用子句集中的“極大項(xiàng)”概念設(shè)計(jì)了一種反向求解策略,進(jìn)而設(shè)計(jì)并實(shí)現(xiàn)基于擴(kuò)展規(guī)則推理的局部搜索算法的框架。在此基礎(chǔ)上,為了使得極大項(xiàng)搜索過程更加適配該框架,提出了一種基于精確格局檢測實(shí)現(xiàn)和雙向半擴(kuò)展規(guī)則策略的兩階段局部搜索算法ERACC(Extension Rule based on Accurately Configuration Checking)。在完善命題邏輯領(lǐng)域推理框架的基礎(chǔ)上,本文進(jìn)一步將擴(kuò)展規(guī)則推理方法推廣到命題模態(tài)邏輯領(lǐng)域中。根據(jù)Kripke語義模型針對S5公理系統(tǒng)提出了一種基于擴(kuò)展規(guī)則推理的并行命題模態(tài)邏輯推理算法(Parallel Propositional Modal Clausal Reasoning based on Novel Extension Rule,PPMCRNER),并與串行算法作了大量對比。本文提出的擴(kuò)展規(guī)則類算法從不同角度提升了命題邏輯和非經(jīng)典邏輯的推理效率。基于擴(kuò)展規(guī)則推理的局部搜索算法突破了傳統(tǒng)擴(kuò)展規(guī)則推理對公式規(guī)模的局限,求解效率有了極大提高,使得擴(kuò)展規(guī)則推理方法不再受公式規(guī)模制約,可以用于知識編譯和可能性推理等多方面的應(yīng)用。PPMCRNER算法在不可滿足的子句集上的推理具有良好的加速比,為高時(shí)間復(fù)雜性的模態(tài)推理方法的進(jìn)一步研究提供了一種可行方案。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP181

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 張斌,高全杰,應(yīng)保勝,王家青;實(shí)例推理和規(guī)則推理在實(shí)例修改中的應(yīng)用[J];計(jì)算機(jī)工程;2005年13期

2 邢乃寧,高紅梅,孫志揮;一種綜合范例推理和規(guī)則推理的發(fā)現(xiàn)技術(shù)[J];南京師范大學(xué)學(xué)報(bào)(工程技術(shù)版);2001年01期

3 江志農(nóng);王慧;魏中青;;基于案例與規(guī)則推理的故障診斷專家系統(tǒng)[J];計(jì)算機(jī)工程;2011年01期

4 宋欣;郭偉;王志勇;;基于回歸分析和規(guī)則推理的實(shí)例調(diào)整機(jī)制[J];天津大學(xué)學(xué)報(bào);2009年02期

5 李彬;王紅衛(wèi);楊劍波;郭敏;;基于置信規(guī)則推理的庫存控制方法[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年07期

6 楊麗彬;李海林;;基于云模型定性規(guī)則推理的分類方法[J];計(jì)算機(jī)時(shí)代;2011年03期

7 譚超;曹鵬;�，撍�;閆芳;杜鵬;張吉堂;;范例與規(guī)則推理在超聲檢測工藝制訂上的應(yīng)用[J];煤炭技術(shù);2011年12期

8 陸l，

本文編號：2565469