[發明專利]歐拉圖的構造方法及基于該方法進行測試序列優化的方法

有效

• 申請號: 201210555457.X
• 申請日: 2012-12-19
• 公開（公告）號: CN103049656B
• 公開（公告）日: 2017-04-12
• 發明（設計）人: 楊志杰;徐寧;呂旌陽;王財進;王瑞;王丁;劉佳
• 申請（專利權）人: 中國鐵道科學研究院;中國鐵道科學研究院通信信號研究所;北京市華鐵信息技術開發總公司;北京銳馳國鐵智能運輸系統工程技術有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 北京凱特來知識產權代理有限公司11260
• 代理人: 鄭立明,趙鎮勇

1.一種歐拉圖的構造方法，其特征在于，該方法包括：

判斷有向圖中各個頂點的出度與入度是否平衡，其中，有向圖中所有的頂點間的弧均有出入方向，出度為以當前頂點為起始點的弧的總數，入度為以當前頂點為終點的弧的總數；

若頂點A的出度與入度的差為W，則查找距離所述頂點A最近的W個頂點，分別以所述W個頂點為起始點構建以所述頂點A為終點的重復弧，或分別以所述頂點A為起始點分別構建以所述W個頂點為終點的重復弧。

2.根據權利要求1所述的方法，其特征在于，該方法還包括：

根據弗洛伊德Floyd算法計算所述有向圖的距離矩陣與路由矩陣，并根據所述距離矩陣與所述路由矩陣查找距離所述頂點A最近的W個頂點；

其中，所述距離矩陣表示兩個頂點最短路徑的長度，所述路由矩陣表示各個頂點的連接路徑。

3.根據權利要求1所述的方法，其特征在于，該方法還包括：

當所述有向圖中重復弧的數量最少，且每個重復弧的費用權值最小時，所述重復弧的總費用最低，其中重復弧的費用權值為該弧包含的測試案例的個數；

minz=Σ(i,j)∈Eωijxij]]>

其表達式為：s.tΣjxij-Σjxji=bi0≤xij≤cij;]]>

其中，s.t.為約束條件，為頂點i的出度，為頂點i的入度，b_i為頂點i的供給量，為有向圖的總費用，ω_ij為弧的費用權值，x_ij為頂點i到頂點j中費用為ω_ij的弧個數，c_ij為弧個數的允許最大值。

4.一種測試序列優化的方法，其特征在于，該方法包括：基于權利要求1-3任一項所述的方法為有向圖添加重復弧；

通過弗羅萊Fleury算法對添加重復弧后的有向圖進行歐拉回路的計算，獲得以某一頂點為起始點并通過所有弧至少一次的測試序列。

5.根據權利要求4所述的方法，其特征在于，該方法還包括：

通過回溯法對所述有向圖的路由矩陣進行回溯，獲得所有重復弧的兩頂點對應的最短路徑；

使用所述重復弧的兩頂點對應的最短路徑替換所述測試序列中的重復弧。

6.根據權利要求5所述的方法，其特征在于，所述使用所述重復弧的兩頂點對應的最短路徑替換所述測試序列中的重復弧之后還包括：

將測試序列中所有弧的費用權值相加獲得測試序列的總費用；所述總費用表示完成該測試序列所需費用，當重復弧的總費用最低時，測試序列的總費用最低。