[發(fā)明專利]歐拉圖的構(gòu)造方法及基于該方法進(jìn)行測試序列優(yōu)化的方法

有效

• 申請?zhí)枺?/td>: 201210555457.X
• 申請日: 2012-12-19
• 公開（公告）號: CN103049656B
• 公開（公告）日: 2017-04-12
• 發(fā)明（設(shè)計）人: 楊志杰;徐寧;呂旌陽;王財進(jìn);王瑞;王丁;劉佳
• 申請（專利權(quán)）人: 中國鐵道科學(xué)研究院;中國鐵道科學(xué)研究院通信信號研究所;北京市華鐵信息技術(shù)開發(fā)總公司;北京銳馳國鐵智能運(yùn)輸系統(tǒng)工程技術(shù)有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 北京凱特來知識產(chǎn)權(quán)代理有限公司11260
• 代理人: 鄭立明,趙鎮(zhèn)勇

技術(shù)領(lǐng)域

本發(fā)明涉及中國列車運(yùn)行控制系統(tǒng)，尤其涉及一種歐拉圖的構(gòu)造方法及基于該方法進(jìn)行測試序列優(yōu)化的方法。

背景技術(shù)

測試案例為對列車車載設(shè)備某個功能特征進(jìn)行的驗證與測試。執(zhí)行特定測試案例要求系統(tǒng)必須到達(dá)此測試案例所需的初始狀態(tài)。這些初始狀態(tài)只有通過執(zhí)行特定系統(tǒng)功能才能達(dá)到，并且這些特定系統(tǒng)功能包含在其它測試案例中。

測試序列是通過一定的方法對測試案例進(jìn)行串聯(lián)，從而形成一個可以實際運(yùn)行的測試場景，并確保測試結(jié)束后，所有的測試案例都被測試過至少一次。測試序列不是隨意產(chǎn)生的，而是遵循一定的方法，將若干測試案例有序串聯(lián)起來，形成一個測試場景式的有序測試案例集。

由于測試案例數(shù)量龐大，并且車載設(shè)備功能復(fù)雜，在測試序列中，重復(fù)使用測試案例的情況較多。為了更方便的對測試序列進(jìn)行優(yōu)化，可將一組測試序列轉(zhuǎn)化為有向圖，列車各工作模式作為有向圖的頂點，測試子序列作為頂點之間的有向弧，測試子序列中所包含的測試案例數(shù)量看作有向弧的費(fèi)用。

現(xiàn)有技術(shù)中通過對有向圖進(jìn)行歐拉圖的構(gòu)造來優(yōu)化有向弧，以減少測試案例的重復(fù)使用。但是在進(jìn)行歐拉圖構(gòu)造時，輔助弧的添加個數(shù)較多，額外占用一定的內(nèi)存空間，影響了歐拉圖構(gòu)造的效率，并且，通過歐拉圖構(gòu)造后的有向圖重復(fù)弧的數(shù)量較大，導(dǎo)致測試序列的成本增加。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種歐拉圖的構(gòu)造方法及基于該方法進(jìn)行測試序列優(yōu)化的方法，減少了輔助空間的使用，提高了歐拉圖構(gòu)造的效率。

本發(fā)明的目的是通過以下技術(shù)方案實現(xiàn)的：

一種歐拉圖的構(gòu)造方法，該方法包括：

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

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

一種測試序列優(yōu)化的方法，該方法包括：

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

由上述本發(fā)明提供的技術(shù)方案可以看出，通過利用貪婪策略，使局部最優(yōu)達(dá)到全局最優(yōu)，逐步構(gòu)造最優(yōu)解，并減少了輔助空間的使用，提高了歐拉圖構(gòu)造的效率。

附圖說明

為了更清楚地說明本發(fā)明實施例的技術(shù)方案，下面將對實施例描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發(fā)明的一些實施例，對于本領(lǐng)域的普通技術(shù)人員來講，在不付出創(chuàng)造性勞動的前提下，還可以根據(jù)這些附圖獲得其他附圖。

圖1為本發(fā)明實施例一提供的一種歐拉圖的構(gòu)造方法的流程圖；

圖2為本發(fā)明實施例二提供的又一種歐拉圖的構(gòu)造方法的流程圖；

圖3為本發(fā)明實施例二提供的一種測試序列有向圖的示意圖；

圖4為本發(fā)明實施例二提供的一種構(gòu)造重復(fù)弧后的有向圖的示意圖；

圖5為本發(fā)明實施例三提供的一種測試序列優(yōu)化的方法的流程圖。

具體實施方式

下面結(jié)合本發(fā)明實施例中的附圖，對本發(fā)明實施例中的技術(shù)方案進(jìn)行清楚、完整地描述，顯然，所描述的實施例僅僅是本發(fā)明一部分實施例，而不是全部的實施例。基于本發(fā)明的實施例，本領(lǐng)域普通技術(shù)人員在沒有做出創(chuàng)造性勞動前提下所獲得的所有其他實施例，都屬于本發(fā)明的保護(hù)范圍。

實施例一

圖1為本發(fā)明實施例一提供的一種歐拉圖的構(gòu)造方法的流程圖，該方法主要包括如下步驟：

步驟101、判斷有向圖中各個頂點的出度與入度是否平衡。其中，頂點為列車的各個工作模式，有向圖中所有的頂點間的弧均有出入方向，出度為以當(dāng)前頂點為起始點的弧的總數(shù)，入度為以當(dāng)前頂點為終點的弧的總數(shù)，所述弧為工作模式間的測試子序列。

判斷有向圖是否為歐拉圖，主要判斷有向圖中各個頂點的出入度是否平衡，即判斷以當(dāng)前頂點為起始點的弧個數(shù)與以當(dāng)前頂點為終點的弧個數(shù)是否相同。

步驟102、若頂點A的出度與入度的差為W，則查找距離所述頂點A最近的W個頂點，分別以所述W個頂點為起始點構(gòu)建以所述頂點A為終點的重復(fù)弧，或分別以所述頂點A為起始點分別構(gòu)建以所述W個頂點為終點的重復(fù)弧。