【摘要】：基于模型診斷是人工智能領域內的一個重要研究方向,求解極小沖突集在基于模型診斷中有著重要應用.在對結合CSISE-Tree求解沖突集方法深入研究的基礎上,根據(jù)沖突集求解特征重構了結合枚舉樹的計算沖突集的過程,提出基于深度優(yōu)先反向搜索求解沖突集的方法.針對CSISE-Tree方法求解時占用內存空間與元件總數(shù)指數(shù)級相關的缺點,構建反向深度搜索方法減小求解時所占用內存空間;針對CSISE-Tree方法不能對部分非極小的沖突集進行剪枝的問題,給出對非沖突集和更多非極小的沖突集進行剪枝的方法,有效減少了求解時調用SAT(Boolean SATisfiability problem)求解器的次數(shù);實驗結果表明,與CSISE-Tree方法相比,本文提出的方法求解效率有明顯的提升,并避免了求解時的內存爆炸問題.
[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.
【作者單位】： 吉林大學計算機科學與技術學院;符號計算與知識工程教育部重點實驗室(吉林大學);吉林大學軟件學院;
【基金】：國家自然科學基金(No.61133011,No.61402196,No.61272208,No.61003101,No.61170092) 吉林省科技發(fā)展計劃項目基金(No.20140520067JH) 浙江省自然科學基金(No.LY16F020004)
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

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

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

3 姜云飛,林笠;用對分HS-樹計算最小碰集[J];軟件學報;2002年12期

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

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

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

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

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

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

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

相關會議論文 前1條

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

相關碩士學位論文 前3條

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

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

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

，

本文編號：2191885