圖論模型與算法在航天器下行數(shù)據(jù)故障診斷知識(shí)循環(huán)依賴缺陷檢測(cè)中的應(yīng)用

王 蕊 沈 星* 吳 偉 潘順良

(1.南京航空航天大學(xué)航空學(xué)院, 南京 210016; 2.北京東方計(jì)量測(cè)試研究所, 北京 100094;3.北京空間飛行器總體設(shè)計(jì)部, 北京 100094)

1 引言

為確認(rèn)在軌航天器的運(yùn)行狀態(tài),保障飛行任務(wù)的正常開展,地面飛控人員需要實(shí)時(shí)監(jiān)測(cè)航天器下行的遙測(cè)參數(shù),并對(duì)其正確性進(jìn)行診斷。隨著航天器構(gòu)造越來(lái)越復(fù)雜,下行遙測(cè)速率也越來(lái)越高。得益于中國(guó)第二代中繼衛(wèi)星天地測(cè)控通信系統(tǒng)的建設(shè),目前天和核心艙的下行遙測(cè)速率已經(jīng)達(dá)到了1.2 Gbps[1],較天舟系列貨運(yùn)飛船提升了1 個(gè)數(shù)量級(jí)[2],較神舟系列載人飛船提升約3 個(gè)數(shù)量級(jí)[3]。中國(guó)空間站構(gòu)造復(fù)雜,并常駐航天員,其下行遙測(cè)參數(shù)的故障診斷不能簡(jiǎn)單地依靠若干門限,必須考慮各遙測(cè)參數(shù)以及上行遙控指令之間的依賴關(guān)系。

中國(guó)空間站等航天器從地面電性能測(cè)試開始就配套故障診斷系統(tǒng)[4],并最終在軌應(yīng)用。航天器下行數(shù)據(jù)故障診斷系統(tǒng)屬于專家系統(tǒng)[5-7]的一種,其核心在于專家知識(shí)庫(kù)和推理引擎[8-9]。故障診斷推理引擎根據(jù)存在于知識(shí)庫(kù)中的診斷知識(shí),依據(jù)下行遙測(cè)參數(shù)和上行遙控指令,得出各遙測(cè)參數(shù)是否正常的結(jié)論,并發(fā)布給地面飛控人員。對(duì)于專家系統(tǒng)而言,知識(shí)獲取是制約其應(yīng)用的瓶頸問(wèn)題[10]。雖然研究人員針對(duì)航天器下行數(shù)據(jù)故障診斷系統(tǒng)錄入了大量的診斷知識(shí),但其中依然存在缺陷的診斷知識(shí),其中較為典型的一類知識(shí)缺陷是循環(huán)依賴,比如遙測(cè)參數(shù)A 的診斷知識(shí)依賴于遙測(cè)參數(shù)B,而遙測(cè)參數(shù)B 的診斷知識(shí)又和遙測(cè)參數(shù)A 相關(guān)。

圖論[11-12]是應(yīng)用數(shù)學(xué)的重要分支,從經(jīng)典的哥尼斯堡七橋問(wèn)題[13]、哈密頓圈問(wèn)題[14]等,到現(xiàn)代的機(jī)器學(xué)習(xí)算法[15-18],圖論都發(fā)揮了重要的作用。本文將遙測(cè)參數(shù)診斷知識(shí)中蘊(yùn)藏的依賴關(guān)系抽象為有向圖中的頂點(diǎn)和有向邊,把診斷知識(shí)中的循環(huán)依賴檢測(cè)問(wèn)題抽象為有向圖中的環(huán)搜索問(wèn)題,應(yīng)用經(jīng)典拓?fù)渑判蛩惴?、Kosaraju 算法[19]、Tarjan 算法[19]及本文提出的改進(jìn)Tarjan 算法開展診斷知識(shí)的缺陷檢測(cè)。

2 診斷知識(shí)分析

2.1 故障診斷知識(shí)庫(kù)

為實(shí)現(xiàn)航天器下行數(shù)據(jù)的故障診斷,中國(guó)空間站等航天器采用了基于腳本的故障診斷系統(tǒng)。對(duì)于每個(gè)遙測(cè)參數(shù),都可以錄入一段診斷腳本,描述遙測(cè)參數(shù)所屬設(shè)備或子系統(tǒng)的運(yùn)行狀態(tài)以及切換過(guò)程,并明確該遙測(cè)參數(shù)在不同狀態(tài)下的值域判斷邏輯,如圖1 所示。

圖1 航天器下行數(shù)據(jù)故障診斷系統(tǒng)示意圖Fig.1 Schematic diagram of spacecraft downlink data fault diagnosis system

圖2 是其中一個(gè)典型的診斷知識(shí)示例,描述了某電壓量遙測(cè)參數(shù)A001 的診斷知識(shí)。其狀態(tài)切換與SBKJ、SBGJ、QBF、QZF 等上行指令相關(guān),而其值域則與某電流量遙測(cè)參數(shù)A002 相關(guān),即遙測(cè)參數(shù)A001 的診斷知識(shí)腳本中描述了如何根據(jù)SBKJ、SBGJ、QBF、QZF 等上行指令確定當(dāng)前參數(shù)所屬設(shè)備的運(yùn)行狀態(tài),再根據(jù)不同的狀態(tài)得出正常值域的范圍(所述值域與遙測(cè)參數(shù)A002 相關(guān))。

圖2 遙測(cè)參數(shù)A001 的診斷知識(shí)示意圖Fig.2 Schematic diagram of diagnostic knowledge of the telemetry data A001

由圖2 可知,遙測(cè)參數(shù)A001 的診斷知識(shí)腳本中出現(xiàn)了相關(guān)指令和遙測(cè)參數(shù)A002。由于對(duì)所有的下行遙測(cè)參數(shù)均可以書寫對(duì)應(yīng)的故障診斷知識(shí)腳本,因此診斷知識(shí)中存在大量的不同下行遙測(cè)參數(shù)間的依賴關(guān)系。

2.2 循環(huán)依賴缺陷

在圖2 所示遙測(cè)參數(shù)A001 的診斷知識(shí)中,其值域與參數(shù)A002 相關(guān)。若參數(shù)A002 的診斷知識(shí)如圖3 所示,即參數(shù)A002 的狀態(tài)切換過(guò)程與遙測(cè)參數(shù)A001 一致,其值域與參數(shù)A001 相關(guān)。由于參數(shù)A001 的值域也與參數(shù)A002 相關(guān),這樣就構(gòu)成了一組循環(huán)依賴的診斷知識(shí)。顯然出現(xiàn)循環(huán)依賴的參數(shù)A001 的診斷知識(shí)和參數(shù)A002的診斷知識(shí)是不完備的,因?yàn)槿粼谠O(shè)備開啟且主機(jī)模式下這2 個(gè)遙測(cè)參數(shù)同時(shí)異常,但其遙測(cè)值依然滿足大于4.9 且小于5.1 的比值關(guān)系,則故障診斷系統(tǒng)并不會(huì)診斷出異常。

圖3 遙測(cè)參數(shù)A002 的診斷知識(shí)示意圖Fig.3 Schematic diagram of diagnostic knowledge of the telemetry data A002

即使對(duì)遙測(cè)參數(shù)A002 的診斷知識(shí)按圖4 所示進(jìn)行加強(qiáng)改進(jìn),即當(dāng)參數(shù)A002 遙測(cè)值＜2 時(shí),可以診斷出異常。但通過(guò)分析可知,其與參數(shù)A001之間的比值關(guān)系判斷是冗余的,因?yàn)樵趨?shù)A001的診斷知識(shí)中已經(jīng)進(jìn)行了該比值關(guān)系的判斷。

圖4 改進(jìn)后的遙測(cè)參數(shù)A002 診斷知識(shí)示意圖Fig.4 Schematic diagram of improved diagnostic knowledge of the telemetry data A002

因此,若不同遙測(cè)參數(shù)的診斷知識(shí)中出現(xiàn)了循環(huán)依賴,一般而言意味著出現(xiàn)如下診斷知識(shí)缺陷:①故障診斷知識(shí)中可能存在不完備的表述;②故障診斷知識(shí)中可能存在冗余。

3 有向圖模型及經(jīng)典圖算法

3.1 有向圖模型構(gòu)建

有向圖D是指一個(gè)二元組(V(D),E(D)),其中V(D)表示頂點(diǎn)的集合,E(D)表示有向邊集合;在有向圖D中,E(D)中的每一個(gè)元素(即1 個(gè)有向邊)對(duì)應(yīng)于V(D)中的1 對(duì)有序元素(即2 個(gè)頂點(diǎn))e=(x,y),其中x為1 個(gè)有向邊的起點(diǎn),y為這個(gè)有向邊的終點(diǎn);此外,用頂點(diǎn)出度表示起點(diǎn)為該頂點(diǎn)的有向邊的數(shù)量,用頂點(diǎn)入度表示終點(diǎn)為該頂點(diǎn)的有向邊的數(shù)量[20]。本文所述的有向圖D不考慮2 個(gè)頂點(diǎn)之間存在多個(gè)有向邊的情況,即有向圖D為有向簡(jiǎn)單圖。

當(dāng)至少存在1 條路徑可以由頂點(diǎn)xs到頂點(diǎn)xe,則稱頂點(diǎn)xs至頂點(diǎn)xe可達(dá)。若有向圖D中存在2 個(gè)頂點(diǎn)相互可達(dá),則稱有向圖D中存在環(huán)。而若一個(gè)有向圖D中的任意2 個(gè)頂點(diǎn)相互可達(dá),則稱有向圖D是強(qiáng)連通(Strongly Connected);有向圖D的極大強(qiáng)連通子圖稱為有向圖D的強(qiáng)連通分量(Strongly Connected Components, SCC)。

針對(duì)本文所述航天器下行數(shù)據(jù)故障診斷系統(tǒng)中的診斷知識(shí)庫(kù),構(gòu)建有向圖Df= (Vf(D),Ef(D)),其中Vf(D)中的每個(gè)頂點(diǎn)對(duì)應(yīng)1 個(gè)獨(dú)立的遙測(cè)參數(shù),而Ef(D)中的每一個(gè)有向邊則表示其起點(diǎn)對(duì)應(yīng)遙測(cè)參數(shù)的診斷知識(shí)與該有向邊終點(diǎn)對(duì)應(yīng)的遙測(cè)參數(shù)相關(guān)。

至此,遙測(cè)參數(shù)故障診斷知識(shí)中的循環(huán)依賴檢測(cè)問(wèn)題,就可抽象為有向圖Df中的環(huán)搜索問(wèn)題。對(duì)于本文構(gòu)建的有向圖Df,所有故障診斷知識(shí)中的循環(huán)依賴都對(duì)應(yīng)于有向圖Df中的環(huán),且這些環(huán)都存在于有向圖Df的SCC 中。

3.2 經(jīng)典算法

3.2.1 拓?fù)渑判蛩惴?/p>

當(dāng)拓?fù)渑判蛩惴╗21]應(yīng)用于診斷知識(shí)的循環(huán)依賴檢測(cè)問(wèn)題時(shí),其運(yùn)算步驟如下:

1)根據(jù)Vf(D)和Ef(D),統(tǒng)計(jì)出Df中所有頂點(diǎn)的入度,記錄在列表List(Vf(D))中,此列表的元素個(gè)數(shù)為Vf(D)中的頂點(diǎn)個(gè)數(shù),且每個(gè)元素中有對(duì)應(yīng)頂點(diǎn)的入度信息。

2)掃描List(Vf(D))中所有入度為0 的元素,對(duì)于每個(gè)入度為0 的元素l,找到其對(duì)應(yīng)的頂點(diǎn)x,并根據(jù)Ef(D)找出所有起點(diǎn)為x的有向邊e,將所有e指向的終點(diǎn)對(duì)應(yīng)的List(Vf(D))中元素的入度減去1;從List(Vf(D))中刪除元素l。

3)反復(fù)執(zhí)行步驟2,若列表List(Vf(D))已空,或者執(zhí)行步驟2 后的列表List(Vf(D))與執(zhí)行前相同,則執(zhí)行步驟4。

4)若列表List(Vf(D))為空,則診斷知識(shí)中不存在循環(huán)依賴;否則List(Vf(D))中的每個(gè)元素所對(duì)應(yīng)的遙測(cè)參數(shù)都處于循環(huán)依賴中。

上述拓?fù)渑判驒z測(cè)算法通過(guò)執(zhí)行1 次廣度優(yōu)先搜索,即可得出診斷知識(shí)中是否存在循環(huán)依賴的結(jié)論,其算法的時(shí)間復(fù)雜度為O(V+E),其中V代表Vf(D)中的頂點(diǎn)數(shù)目,而E代表Ef(D)中的有向邊數(shù)目。

3.2.2 Kosaraju 算法

Kosaraju 算法[22]通過(guò)正反2 次深度優(yōu)先搜索過(guò)程確定有向圖中的SCC,也可以用于診斷知識(shí)的循環(huán)依賴檢測(cè),運(yùn)算步驟如下:

1)對(duì)有向圖Df中的所有頂點(diǎn)Vf(D),根據(jù)Ef(D)以后序深度優(yōu)先搜索方式進(jìn)行遍歷入棧(棧Stack),所述后序深度優(yōu)先是指先遞歸訪問(wèn)起點(diǎn)為當(dāng)前頂點(diǎn)的有向邊指向的終點(diǎn),再入棧當(dāng)前頂點(diǎn);記錄每個(gè)頂點(diǎn)的入棧時(shí)間。

2)將Ef(D)中的每個(gè)有向邊反序,得到反序有向圖D′f=(Vf(D),E′f(D))。

3)將Stack 中棧頂?shù)捻旤c(diǎn)出棧,若該頂點(diǎn)已被步驟3 處理過(guò),則執(zhí)行步驟4;若該頂點(diǎn)未被步驟3 處理過(guò),則由該頂點(diǎn)在反序有向圖D′f中對(duì)應(yīng)的頂點(diǎn)開始,根據(jù)E′f(D)進(jìn)行深度優(yōu)先搜索,記錄由該頂點(diǎn)能夠遍歷到的所有頂點(diǎn),這些頂點(diǎn)就構(gòu)成了有向圖Df的一個(gè)SCC,并標(biāo)記這些頂點(diǎn)已被步驟3 處理過(guò)。

4)若Stack 已空,則算法結(jié)束;否則,繼續(xù)步驟3。

Kosaraju 算法通過(guò)執(zhí)行2 次深度優(yōu)先搜索,可以得出有向圖Df中的所有SCC,其算法的時(shí)間復(fù)雜度也為O(V+E)。

3.2.3 Tarjan 算法

Tarjan 算法[23]可以僅通過(guò)1 次深度優(yōu)先搜索過(guò)程就確定有向圖中的SCC,從而實(shí)現(xiàn)診斷知識(shí)的循環(huán)依賴檢測(cè)。與Kosaraju 算法類似,Tarjan算法對(duì)圖Df中的所有頂點(diǎn)Vf(D),根據(jù)Ef(D)以先序深度優(yōu)先搜索方式進(jìn)行遍歷入棧,所述先序深度優(yōu)先是指先訪問(wèn)當(dāng)前頂點(diǎn),再遞歸訪問(wèn)起點(diǎn)為當(dāng)前頂點(diǎn)的有向邊指向的終點(diǎn),每次訪問(wèn)時(shí)執(zhí)行如下步驟:

1)訪問(wèn)頂點(diǎn)時(shí)首先記錄1 個(gè)該頂點(diǎn)的入棧時(shí)間,并初始化另一個(gè)稱為可達(dá)最小入棧時(shí)間的值為同一時(shí)間;在Ef(D)中找出所有以該頂點(diǎn)為起點(diǎn)的有向邊,對(duì)于每個(gè)有向邊(x,y)執(zhí)行步驟2;隨后判斷,若該頂點(diǎn)的入棧時(shí)間與可達(dá)最小入棧時(shí)間相同,則執(zhí)行步驟3。

2)若y對(duì)應(yīng)的頂點(diǎn)尚未入棧,則對(duì)y執(zhí)行步驟1,并將x的可達(dá)最小入棧時(shí)間更新為x的可達(dá)最小入棧時(shí)間和y的可達(dá)最小入棧時(shí)間中的較小值;若y對(duì)應(yīng)的頂點(diǎn)已入棧,則將x的可達(dá)最小入棧時(shí)間更新為x的可達(dá)最小入棧時(shí)間和y的入棧時(shí)間中的較小值。

3)執(zhí)行出棧操作,直至步驟1 的當(dāng)前訪問(wèn)頂點(diǎn)出棧,這些頂點(diǎn)構(gòu)成有向圖Df的1 個(gè)SCC。

Tarjan 算法僅通過(guò)1 次深度優(yōu)先搜索,即可得出有向圖Df的中的所有SCC,其算法的時(shí)間復(fù)雜度也為O(V+E)。

3.3 改進(jìn)算法

引入圖論模型后,可以應(yīng)用上述拓?fù)渑判?、Kosaraju、Tarjan 等經(jīng)典算法來(lái)檢測(cè)故障診斷知識(shí)中的循環(huán)依賴缺陷,但考慮到航天器下行數(shù)據(jù)故障診斷系統(tǒng)的診斷知識(shí)會(huì)經(jīng)常迭代,為了在迭代時(shí)提示用戶所更新的診斷知識(shí)是否存在循環(huán)依賴的缺陷,就需要在每次診斷知識(shí)迭代時(shí)開展缺陷檢測(cè),這個(gè)檢測(cè)過(guò)程會(huì)引入較大的運(yùn)算量,對(duì)于中國(guó)空間站這種復(fù)雜航天器,該檢測(cè)過(guò)程的運(yùn)算量將更加龐大,甚至?xí)绊懼R(shí)更新的實(shí)時(shí)性。因此,本文在分析故障診斷知識(shí)迭代特點(diǎn)的基礎(chǔ)上,提出了一種改進(jìn)Tarjan 算法,以降低循環(huán)依賴缺陷檢測(cè)的運(yùn)算量。

3.3.1 故障診斷知識(shí)的迭代由于故障診斷知識(shí)的迭代是以各遙測(cè)參數(shù)為單位進(jìn)行的,用戶往往針對(duì)某個(gè)特定的少量遙測(cè)參數(shù)進(jìn)行診斷知識(shí)的更新,而無(wú)需對(duì)所有的遙測(cè)參數(shù)進(jìn)行故障診斷知識(shí)迭代。若可以在對(duì)所有遙測(cè)參數(shù)的診斷知識(shí)進(jìn)行全范圍循環(huán)依賴缺陷檢測(cè)前,對(duì)一些無(wú)需進(jìn)行全范圍搜索即可得出結(jié)論的情況進(jìn)行過(guò)濾,就可以極大降低系統(tǒng)的開銷。

3.3.2 改進(jìn)Tarjan 算法

改進(jìn)Tarjan 算法的核心思想是首先判斷某次診斷知識(shí)的迭代更新是否改變了有向圖Df的SCC 特性,如不改變,則不再進(jìn)行診斷知識(shí)的缺陷檢測(cè);同時(shí)在每次全范圍搜索后,保留各SCC 的記錄,并優(yōu)先檢測(cè)所迭代遙測(cè)參數(shù)所屬的SCC 是否依然全連通,從而降低進(jìn)行全范圍搜索的可能性。

具體算法如下:

1)初始化時(shí),對(duì)有向圖Df利用Tarjan 算法搜索得到所有SCC,并記錄其中頂點(diǎn)數(shù)量≥2 的部分,記錄為Qf;

2)當(dāng)1 個(gè)遙測(cè)參數(shù)的診斷知識(shí)更新時(shí),若其舊版診斷知識(shí)已檢測(cè)出存在循環(huán)依賴缺陷,則執(zhí)行步驟3,否則執(zhí)行步驟5;

3)比對(duì)新版診斷知識(shí)與舊版診斷知識(shí)中相關(guān)遙測(cè)參數(shù)的范圍,若范圍增大或者保持不變,則提示依然存在循環(huán)依賴缺陷,否則執(zhí)行步驟4;

4)在遙測(cè)參數(shù)所屬SCC 中,再次進(jìn)行小范圍的Tarjan 算法,若依然保持全連通性,則直接提示依然存在循環(huán)依賴缺陷,否則執(zhí)行步驟6;

5)比對(duì)新版診斷知識(shí)與舊版診斷知識(shí)中相關(guān)遙測(cè)參數(shù)的范圍,若范圍縮小或者保持不變,則提示正常,否則執(zhí)行步驟6;

6)對(duì)有向圖Df利用Tarjan 算法重新搜索1 次所有SCC,并將其中頂點(diǎn)數(shù)量≥2 的部分更新為Qf,若本遙測(cè)參數(shù)對(duì)應(yīng)的頂點(diǎn)在更新后的Qf中,則提示存在循環(huán)依賴缺陷,否則提示正常。

由上述步驟可知,改進(jìn)Tarjan 算法并未影響單次Tarjan 執(zhí)行過(guò)程,而是通過(guò)步驟3 和步驟5來(lái)避免后續(xù)較為復(fù)雜的Tarjan 執(zhí)行過(guò)程,從而達(dá)到降低運(yùn)算量的目的。

4 算法對(duì)比及驗(yàn)證

4.1 算法對(duì)比

拓?fù)渑判蛩惴āosaraju 算法和Tarjan 算法都 以O(shè)(V+E)的時(shí)間復(fù)雜度判斷有向圖Df中是否存在環(huán),但Kosaraju 算法和Tarjan 算法還可以得出Df中的所有SCC,這在實(shí)際的診斷知識(shí)缺陷檢測(cè)中十分有用,可提示用戶進(jìn)行針對(duì)性調(diào)整。在不考慮空間復(fù)雜度時(shí),由于Tarjan 算法僅需進(jìn)行1 次深度優(yōu)先搜索,而Kosaraju 算法則需要進(jìn)行2 次深度優(yōu)先搜索,因此Tarjan 算法的執(zhí)行效率優(yōu)于Kosaraju 算法。

綜合對(duì)比后,Tarjan 算法在診斷知識(shí)的循環(huán)依賴檢測(cè)中的綜合表現(xiàn)更優(yōu);而本文提出的改進(jìn)Tarjan 算法可以有效減少具體執(zhí)行Tarjan 過(guò)程的次數(shù),帶來(lái)更低的運(yùn)算開銷。

4.2 仿真結(jié)果

構(gòu)造包含500 000 個(gè)頂點(diǎn)的有向圖,其中分別有6‰、12‰、18‰、24‰、30‰、36‰、42‰、48‰、54‰和60‰的頂點(diǎn)存在循環(huán)依賴問(wèn)題,仿真200 次,其中本文提出的改進(jìn)Tarjan 算法有1%的可能僅執(zhí)行步驟3 或步驟5 即可得出結(jié)論,則各算法執(zhí)行時(shí)間的對(duì)比圖如圖5 所示。

由圖5 可知,拓?fù)渑判蛩惴ǖ暮臅r(shí)最少,但是由于其無(wú)法得出Df中的所有SCC,因此無(wú)法在實(shí)際工作中實(shí)際應(yīng)用;Tarjan 算法耗時(shí)優(yōu)于Kosaraju算法,而本文提出的改進(jìn)Tarjan 算法較Tarjan 算法更優(yōu),且循環(huán)依賴越嚴(yán)重,降低運(yùn)算開銷效果越明顯。

圖5 不同算法執(zhí)行時(shí)間對(duì)比Fig.5 Comparison of execution time of various algorithms

4.3 改進(jìn)Tarjan 算法的執(zhí)行效果驗(yàn)證

將改進(jìn)Tarjan 算法實(shí)際應(yīng)用于某型號(hào),統(tǒng)計(jì)一段時(shí)間內(nèi)僅執(zhí)行步驟3 或步驟5(無(wú)需執(zhí)行步驟4 和步驟6)即可得出結(jié)論的次數(shù),計(jì)算得到這些次數(shù)相對(duì)于總診斷知識(shí)迭代次數(shù)的比率,如表1 所示。

表1改進(jìn)Tarjan算法僅執(zhí)行步驟3或5的比例Table 1Therateofstep3onlyandstep5onlyofthe improvedTarjanalgorithm單位:%

如表1 所示,改進(jìn)Tarjan 算法在實(shí)際運(yùn)行中避免了70%以上的全范圍或小范圍Tarjan 搜索過(guò)程,從而大幅降低了系統(tǒng)的計(jì)算開銷。

5 結(jié)論

航天器下行數(shù)據(jù)故障診斷系統(tǒng)作為專家系統(tǒng)的一種典型實(shí)現(xiàn),存在知識(shí)獲取瓶頸。經(jīng)過(guò)分析,一類典型的診斷知識(shí)缺陷是不同遙測(cè)參數(shù)的診斷知識(shí)中存在循環(huán)依賴。本文通過(guò)將診斷知識(shí)中的循環(huán)依賴檢測(cè)問(wèn)題抽象為有向圖中的環(huán)搜索問(wèn)題,從而得以應(yīng)用經(jīng)典的拓?fù)渑判蛩惴?、Kosaraju算法和Tarjan 算法開展診斷知識(shí)的缺陷檢測(cè),并結(jié)合診斷知識(shí)經(jīng)常迭代更新的特點(diǎn),提出了一種改進(jìn)Tarjan 算法。

1)將拓?fù)渑判?、Kosaraju 算法、Tarjan 算法等經(jīng)典算法引入問(wèn)題解決過(guò)程,對(duì)比發(fā)現(xiàn)了Tarjan算法的優(yōu)勢(shì);

2)考慮到診斷知識(shí)的迭代以單個(gè)遙測(cè)參數(shù)為單位進(jìn)行,在Tarjan 算法執(zhí)行前,對(duì)無(wú)需執(zhí)行Tarjan 核心步驟即可得出檢測(cè)結(jié)論的部分進(jìn)行過(guò)濾,設(shè)計(jì)的改進(jìn)Tarjan 算法在有效檢測(cè)診斷知識(shí)的循環(huán)依賴缺陷的同時(shí),可大幅降低了系統(tǒng)的運(yùn)算開銷。