基于有向圖的評分改進(jìn)算法設(shè)計與實(shí)現(xiàn)

陳佳伊，李紅波，崔偉燦，王 吉，應(yīng)正波

（浙江中控技術(shù)股份有限公司，杭州 310053）

0 引言

一所現(xiàn)代化工廠成功的一個重要因素就是具有較高技術(shù)水平和豐富經(jīng)驗的現(xiàn)場操作人員。傳統(tǒng)的師傅帶徒弟的一對一培訓(xùn)模式由于效率低下，已經(jīng)逐漸被淘汰，采用虛擬控制仿真培訓(xùn)系統(tǒng)不僅可以大大提高培訓(xùn)效果，節(jié)省培訓(xùn)費(fèi)用，縮短培訓(xùn)時間，而且可以降低裝置操作的不確定性，減少或避免事故發(fā)生。同時仿真培訓(xùn)可以培養(yǎng)一人多崗，一專多能的高素質(zhì)人才，為企業(yè)的長期發(fā)展提供人才保障，是國內(nèi)外公認(rèn)的煤化工、石油化工等領(lǐng)域最高效的現(xiàn)代化技能培訓(xùn)與考核手段。

目前OTS 仿真培訓(xùn)的評分算法采用的是單向鏈表的數(shù)據(jù)結(jié)構(gòu)，評分規(guī)則單一，對評分配置的限制諸多，難以滿足工程上對于評分規(guī)則靈活性的要求。本文提出了一種評分關(guān)系依賴模型，改進(jìn)了評分規(guī)則算法，使得工程實(shí)施時的靈活度和便利性大大提高。

1 建立評分關(guān)系依賴模型

圖1 有向圖表示步驟間依賴關(guān)系示例圖Fig.1 An example diagram of a directed graph of inter-step dependencies

在培訓(xùn)過程中，教員使用評分組態(tài)軟件設(shè)計一套評分規(guī)則對學(xué)員的現(xiàn)場操作進(jìn)行考察，構(gòu)成評分規(guī)則的基本元素為評分步驟。步驟表示操作員的一個操作動作，不同步驟根據(jù)不同的規(guī)則組合在一起，用于評定操作員的操作順序是否正確，操作是否達(dá)到預(yù)期目標(biāo)。

一個步驟可以抽象為有向圖中的一個節(jié)點(diǎn)，在此將步驟記為S。步驟與步驟之間存在依賴關(guān)系，依賴關(guān)系的類型有時間關(guān)系、順序關(guān)系和引用關(guān)系。時間關(guān)系用于考察兩個關(guān)聯(lián)的步驟是否在設(shè)定的時間關(guān)系內(nèi)完成，順序關(guān)系考察兩個關(guān)聯(lián)的步驟是否按照設(shè)定的次序被執(zhí)行，引用關(guān)系表示一個步驟引用另一個步驟的狀態(tài)作為該步驟的評分依據(jù)。例如，步驟2 引用步驟1 的完成狀態(tài)作為該步驟開始的條件。

步驟的最終計算結(jié)果與步驟間的依賴關(guān)系有關(guān)，步驟的時間關(guān)聯(lián)和順序關(guān)聯(lián)也可抽象為有向圖中的一個節(jié)點(diǎn)，分別記為T 和O，引用關(guān)系和函數(shù)關(guān)系以箭頭方式表示。在評分關(guān)系依賴模型中存在多個依賴關(guān)系確定步驟狀態(tài)的情況，記為{O,T-＞S}，其中O,T-＞S 的含義即為順序依賴關(guān)系O 和時間依賴關(guān)系T 共同確定步驟S 的狀態(tài)。圖1 表示了這種依賴關(guān)系，其中用圓弧連接兩條有向邊表示節(jié)點(diǎn)間存在“與”的關(guān)系，“或”關(guān)系未在圖中做出特殊標(biāo)記。

2 評分算法的設(shè)計與實(shí)現(xiàn)

2.1 構(gòu)建最小函數(shù)依賴集

步驟的規(guī)則屬性間存在函數(shù)依賴關(guān)系，該函數(shù)依賴關(guān)系反映了規(guī)則屬性間的關(guān)聯(lián)性和數(shù)據(jù)的完整性約束。而由于各步驟規(guī)則屬性間存在錯綜復(fù)雜的依賴關(guān)系，為了使依賴關(guān)系簡單、明了，減少在實(shí)際運(yùn)算過程中的重復(fù)運(yùn)算，首先需要求解模型的最小函數(shù)依賴[1]集以簡化運(yùn)算。在求解最小函數(shù)依賴集的過程中，傳統(tǒng)的算法能解決相應(yīng)問題，但不夠直觀，將有向圖的表達(dá)運(yùn)用到函數(shù)依賴關(guān)系中去，會使得問題的求解更加清晰、直觀。

下面給出最小函數(shù)依賴集F'的求解算法：

圖2 深度遍歷模型示例圖Fig.2 Depth traversing model sample

1）根據(jù)函數(shù)依賴集F，畫出步驟間依賴關(guān)系的有向圖，其中各節(jié)點(diǎn)表示各個步驟或時間、順序關(guān)系、引用關(guān)系，有向邊表示函數(shù)關(guān)系，有向邊箭頭的起始結(jié)點(diǎn)為決定因子。

2）考察圖中每條邊，如果出現(xiàn)平行邊，則刪除存在“與”的關(guān)系的那組邊，由于在函數(shù)依賴集中不會出現(xiàn)完全相同的函數(shù)依賴關(guān)系，所以這里的平行邊只會存在于一條獨(dú)立邊與一組“與”邊中的其中一條。

3）如果圖中某個結(jié)點(diǎn)到達(dá)另一個節(jié)點(diǎn)的路徑有多條，則刪除直接相連的邊，保留經(jīng)過其他節(jié)點(diǎn)到達(dá)的邊。經(jīng)過簡化后，消除了由傳遞函數(shù)依賴導(dǎo)致的多余函數(shù)依賴。

4）將變換后的圖中屬性間的關(guān)系轉(zhuǎn)換為函數(shù)依賴關(guān)系的表達(dá)，得到的函數(shù)依賴集即為最小函數(shù)依賴集F'。

2.2 環(huán)的存在與檢測

得到步驟關(guān)系依賴圖，在對步驟進(jìn)行拓?fù)渑判蚯?，需要對步驟間的依賴關(guān)系進(jìn)行環(huán)路檢測，保證得到的步驟關(guān)系依賴圖是一個有向無環(huán)圖[2]。如果存在環(huán)路，步驟間接引用自身的狀態(tài)將會導(dǎo)致死循環(huán)。例如，步驟1 引用步驟3 的考試結(jié)束狀態(tài)作為步驟開始的條件，步驟3 引用步驟2的考試結(jié)束狀態(tài)作為步驟開始的條件，步驟2 又引用步驟1 的考試結(jié)束狀態(tài)作為步驟開始的條件，此時步驟1 又去獲取步驟3 的考試狀態(tài)，造成死循環(huán)。

這里采用著色法檢測有向圖中是否存在環(huán)路，檢測算法如下：

1）分別對每個節(jié)點(diǎn)進(jìn)行深度遍歷。

2）對每個節(jié)點(diǎn)的狀態(tài)進(jìn)行標(biāo)記，白色代表此節(jié)點(diǎn)還沒有被處理；灰色代表此節(jié)點(diǎn)正在被處理，或者說他的兒孫們還沒有被處理；黑色代表此節(jié)點(diǎn)以及其所有兒孫都已經(jīng)被處理過了。

3）在深度遍歷時，如果到達(dá)了一個灰色的節(jié)點(diǎn)，說明該有向圖中存在環(huán)路。

圖3 評分關(guān)系模型示例圖Fig.3 An example of scoring relationship model

以圖2 為例，以深度優(yōu)先搜索S1 節(jié)點(diǎn)時，先將S1 標(biāo)記為灰色，依次尋找子節(jié)點(diǎn)得到S1-＞S3，到達(dá)S3 節(jié)點(diǎn)時發(fā)現(xiàn)不存在子節(jié)點(diǎn)，將S3 標(biāo)記為黑色。繼續(xù)搜索得到S1-＞S2-＞S4-＞S3,到達(dá)S3 節(jié)點(diǎn)時發(fā)現(xiàn)不存在子節(jié)點(diǎn)，將S1、S2 標(biāo)記為黑色，此時對S1 節(jié)點(diǎn)搜索完畢，繼續(xù)搜索S2 節(jié)點(diǎn)，先將S2 標(biāo)記為灰色，依次尋找子節(jié)點(diǎn)得到S2-＞S4-＞S5-＞S6-＞S2，此時S2 的狀態(tài)為灰色，該圖中存在環(huán)路。

2.3 建立拓?fù)湫蛄袌D

以下面的評分關(guān)系模型為例，如圖3 所示。

在未經(jīng)排序優(yōu)化前，步驟根據(jù)默認(rèn)的順序進(jìn)行計算，過程如下：

1）計算得到S1 的評分結(jié)果。

2）對S2 進(jìn)行評分計算-＞獲取本輪評分中S1 和上一輪評分中S3 的結(jié)果-＞得到S2 的結(jié)果。

3）對S3 進(jìn)行評分計算-＞獲取本輪評分中S1 的結(jié)果-＞得到S3 的結(jié)果。

4）對S4 進(jìn)行評分計算-＞獲取本輪評分中S1 和上一輪評分中S6 的結(jié)果-＞得到S4 的結(jié)果。

5）對S5 進(jìn)行評分計算-＞獲取本輪評分中S3 和上一輪評分中S4、S6 的結(jié)果-＞得到S5 的結(jié)果。

6）對S6 進(jìn)行評分計算-＞獲取本輪評分中S4、S5 的結(jié)果-＞得到S5 的結(jié)果。

由此可見，采用默認(rèn)的計算順序會導(dǎo)致評分計算輪次混雜，步驟的依賴數(shù)據(jù)未更新，甚至出現(xiàn)引用同一個步驟得到的計算結(jié)果不一致的問題，而實(shí)際應(yīng)用中的模型遠(yuǎn)比上述模型復(fù)雜的多，更容易出現(xiàn)難以預(yù)料的結(jié)果。建立拓?fù)湫蛄袌D[3]，對評分中的最小元素進(jìn)行計算順序的排序可以規(guī)避這種問題，拓?fù)渑判蛩惴ㄈ缦拢?/p>

① 在步驟關(guān)系依賴圖中選一個沒有前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)并且輸出。

② 從圖中刪除該節(jié)點(diǎn)和所有以它為尾的邊。

③ 重復(fù)上述兩步，直至所有節(jié)點(diǎn)輸出，或者當(dāng)前圖中不存在無前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)為止，最后得到整理好的拓?fù)湫蛄小?/p>

以圖2 的關(guān)系模型為例，展示拓?fù)渑判蜻^程：

圖4 變換后的步驟關(guān)系圖Fig.4 Transformed step diagram

首先，發(fā)現(xiàn)S6 和S1 沒有前驅(qū)節(jié)點(diǎn)，隨機(jī)選擇一個輸出，這里選擇先輸出S1，刪除和S1 有關(guān)的邊，得到如圖4(a)所示結(jié)果。

然后，繼續(xù)尋找沒有前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)，發(fā)現(xiàn)S6 沒有前驅(qū)節(jié)點(diǎn)，輸出S6，刪除和S6 有關(guān)的邊，得到如圖4（b）的結(jié)果。

然后，又發(fā)現(xiàn)S4 和S3 都是沒有前驅(qū)節(jié)點(diǎn)的，這里選擇先輸出S4，得到如圖4（c）結(jié)果。

然后，繼續(xù)輸出沒有前驅(qū)節(jié)點(diǎn)的S3，此時只剩下兩個沒有前驅(qū)節(jié)點(diǎn)的節(jié)點(diǎn)S2 和S5，輸出S2 和S5。最后全部節(jié)點(diǎn)輸出完成，整理得到該圖的一個拓?fù)湫蛄袨椋篠1-＞S6-＞S4-＞S3-＞S2-＞S5。

此時按照拓?fù)漤樞蛞来斡嬎悴襟E狀態(tài)，可以保證步驟引用的每個依賴數(shù)據(jù)都是本輪次的最新數(shù)據(jù)。

3 結(jié)論

本文提出了一種基于有向圖的工業(yè)仿真培訓(xùn)系統(tǒng)評分關(guān)系依賴模型，解決了在評分計算中的步驟狀態(tài)循環(huán)引用檢測問題，提高了評分規(guī)則設(shè)置的靈活性。同時對原有的評分算法進(jìn)行了改進(jìn)，提出了一種計算順序重排算法，解決了在同一輪次中計算結(jié)果不一致的問題，規(guī)避了風(fēng)險。