【摘要】：基于模型診斷是人工智能領(lǐng)域內(nèi)的一個(gè)重要研究方向,求解極小沖突集在基于模型診斷中有著重要應(yīng)用.在對結(jié)合CSISE-Tree求解沖突集方法深入研究的基礎(chǔ)上,根據(jù)沖突集求解特征重構(gòu)了結(jié)合枚舉樹的計(jì)算沖突集的過程,提出基于深度優(yōu)先反向搜索求解沖突集的方法.針對CSISE-Tree方法求解時(shí)占用內(nèi)存空間與元件總數(shù)指數(shù)級相關(guān)的缺點(diǎn),構(gòu)建反向深度搜索方法減小求解時(shí)所占用內(nèi)存空間;針對CSISE-Tree方法不能對部分非極小的沖突集進(jìn)行剪枝的問題,給出對非沖突集和更多非極小的沖突集進(jìn)行剪枝的方法,有效減少了求解時(shí)調(diào)用SAT(Boolean SATisfiability problem)求解器的次數(shù);實(shí)驗(yàn)結(jié)果表明,與CSISE-Tree方法相比,本文提出的方法求解效率有明顯的提升,并避免了求解時(shí)的內(nèi)存爆炸問題.
[Abstract]:Model based diagnosis is an important research direction in the field of artificial intelligence. Solving minimal conflict sets has an important application in model based diagnosis. On the basis of deep research on the method of solving conflict set with CSISE-Tree, this paper reconstructs the process of computing conflict set combined with enumeration tree according to the feature of conflict set solving, and puts forward a method of solving conflict set based on depth first reverse search. In order to solve the problem that the memory occupied by the CSISE-Tree method is related to the exponential level of the total number of components, the inverse depth search method is constructed to reduce the memory space occupied in the solution, and the CSISE-Tree method can not prune some non-minimal conflict sets. The pruning method for non-conflict sets and more non-minimal conflict sets is given, which effectively reduces the number of calls to SAT (Boolean SATisfiability problem) solvers in the solution, and the experimental results show that the efficiency of the proposed method is significantly improved compared with that of the CSISE-Tree method. The problem of memory explosion is avoided.
【作者單位】： 吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;符號計(jì)算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室(吉林大學(xué));吉林大學(xué)軟件學(xué)院;
【基金】：國家自然科學(xué)基金(No.61133011,No.61402196,No.61272208,No.61003101,No.61170092) 吉林省科技發(fā)展計(jì)劃項(xiàng)目基金(No.20140520067JH) 浙江省自然科學(xué)基金(No.LY16F020004)
【分類號】：TP18

【相似文獻(xiàn)】

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

1 劉曉平;季浩;石慧;;一種基于最小沖突集的約束沖突消解方法[J];工程圖學(xué)學(xué)報(bào);2010年02期

2 方敏;一種識別最小沖突集的實(shí)用方法[J];合肥工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);1999年01期

3 姜云飛,林笠;用對分HS-樹計(jì)算最小碰集[J];軟件學(xué)報(bào);2002年12期

4 林笠;基于ENV診斷模型的建立[J];暨南大學(xué)學(xué)報(bào)(自然科學(xué)與醫(yī)學(xué)版);2001年05期

5 欒尚敏,戴國忠,陳由迪;基于邏輯的一種診斷方法[J];貴州工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2002年04期

6 趙相福;歐陽丹彤;;可用于診斷產(chǎn)生的計(jì)算碰集的新方法[J];吉林大學(xué)學(xué)報(bào)(理學(xué)版);2006年03期

7 張立明;歐陽丹彤;趙相福;;一種基于ATMS的求解所有極小沖突集的新方法[J];計(jì)算機(jī)工程與科學(xué);2007年11期

8 代樹武,孫輝先;基于模型故障診斷中的沖突求解[J];控制理論與應(yīng)用;2003年04期

9 林笠;遞歸建立HS-樹計(jì)算最小碰集[J];微電子學(xué)與計(jì)算機(jī);2002年02期

10 王肖;趙相福;;用CHS-tree基于集合勢的方法計(jì)算極小碰集[J];計(jì)算機(jī)集成制造系統(tǒng);2014年02期

相關(guān)會議論文 前1條

1 李占山;王濤;孫吉貴;寇飛宏;;基于模型推理的系統(tǒng)修復(fù)與重用設(shè)計(jì)研究[A];2006年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會論文集[C];2006年

相關(guān)碩士學(xué)位論文 前3條

1 張立明;基于一致性診斷中若干問題研究[D];吉林大學(xué);2009年

2 趙相福;基于模型診斷中的關(guān)鍵算法研究[D];吉林大學(xué);2006年

3 艾陽;求解極小碰集的ROBDD算法的研究與分析[D];吉林大學(xué);2011年

，

本文編號：2191885