黃子惟，馬小龍

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

0 引言

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

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

1 總體分析

1.1 測試流程分析

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

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

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

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

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

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

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

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

1.2 有向圖

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

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

1.3 依賴矩陣

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

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

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

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

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

依賴矩陣的形式為

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

2 矩陣分析

2.1 列消元法

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

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

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

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

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

2.2 最小路徑覆蓋算法

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

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

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

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

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

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

圖4 二分圖Fig.4 Bipartite graph

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

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

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

2.3 割點算法

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

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

圖5 割點算法Fig.5 Cut point algorithm

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將評估優(yōu)化后的模型部署到專家?guī)熘?。需要在日常測試中對專家?guī)爝M行維護，及時自動化更新數(shù)據(jù)和模型，以保證專家?guī)斓臏蚀_性和可靠性。

3.3 實施注意事項

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

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

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

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

4 結(jié)束語

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