基于模型診斷是人工智能領(lǐng)域的熱門研究課題,彌補(bǔ)了傳統(tǒng)診斷方法的多種不足。其理論研究成果豐碩,并廣泛應(yīng)用于實(shí)際生產(chǎn)中,加快了人工智能的發(fā)展速度。通常分兩步對(duì)其求解:首先,求解給定電路系統(tǒng)的全部極小沖突集;然后,求解全部極小沖突集的全部極小碰集,即為給定電路系統(tǒng)的全部極小診斷解�？蓾M足問題(SAT)是經(jīng)典的NP問題,其理論研究及技術(shù)應(yīng)用發(fā)展成熟。很多問題都可以轉(zhuǎn)化為可滿足問題求解。國際上定期舉辦的SAT問題競(jìng)賽,使SAT求解器得到了快速的發(fā)展。因此,把極小沖突集求解問題轉(zhuǎn)化為SAT問題是一個(gè)很好的研究方向。CSRDSE方法是一種結(jié)合SAT問題求解極小沖突集的方法。根據(jù)枚舉樹結(jié)構(gòu)特點(diǎn)及沖突集相關(guān)推論,對(duì)枚舉樹中非沖突集的真子集節(jié)點(diǎn)及沖突集的真超集節(jié)點(diǎn)進(jìn)行剪枝,減少訪問節(jié)點(diǎn)數(shù)量,加快了問題的求解。本文在深度研究CSRDSE方法的基礎(chǔ)上,根據(jù)對(duì)電路結(jié)構(gòu)的分析,發(fā)現(xiàn)每個(gè)元件異常時(shí)對(duì)異常輸出的影響程度不同,與電路系統(tǒng)異常輸出端相關(guān)聯(lián)的元件對(duì)異常輸出的影響程度更大,且對(duì)異常輸出影響較大的元件之間的組合更可能是沖突集。根據(jù)上述發(fā)現(xiàn),提出了基于異常概率的極小沖突集求解方法(CSABP)。首先,給出了異常概率的定義,并給出了計(jì)算元件異常概率的算法SolveABP;然后,按照元件異常概率由大到小的順序生成枚舉樹,能夠先遍歷對(duì)異常輸出影響較大的元件構(gòu)成的節(jié)點(diǎn),以至于盡快的找到?jīng)_突集,減少對(duì)沖突集超集節(jié)點(diǎn)的判斷。實(shí)驗(yàn)結(jié)果表明,與CSRDSE方法相比,CSABP方法提高了問題求解效率。在CSABP方法的基礎(chǔ)上,結(jié)合枚舉樹的結(jié)構(gòu)特性和沖突集的子集更可能是極小沖突集的原理發(fā)現(xiàn):將沖突集中的元件在枚舉樹第一層的節(jié)點(diǎn)連同其子樹一起向左移動(dòng),提前搜索這些子樹,有利于提早找到極小沖突集。在判斷后續(xù)節(jié)點(diǎn)時(shí),先將當(dāng)前訪問節(jié)點(diǎn)同已找到的沖突集作對(duì)比,若是某個(gè)沖突集的超集,可免去對(duì)該節(jié)點(diǎn)進(jìn)行判斷;否則,調(diào)用求解器判斷該節(jié)點(diǎn)的沖突性�；谏鲜鱿敕�,提出了位置標(biāo)記的概念,用來調(diào)整枚舉樹狀態(tài)的變化。最后,將異常概率與位置標(biāo)記方法結(jié)合在一起,提出了基于異常概率和位置標(biāo)記的極小沖突集求解方法(CSABPPM)。實(shí)驗(yàn)結(jié)果表明,CSABPPM方法減掉了更多的冗余節(jié)點(diǎn),更好的解決了極小沖突集求解問題。
【學(xué)位單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2019
【中圖分類】：TP18
【文章目錄】：
摘要
abstract
第1章 緒論
    1.1 研究背景和意義
    1.2 研究現(xiàn)狀
    1.3 本文工作
第2章 基本知識(shí)
    2.1 基于模型診斷問題
    2.2 可滿足問題
    2.3 電路問題轉(zhuǎn)化為SAT問題
    2.4 本章小結(jié)
第3章 極小沖突集求解方法介紹
    3.1 基于CSSE-tree的極小沖突集求解方法
        3.1.1 相關(guān)推論及概念
        3.1.2 CSSE-tree基本思想
        3.1.3 CSSE-tree方法分析
    3.2 基于CSISE-tree的極小沖突集求解方法
        3.2.1 相關(guān)概念
        3.2.2 CSSE-tree基本思想
        3.2.3 CSSE-tree方法分析
    3.3 基于反向深度搜索的極小沖突集求解方法
        3.3.1 相關(guān)概念
        3.3.2 CSRDSE基本思想
        3.3.3 CSRDSE方法
        3.3.4 CSRDSE方法分析
    3.4 本章小結(jié)
第4章 基于異常概率的極小沖突集求解方法
    4.1 預(yù)備知識(shí)
    4.2 方法思想
    4.3 方法實(shí)現(xiàn)
    4.4 實(shí)驗(yàn)結(jié)果及分析
    4.5 本章小結(jié)
第5章 基于位置標(biāo)記的極小沖突集求解方法
    5.1 預(yù)備知識(shí)
    5.2 方法思想
    5.3 方法實(shí)現(xiàn)
    5.4 實(shí)驗(yàn)結(jié)果及分析
    5.5 本章小結(jié)
第6章 總結(jié)和展望
    6.1 工作總結(jié)
    6.2 工作展望
參考文獻(xiàn)
作者簡(jiǎn)介及在學(xué)期間所取得的科研成果
致謝

【相似文獻(xiàn)】

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

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

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

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

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

5 王藝源;歐陽丹彤;張立明;張永剛;;利用CSP求解極小碰集的方法[J];計(jì)算機(jī)研究與發(fā)展;2015年03期

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

7 欒尚敏,戴國忠;利用結(jié)構(gòu)信息的故障診斷方法[J];計(jì)算機(jī)學(xué)報(bào);2005年05期

8 徐旖旎;歐陽丹彤;劉夢(mèng);張立明;張永剛;;結(jié)合故障輸出結(jié)構(gòu)特征的極小沖突求解算法[J];計(jì)算機(jī)研究與發(fā)展;2018年11期

9 潘理;鄭紅;劉顯明;楊勃;;基于Petri網(wǎng)局部性的極大沖突集枚舉算法[J];電子學(xué)報(bào);2016年08期

10 劉燕麗;李初民;何琨;;基于優(yōu)化沖突集提高下界的MAXSAT完備算法[J];計(jì)算機(jī)學(xué)報(bào);2013年10期

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

1 邵繼業(yè);基于模型的故障診斷方法研究及在航天中的應(yīng)用[D];哈爾濱工業(yè)大學(xué);2009年

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

1 陶婭;基于異常概率和位置標(biāo)記的極小沖突集求解方法研究[D];吉林大學(xué);2019年

2 劉伯文;結(jié)合問題特征的基于模型診斷相關(guān)問題研究[D];吉林大學(xué);2018年

3 凡義;基于松弛沖突集改進(jìn)Max-SAT完備算法[D];華中科技大學(xué);2016年

4 徐俊潔;一種基于模型的故障診斷系統(tǒng)研究與實(shí)現(xiàn)[D];大連海事大學(xué);2010年

5 常偉;基于角色的訪問控制技術(shù)研究與應(yīng)用[D];南京航空航天大學(xué);2012年

6 何士玉;基于模型診斷的搜索算法研究及其在配電網(wǎng)中的應(yīng)用[D];西南交通大學(xué);2013年

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

8 云帆;求解極小碰集的遺傳算法及其相關(guān)算法的研究[D];吉林大學(xué);2007年

9 高松;牽引供電系統(tǒng)故障的基于模型診斷方法研究[D];西南交通大學(xué);2015年

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

本文編號(hào)：2859898