黃子惟，馬小龍

（北京宇航系統(tǒng)工程研究所，北京，100076）

0 引言

為考核運(yùn)載火箭復(fù)雜系統(tǒng)的性能，必須對其進(jìn)行全面的測試，現(xiàn)有的測試方法主要采用分層測試的方式，將系統(tǒng)分為子系統(tǒng)，然后分別進(jìn)行測試，最后再測試整個(gè)系統(tǒng)［1］。然而，這種方法存在局限性，包括狀態(tài)轉(zhuǎn)換耗時(shí)長、受約束多、無法充分考慮所有潛在故障通路等。

為了克服這些問題，需要采用更先進(jìn)的測試方法來提高測試效率并降低測試成本。一個(gè)有效的方法是將測試項(xiàng)目與故障建立有向圖模型，以矩陣形式建立關(guān)聯(lián)，矩陣即成為測試的數(shù)學(xué)模型，計(jì)算故障檢出率、系統(tǒng)測試性、查找冗余測試等工作可以轉(zhuǎn)化為矩陣計(jì)算和矩陣優(yōu)化的問題。采用列消元法檢測冗余測試，用最小路徑覆蓋算法來檢測最小測試，用割點(diǎn)算法來確定測試項(xiàng)目的關(guān)鍵程度，從而幫助制定更高效的測試策略。采用AO*算法進(jìn)行矩陣優(yōu)化，可以簡化測試過程，提高測試效率［2］。

1 總體分析

1.1 測試流程分析

測試流程如圖1所示，可以分為以下步驟［3］：

圖1 測試流程Fig.1 Test model flow block diagram

a）分析測試需求。根據(jù)系統(tǒng)的功能要求、性能指標(biāo)、安全性等需求形成需求說明書，據(jù)此制定測試計(jì)劃，以確保測試的全面性和有效性。

b）制定測試計(jì)劃。制定測試計(jì)劃應(yīng)該包括測試的范圍、測試的目標(biāo)、測試的計(jì)劃安排、測試資源和測試方法。在制定測試計(jì)劃時(shí)，需要考慮系統(tǒng)的復(fù)雜性和測試的覆蓋性，確保測試計(jì)劃能夠覆蓋系統(tǒng)的各個(gè)方面。

c）設(shè)計(jì)測試項(xiàng)目。應(yīng)該根據(jù)需求分析和測試計(jì)劃設(shè)計(jì)測試項(xiàng)目。測試項(xiàng)目應(yīng)該包括正常情況、冗余測試、邊界測試等，測試項(xiàng)目應(yīng)該可重復(fù)執(zhí)行，便于測試系統(tǒng)對輸入反饋的一致性，同時(shí)應(yīng)搭建盡可能接近真實(shí)的測試環(huán)境。

d）執(zhí)行測試。在測試執(zhí)行階段，應(yīng)該按照測試計(jì)劃和測試項(xiàng)目，編寫測試腳本并執(zhí)行自動(dòng)化測試。

e）測試管理。測試執(zhí)行后，應(yīng)該對測試中發(fā)現(xiàn)的缺陷進(jìn)行分類和跟蹤管理，未通過測試的項(xiàng)目應(yīng)根據(jù)測試結(jié)果修改完成后執(zhí)行回歸測試，直至測試合格為止。

f）測試報(bào)告。應(yīng)該對測試結(jié)果進(jìn)行分析和總結(jié)，根據(jù)測試結(jié)果和問題管理情況生成測試報(bào)告。

1.2 有向圖

有向圖是一種形式化的建模方法，用于描述系統(tǒng)中各個(gè)組件之間的因果依賴關(guān)系［4］。如圖2所示，由節(jié)點(diǎn)和邊組成的有向圖，其中節(jié)點(diǎn)表示系統(tǒng)中的測試項(xiàng)目，邊表示這些項(xiàng)目之間的因果依賴關(guān)系。有向圖可以用于系統(tǒng)可測試性分析和故障診斷，通過對因果依賴關(guān)系進(jìn)行建模和分析，可以實(shí)現(xiàn)高效的故障隔離和診斷。多信號有向圖可以用來生成測試序列，并進(jìn)行復(fù)雜系統(tǒng)的可測試性分析。也可以通過“模型驅(qū)動(dòng)”的方法，直接根據(jù)系統(tǒng)的設(shè)計(jì)模型生成有向圖。

圖2 測試有向圖Fig.2 Testing directed graphs

1.3 依賴矩陣

依賴矩陣可以用來描述系統(tǒng)中故障和測試項(xiàng)目之間的依賴關(guān)系，進(jìn)而用于分析測試相關(guān)特性、優(yōu)化測試設(shè)計(jì)［5］。

有向圖向依賴矩陣轉(zhuǎn)化的方法：

a）確定所有的節(jié)點(diǎn)，并為每個(gè)節(jié)點(diǎn)分配一個(gè)唯一的標(biāo)識符，例如用整數(shù)來表示；

b）根據(jù)節(jié)點(diǎn)的數(shù)量創(chuàng)建一個(gè)空的矩陣，這個(gè)矩陣的大小為N*N，其中N為節(jié)點(diǎn)的數(shù)量；

c）標(biāo)記依賴關(guān)系，根據(jù)圖形中的邊，標(biāo)記矩陣中的元素，如果節(jié)點(diǎn)i依賴于節(jié)點(diǎn)j，則矩陣中第j行第i列的元素為1，否則為0。

依賴矩陣的形式為

如式（1）所示，依賴矩陣可以幫助確定系統(tǒng)中各個(gè)信號之間的依賴關(guān)系，因此可以精確地檢測系統(tǒng)中的故障。當(dāng)系統(tǒng)中某個(gè)信號出現(xiàn)故障時(shí)，它可能會影響到其他信號的計(jì)算結(jié)果，進(jìn)而影響系統(tǒng)的正確性和性能。依賴矩陣定位故障所在的信號，進(jìn)而進(jìn)行修復(fù)。依賴矩陣可以根據(jù)系統(tǒng)中的信號數(shù)目進(jìn)行擴(kuò)展，因此可以適應(yīng)從單機(jī)測試到總體測試的不同規(guī)模測試場景。

2 矩陣分析

2.1 列消元法

通過對依賴矩陣進(jìn)行列消元，可以確定哪些測試是冗余的［6］。這些測試可以被刪除或替換為更有效的測試。列消元法利用依賴矩陣的列之間的線性關(guān)系，將其中一些列表示為其他列的線性組合形式，從而消除冗余信息。具體來說，列消元法可以分為以下步驟：

a）構(gòu)造增廣矩陣。將依賴矩陣和一個(gè)單位矩陣按列合并，構(gòu)造出一個(gè)增廣矩陣。

b）列主元消元。對增廣矩陣進(jìn)行列主元消元，將其轉(zhuǎn)化為行最簡形式，在進(jìn)行消元操作時(shí)，需要選取每一列中絕對值最大的元素作為主元素，將其他元素通過行變換轉(zhuǎn)化為零。

c）提取基本列。將行最簡形式的增廣矩陣按列劃分為2個(gè)矩陣，其中左邊的矩陣為依賴矩陣的行最簡形式，右邊的矩陣為單位矩陣的行最簡形式。此時(shí)左邊矩陣中不為零的列就是依賴矩陣的基本列，其他列則可以表示為基本列的線性組合形式。

通過列消元法，可以將依賴矩陣中的冗余信息消除，提取出基本列，從而減少矩陣的維度，用于優(yōu)化測試用例的選擇和生成，減少冗余測試，從而提高測試效率和覆蓋率。

2.2 最小路徑覆蓋算法

通過將依賴矩陣轉(zhuǎn)換為一個(gè)有向無環(huán)圖，可以使用最小路徑覆蓋算法來確定最少需要多少個(gè)測試來覆蓋所有可能的故障?？梢允褂肞ython將矩陣轉(zhuǎn)換為有向無環(huán)圖［7］，示例依賴矩陣M形式為

圖3為示例依賴矩陣M轉(zhuǎn)換后的有向無環(huán)圖。能更清楚地展示任務(wù)之間的依賴、順序和流程?？梢愿玫乩斫夂头治鋈蝿?wù)之間的依賴關(guān)系，從而有助于進(jìn)行優(yōu)化和決策。

圖3 有向無環(huán)圖Fig.3 Directed acyclinc graph

路徑覆蓋是指一組不相交的簡單路徑，這些路徑覆蓋了圖中的所有頂點(diǎn)，即每個(gè)頂點(diǎn)恰好在一條路徑上。最小路徑覆蓋就是指路徑覆蓋中包含最少路徑數(shù)的覆蓋方案。

最小路徑覆蓋算法可以通過以下步驟實(shí)現(xiàn)：

a）構(gòu)造二分圖。將有向無環(huán)圖轉(zhuǎn)換為一個(gè)二分圖，如圖4所示，其中左部節(jié)點(diǎn)對應(yīng)圖4中的所有源節(jié)點(diǎn)，右部節(jié)點(diǎn)對應(yīng)所有的匯節(jié)點(diǎn)。對于圖4中的每個(gè)邊(u，v)，將其轉(zhuǎn)換為一條從u對應(yīng)的左部節(jié)點(diǎn)到v對應(yīng)的右部節(jié)點(diǎn)的邊。

圖4 二分圖Fig.4 Bipartite graph

b）求二分圖的最大匹配。對于上一步構(gòu)造的二分圖，求出它的最大匹配。最大匹配是指二分圖中包含最多邊的一個(gè)匹配，可以使用匈牙利算法、Hopcroft-Karp算法等常用的最大匹配算法進(jìn)行求解。

c）構(gòu)造路徑覆蓋。將最大匹配中的匹配邊分解為若干條不相交的簡單路徑，這些路徑即為路徑覆蓋。在構(gòu)造過程中，可以使用深度優(yōu)先搜索或廣度優(yōu)先搜索等算法。

d）計(jì)算最小路徑覆蓋。計(jì)算得到的路徑覆蓋所包含的路徑數(shù)即為最小路徑覆蓋的路徑數(shù)。

2.3 割點(diǎn)算法

通過將依賴矩陣轉(zhuǎn)換為一個(gè)無向圖，并使用割點(diǎn)算法來確定哪些測試是關(guān)鍵測試，這些關(guān)鍵測試可以提高故障診斷的準(zhǔn)確性和效率［8］。

割點(diǎn)也被稱為關(guān)鍵節(jié)點(diǎn)或割點(diǎn)節(jié)點(diǎn)，是指如果將該節(jié)點(diǎn)從圖中刪除，會導(dǎo)致圖不連通的節(jié)點(diǎn)，如圖5所示。

圖5 割點(diǎn)算法Fig.5 Cut point algorithm

割點(diǎn)算法是基于深度優(yōu)先搜索（Depth-first Search，DFS）開展的，割點(diǎn)算法可以通過以下步驟實(shí)現(xiàn)：

a）對于每個(gè)節(jié)點(diǎn)v∈V，假設(shè)其在DFS 樹中的父節(jié)點(diǎn)為u，如果節(jié)點(diǎn)v在DFS 樹中沒有子節(jié)點(diǎn)或者子節(jié)點(diǎn)的后代節(jié)點(diǎn)中沒有回到節(jié)點(diǎn)v的，則節(jié)點(diǎn)u為割點(diǎn)。

b）如果節(jié)點(diǎn)v在DFS樹的根節(jié)點(diǎn)處，且有2個(gè)或2個(gè)以上的子節(jié)點(diǎn)，則節(jié)點(diǎn)v為割點(diǎn)。

割點(diǎn)算法的時(shí)間復(fù)雜度為O（V+E），其中V和E分別為圖的頂點(diǎn)數(shù)和邊數(shù)。

3 優(yōu)化依賴矩陣

使用AO*算法優(yōu)化依賴矩陣是一個(gè)常用的方法。具體而言，AO*算法從起點(diǎn)開始搜索，每次選擇距離起點(diǎn)最近的未擴(kuò)展節(jié)點(diǎn)進(jìn)行擴(kuò)展。在擴(kuò)展節(jié)點(diǎn)時(shí)，AO*算法計(jì)算節(jié)點(diǎn)到終點(diǎn)的估價(jià)函數(shù)值，將其作為節(jié)點(diǎn)的優(yōu)先級，以選擇下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。如果當(dāng)前節(jié)點(diǎn)到終點(diǎn)的路徑長度已經(jīng)超過當(dāng)前最優(yōu)路徑長度，則將當(dāng)前節(jié)點(diǎn)標(biāo)記為不可達(dá)，不再進(jìn)行擴(kuò)展，直到找到終點(diǎn)或者所有可達(dá)節(jié)點(diǎn)都被擴(kuò)展完成，AO*算法才停止搜索，并返回最短路徑和路徑長度。

3.1 估價(jià)函數(shù)及其優(yōu)化

根據(jù)依賴矩陣的特性，采用估價(jià)函數(shù)來估計(jì)從當(dāng)前狀態(tài)到達(dá)目標(biāo)狀態(tài)的代價(jià)，以便更快地搜索到最優(yōu)解。若定義估價(jià)函數(shù)為路徑的總長度或總代價(jià)，路徑長度可以表示任務(wù)的執(zhí)行時(shí)間、資源投入、可靠性等，最優(yōu)解通常為使路徑總長度最小的路徑集合。估價(jià)函數(shù)的優(yōu)點(diǎn)是可以比較準(zhǔn)確地預(yù)測當(dāng)前節(jié)點(diǎn)到終點(diǎn)的距離。

加權(quán)平均法是一種組合估價(jià)函數(shù)的方法，可以將多個(gè)估價(jià)函數(shù)進(jìn)行加權(quán)平均，得到一個(gè)更加準(zhǔn)確的估價(jià)函數(shù)。在優(yōu)化AO*算法的估價(jià)函數(shù)時(shí)，可以采用加權(quán)平均法來得到更加優(yōu)化的估價(jià)函數(shù)［9］。

具體而言，定義m個(gè)估價(jià)函數(shù)f1（n），…，fm（n），然后采用加權(quán)平均的方式將它們組合成一個(gè)新的估價(jià)函數(shù)f(n)。加權(quán)平均法的計(jì)算公式為

式中w1，…，wm分別表示估價(jià)f1(n)，…，fm(n)的權(quán)重，滿足w1+… +wm=1。

在應(yīng)用加權(quán)平均法優(yōu)化AO*算法的估價(jià)函數(shù)時(shí)，選擇不同的估價(jià)函數(shù)作為組合的基礎(chǔ)，可以根據(jù)測試時(shí)間長度和測試資源投入設(shè)計(jì)2 個(gè)估價(jià)函數(shù)f1(n) 和f2(n)，然后使用加權(quán)平均法將它們組合起來，得到一個(gè)更加準(zhǔn)確的估價(jià)函數(shù)，從而優(yōu)化AO*算法的搜索效率和搜索結(jié)果的質(zhì)量。

3.2 擴(kuò)展函數(shù)及其優(yōu)化

擴(kuò)展函數(shù)，用于從當(dāng)前狀態(tài)擴(kuò)展出下一步可能的狀態(tài)，并計(jì)算每個(gè)狀態(tài)的代價(jià)。節(jié)點(diǎn)擴(kuò)展策略是指在擴(kuò)展節(jié)點(diǎn)時(shí)選擇合適的優(yōu)先級。

可以通過建立專家?guī)靸?yōu)化擴(kuò)展函數(shù)［10］。

建立專家?guī)?，主要從過去的故障庫中，經(jīng)過機(jī)器學(xué)習(xí)訓(xùn)練得到專家?guī)炷Ｐ?。需要從故障庫中收集大量的?shù)據(jù)，這些數(shù)據(jù)包括故障類型、故障原因、解決方案等信息。同時(shí)需要對數(shù)據(jù)進(jìn)行清洗、去重、標(biāo)準(zhǔn)化等操作，以確保數(shù)據(jù)的質(zhì)量和一致性。然后對數(shù)據(jù)進(jìn)行特征提取，從原始數(shù)據(jù)中提取出有意義的特征，以用于后續(xù)的模型訓(xùn)練。選擇決策樹、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)等學(xué)習(xí)模型，并利用訓(xùn)練數(shù)據(jù)對模型進(jìn)行訓(xùn)練。同時(shí)，還可以根據(jù)專家經(jīng)驗(yàn)和知識，自定義來指導(dǎo)擴(kuò)展函數(shù)的生成。

將評估優(yōu)化后的模型部署到專家?guī)熘小Ｐ枰谌粘y試中對專家?guī)爝M(jìn)行維護(hù)，及時(shí)自動(dòng)化更新數(shù)據(jù)和模型，以保證專家?guī)斓臏?zhǔn)確性和可靠性。

3.3 實(shí)施注意事項(xiàng)

a）AO*算法陷入無限循環(huán)。

當(dāng)搜索算法試圖展開一個(gè)狀態(tài)時(shí)，如果它認(rèn)為展開該狀態(tài)會導(dǎo)致搜索結(jié)果變差，那么它可能會跳過該狀態(tài)。但是，如果該狀態(tài)實(shí)際上是搜索結(jié)果的一部分，那么搜索算法可能會陷入循環(huán)，反復(fù)嘗試展開該狀態(tài)。為避免這種情況，可以添加一個(gè)最大深度限制，以確保算法不會搜索太深，或者使用回溯技術(shù)來撤銷搜索過程中的某些步驟。

b）AO*算法會受到依賴矩陣大小的限制。

若依賴矩陣較大，可能會由于搜索時(shí)間過長或者占用內(nèi)存過多而導(dǎo)致性能下降，為避免這種情況，可以使用剪枝技術(shù)來減少搜索空間的大小。例如使用Alpha-Beta 剪枝技術(shù)或者使用迭代加深搜索來限制搜索的深度。同時(shí)也可以使用稀疏矩陣來優(yōu)化，將搜索狀態(tài)空間表示為一個(gè)稀疏矩陣。在搜索過程中，只需要存儲非零元素和相關(guān)信息，而不需要存儲零元素和無關(guān)信息，從而將減少內(nèi)存占用，加速搜索。

4 結(jié)束語

通過將測試過程和方法模型轉(zhuǎn)化為依賴矩陣，可提供更為清晰的可視化方式，更好地理解測試之間的依賴關(guān)系，可以量化測試方法之間的關(guān)聯(lián)度和依賴程度從而得到更加具體和可度量的結(jié)果，通過矩陣算法分析識別其中的冗余測試，結(jié)合圖論、專家?guī)旌蜋C(jī)器學(xué)習(xí)等手段，充分利用各種方法的優(yōu)勢，使得測試過程更為全面，提高測試方法的準(zhǔn)確性和智能化水平。