基于拓撲排序的部隊輸送序列問題研究

吳曉東，楊 斌，朱桐生

(1.軍事交通學院 聯合投送系，天津300161;2.軍事交通學院 研究生管理大隊，天津300161;

3.駐鄭州鐵路局軍事代表辦事處，鄭州450000)

輸送序列是指部隊輸送的先后順序。大規(guī)模部隊輸送應優(yōu)先考慮輸送序列，只有按照輸送序列組織，盡量壓縮輸送持續(xù)時間，以確保在規(guī)定的輸送期限內完成輸送任務。不顧輸送序列，片面提高輸送進度，追求快速反應能力和應急機動能力，可能會打亂整個戰(zhàn)役部署，破壞作戰(zhàn)企圖的實現，造成嚴重后果。因此，確定部隊的輸送序列是進行部隊輸送的首要工作，按照輸送序列實施輸送是輸送組織的嚴格要求。本文通過建立序列樹模型以描述部隊輸送序列要求，設計相應的拓撲排序算法。

1 模型描述

多個部隊組成的集合A= (a1，a2，…，an)中，部隊的重要程度不盡相同。據此要求某些部隊在輸送中滿足特定的先后關系，但并不是所有的部隊在輸送中的先后關系都是明確的。如:有的部隊全體要求比另一部隊都提前到達;有的部隊要求有下屬部隊比另一部隊的下屬部隊提前到達;有的部隊相互間沒有關系。發(fā)現集合A是一個偏序集，即有如下定義。

(1)設L為一集合，x，y，z∈L，L的一個偏序是一個二元關系R，滿足:①xRx(自反性);②xRy∧yRx?x=y(反對稱性);③xRy∧yRz?xRz(傳遞性)。

具有偏序關系R的集合L稱為偏序集［1］，記為(L，R)。如果對每個x，y∈L，必有xRy或yRx，則稱R是集合上的全序關系。由某個集合上的一個偏序加強為該集合上的一個全序，這個操作稱為拓撲排序?？梢杂脽o圈圖表示一個偏序集，每個節(jié)點表示一個元素。如將無圈圖G中的所有頂點排成一個線性序列，使得圖G中任意一對頂點u和v，若(u，y)∈E(G)，則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序的序列，簡稱拓撲序列［2］。對于部隊輸送而言，簡單的偏序關系還不能完全描述序列要求，本文再進行如下定義。

(2)樹:無圈的連通圖稱為樹(又稱樹圖，記作T(V，E))。

(3)絕對優(yōu)先關系:樹中?非父子的2 個節(jié)點a、b，如果a比b重要(a』b)，且a的任一子節(jié)點都比b的任意子節(jié)點重要，稱a﹥b。反之，如果a沒有b重要(a『b)，且a的任一子節(jié)點都沒有b的任意子節(jié)點重要，稱a﹤b。如果a與b重要程度相同，稱a≒b。這3 種關系統(tǒng)稱為2 個節(jié)點具有絕對優(yōu)先關系。

(4)相對優(yōu)先關系:樹中?非父子的2 個節(jié)點a、b，如果a存在某一子節(jié)點比b和b的任意子節(jié)點重要，稱a』b。反之，如果a存在某一子節(jié)點沒有b和b的任意子節(jié)點重要，稱a『b。這2 種關系統(tǒng)稱為2 個節(jié)點具有相對優(yōu)先關系。

(5)節(jié)點相關性與無關性:具有絕對優(yōu)先關系和相對優(yōu)先關系的2 個節(jié)點稱為具有節(jié)點相關性，或2 個節(jié)點有相互關系。如果a與b重要程度沒有可比性，且a的任意子節(jié)點與b的任意子節(jié)點的重要程度都沒有可比性，稱2 個節(jié)點具備節(jié)點無關性，或稱2 個節(jié)點沒有相互關系，記為a＞＜b。

(6)序列樹:?非父子的2 個節(jié)點間存在節(jié)點相關性或者節(jié)點無關性關系的樹稱為序列樹。序列樹有如下性質。

①序列樹中的2 點a、b，如果a﹥b，則a中任一子節(jié)點a’與b中任意子節(jié)點b’都有關系a’﹥b’，且有a』b。如果a﹤b，則a中任一子節(jié)點a’與b中任意子節(jié)點b’都有關系a’﹤b’，且有a『b。

②序列樹中的3 點a、b、c，如果存在a﹥b，b﹥c，必然存在a﹥c。同理，如果存在a﹤b，b﹤c，必然存在a﹤c。如果存在a』b和b』c，必然存在a』c。同理，如果存在a『b和b『c，必然存在a『c。

③D=(d1，d2，…，dn)，S=(s1，s2，…，sn)是序列樹的中的點組成的2 個集合，如果有D＜S，則有D中的任一di﹤S中的任一sj。如果有D＞S，則有D中的任一di＞S中的任一sj。如果有D＞＜S，則有D中的任一di＞＜S中的任一sj。

根據以上定義，整個部隊輸送序列問題可以用序列樹來表示，每支部隊可以用節(jié)點來表示，部隊的隸屬關系可以用節(jié)點的父子關系表示，部隊輸送序列可以用節(jié)點間的相關關系表示。

2 決策樹算法

對于拓撲排序已經有的方法［3-5］，拓撲排序的算法思想通常描如下。

(1)在AOV 網中選一個沒有前趨的頂點且輸出。

(2)在網中刪去該頂點及其所發(fā)出的弧。

(3)重復(1)、(2)，直至輸出全部沒有前趨的頂點。

當過程結束時，如果網中的所有頂點均已輸出，則說明網中不存在回路，否則說明網中存在回路，相應的排序是不可行的。

考察輸送序列問題，根據上文所述依據與原則，可定性比較部隊間的重要程度，并能夠確定其中某些部隊的相互關系。但由于定性描述的局限性，難以明確所有部隊的相互關系，也就無法確定所有部隊的序列。AOV 網的排序方法雖然可以很好地表示頂點的相互關系，但是無法描述部隊的上下級層次隸屬關系，也難以表示部隊的不同方向與不同任務。考慮部隊的上下隸屬關系與“樹”的某些特性非常相似，通過樹的父子節(jié)點關系可以很好地描述部隊的上下級隸屬關系以及運輸中分方向、分屬性等特性。本文將輸送部隊建成一個分層的權重樹，一個部隊對應一個節(jié)點，父子節(jié)點代表上下級單位，通過對樹節(jié)點的依次搜索，實現對節(jié)點排序，從而實現運輸序列排定。算法思路如下:通過建立節(jié)點關系表、節(jié)點初始權重賦值、節(jié)點搜索排序3 個步驟實現。首先建立節(jié)點關系表，對既有節(jié)點關系進行分析與推理，然后通過一定算法對節(jié)點賦權重值，最后通過搜索確定節(jié)點的序列。

2.1 建立節(jié)點關系表

將節(jié)點間的關系用列表的方式完整的表達出來，稱該列表為節(jié)點關系表。建立節(jié)點關系表步驟如下。

(1)初始節(jié)點關系的確立。一是直接對節(jié)點關系的指定，即根據第一部分模型描述定義(4)、(5)確立;二是通過節(jié)點屬性及屬性間的優(yōu)先關系間接的指定，即依據序列樹的性質確立，這一步驟不明確，難以操作。

(2)為節(jié)點關系劃分優(yōu)先等級。根據節(jié)點關系的重要程度，可為節(jié)點關系明確優(yōu)先等級。可將所有的節(jié)點關系劃分為若干等級，等級低的關系服從于等級高的關系，其目的是為了節(jié)點關系出現沖突時進行疏解，要有明確的劃分方法。

(3)節(jié)點關系沖突的疏解。在多個節(jié)點關系中，有時會出現相互沖突。比如出現a＞b，b＞c，c＞a，這時就需要對沖突進行疏解。在發(fā)生沖突的關系間，必須首先劃分各自得優(yōu)先等級，然后依據低等級關系服從于高等級關系的原則，在節(jié)點關系表中將沖突中等級低的關系刪除，最終得到沒有沖突的節(jié)點關系表。沖突種類可劃分為2 類:①對向沖突。即經過推理，2 個節(jié)點間出現對立的相互關系。即經過推理得到a＞b，同時b＞a或b『a，例如由a＞b，b＞c，c＞a可得，或者a＜b，同時b＜a或a』b;②無關性沖突。即經過推理，2個節(jié)點間出現既無關又相關的2 種關系。例如，經過推理得到a＞b或b＞a，同時b＞＜a。

2.2 節(jié)點初始權重賦值

節(jié)點初始權重賦值思路如下:將所有的節(jié)點依據權重等級分層，同等級的節(jié)點權重相同，等級高的層級權重高于等級低的權重。每次迭代尋找重要程度最低的若干節(jié)點，將這些節(jié)點放入當前的最低權重等級，其權重即為當前層次的權重。本次迭代完畢后，將最低權重等級的所有節(jié)點從序列樹中去除，設立新的層次與權重，用同樣方法搜索并賦權，直到所有的節(jié)點賦權完畢。算法步驟如下。

(1)令k=1，權重系數c≥1。所有節(jié)點集合S=(s1，s2，…，sn)，節(jié)點數為n，葉子集合D=(d1，d2，…，dm)。葉子數為m。顯然有D∈S。

(2)標記向量B=［0，0，…，0］m。

(3)S中節(jié)點與葉子di相比較(考察節(jié)點關系表)，如果存在某一節(jié)點sw＞di，且不存在任意節(jié)點sv使得di＞sv，則標記向量bi=1。

(4)i=i+1;如果i＞m，步入(5)，否則回到步驟(3)。

(5)bi=1(i=1，2，…，m)的節(jié)點為標記節(jié)點。標記節(jié)點的權重fi=fi+c·k。從S和D中除去標記節(jié)點，得到新的節(jié)點數n’和葉子數m，更新節(jié)點關系表。如果n’＞0 且n＞n’，則n=n’，m=m’，k=k+1，回到步驟(2)，否則，所有未賦值節(jié)點權重fi=fi+c·k，計算完畢，退出。

這一方法優(yōu)點是通過分層可以清晰、完整地表達任意兩節(jié)點間的絕對優(yōu)先關系，但是這一方法的局限性是不能有效表達相對優(yōu)先關系。相對優(yōu)先關系將在下文的搜索方法中體現。

2.3 節(jié)點搜索排序

在介紹方法之前引入2 個定義。

(1)節(jié)點信息熵。在序列樹中，任一節(jié)點所包含的葉節(jié)點數目為m，搜索過程中的任一時刻，未曾搜索的葉節(jié)點數為n。若該節(jié)點為非葉節(jié)點，即m＞0，則節(jié)點的搜索信息熵ω=(n-1)/m;如果該節(jié)點為葉節(jié)點，即m=0，則節(jié)點的搜索信息熵ω=1。節(jié)點的搜索信息熵簡稱節(jié)點信息熵。

(2)節(jié)點鏈。在序列樹中，從根節(jié)點b經由各中間節(jié)點(n1，n2，…，nm)，至某一葉節(jié)點y組成的鏈表稱為該葉節(jié)點的節(jié)點鏈，即節(jié)點向量Ny=(b，n1，n2，…，nm，y)。

節(jié)點搜索排序的原則:任意父節(jié)點在其所有子節(jié)點選取完畢后方可選取(因為父節(jié)點是子節(jié)點的總和，在采取結束驗證序列方法下，子節(jié)點不搜索完畢，父節(jié)點不能算搜索完畢);選取節(jié)點時，要盡量保證同等重要的節(jié)點具有相同的搜索幾率，并保證能夠幾乎同時完成搜索(在部隊輸送中，可保證若干相同重要程度的部隊齊頭并進，通過并行機制，能夠為最快時間完成輸送創(chuàng)造條件)。依據節(jié)點搜索排序的原則，設計搜索算法分為以下2 步驟。

2.3.1 建立權重分層序列樹

依據權重由高到低將所有節(jié)點分為若干權重層。同一層次的節(jié)點具有相同的權重值，即同層次的任意節(jié)點的重要程度相當。依據權重層次，可建立權重分層序列樹。

2.3.2 搜索權重分層序列樹

本文提出依據節(jié)點搜索信息熵進行權重分層序列樹搜索的算法。由于搜索的原則是力求等同重要的節(jié)點具有同等的搜索幾率，因此同等重要節(jié)點的子節(jié)點(尤其是葉節(jié)點)應具有同等搜索幾率，搜索信息熵正是反映這一信息。通過下一步節(jié)點搜索的概率信息，搜索時選擇搜索信息熵最大的節(jié)點，可以保證各等同重要節(jié)點的盡可能同時完成搜索。搜索權重分層序列樹的思路如下。

(1)依據層次的高低先后搜索。

(2)在每一層搜索時，考察該層所有的葉節(jié)點的節(jié)點鏈，則所有葉節(jié)點的節(jié)點向量組成了一個節(jié)點矩陣。考察矩陣的每一行，比較其中每一節(jié)點的搜索信息熵，選擇最大者。如果信息熵最高的節(jié)點有多個，選擇葉節(jié)點數少的節(jié)點;如果葉節(jié)點數最少的節(jié)點也有若干個，通過平均概率選擇其中某一節(jié)點。如果選中的某一節(jié)點出現在若干節(jié)點向量中，向下考察下一行，同樣方法搜索新的節(jié)點，直到搜索到葉節(jié)點。

(3)在對節(jié)點矩陣的每一行比較時，考慮節(jié)點的相對優(yōu)先關系。為每行的節(jié)點分層(分層方法同上)，首先為節(jié)點賦權重，再依據權重分層(同權重分層序列樹方法)。具有較高相對優(yōu)先關系的節(jié)點的層次高于具有較低相對優(yōu)先關系的節(jié)點。依據分層進行節(jié)點的搜索，先搜索具有高層次的節(jié)點，后搜索低層次的節(jié)點。可以看到，當某節(jié)點的某一子節(jié)點搜索完畢后，其相對較高的優(yōu)先關系取消，節(jié)點放入下一層次。同理易見，任一節(jié)點的相對較低優(yōu)先關系直到其所有子節(jié)點搜索完畢后才取消。同層次的節(jié)點搜索方法同思路(2)，優(yōu)先選擇信息熵最大的節(jié)點。

權重分層序列樹搜索的步驟如下:①設定搜索的層次。令m=1，從最高層開始搜索。②考察m層所有的葉節(jié)點，如果葉節(jié)點為空，m=m+1，回到②。建立由節(jié)點鏈組成的節(jié)點矩陣Nm。設定Nm搜索的行向量Nm(j)，令j=1，即從第1 行(根節(jié)點)開始搜索。③依據相對先后關系為j行向量節(jié)點賦權重。④依據權重為j行向量節(jié)點分子層。同等權重的節(jié)點為同一子層，權重高的節(jié)點層次高于權重低的節(jié)點。搜索j行向量，如果考察對象向量Nm‘(j)沒有賦值，令j行向量中所有的節(jié)點組成考察對象向量Nm‘(j)。⑤研究j行向量中的考察對象向量Nm‘(j)，選擇最高子層作為研究對象。比較該層所有節(jié)點的信息熵，選擇最大的若干節(jié)點，形成j+ 1 層的考察對象向量Nm‘(j+1)。如果Nm‘(j+1)中包含葉節(jié)點，進入⑥，否則，令j=j+1，回到③。⑥通過平均概率選擇Nm‘(j+1)中包含的葉節(jié)點的一個，將該節(jié)點存入搜索結果列表，序列樹中刪除該節(jié)點，更改其節(jié)點鏈中其他節(jié)點信息熵。如果某父節(jié)點不存在其他子節(jié)點，將該父節(jié)點存入搜索結果列表，序列樹中刪除該節(jié)點，同時更改節(jié)點鏈其他節(jié)點的信息熵。此時，如果序列樹中節(jié)點已全部刪除，計算完畢，退出;否則，m=m+1，進入②。

其中，步驟③中依據相對先后關系為j行向量節(jié)點賦權重的方法如下:?令k=1，權重系數c≥1，節(jié)點行向量的節(jié)點集合S=(s1，s2，…，sn)，節(jié)點數為n;?標記向量B=［0，0，…，0］n;?S中節(jié)點di與其他節(jié)點相比較(考察節(jié)點關系表)，如果存在某一節(jié)點sw』di，且不存在任意節(jié)點sv使得di』sv，則標記向量bi=1;?i=i+1，如果i＞n，步入?，否則回到?;?bi=1(i=1，2，…，n)的節(jié)點為標記節(jié)點。標記節(jié)點的權重fi=fi+c·k。從S中除去標記節(jié)點，得到新的節(jié)點數n’，更新節(jié)點關系表。如果n’＞0 且n＞n’，則n=n’，k=k+1，回到?，否則，所有未賦值節(jié)點權重fi=fi+c·k，計算完畢。

3 算 例

如圖1 序列樹中，存在節(jié)點間關系:節(jié)點2 ＞節(jié)點3，節(jié)點32 ＞節(jié)點22，節(jié)點31 ＞節(jié)點33，節(jié)點33 ＞節(jié)點42，節(jié)點31 ＞節(jié)點43，節(jié)點41 ＞節(jié)點21。其中:關系節(jié)點2 ＞節(jié)點3 最為重要，求解決策樹的節(jié)點排序;節(jié)點2、節(jié)點3、節(jié)點4 分別指3個部隊，其下屬節(jié)點分別為這些部隊的下屬單位。節(jié)點排序即表示部隊的輸送序列。

3.1 建立節(jié)點關系表

(1)初始節(jié)點關系表。建立初始節(jié)點關系表，其中，由于s2＞s3，將s2與s3的子節(jié)點間關系明確(見表1)。

圖1 序列樹

表1 初始節(jié)點關系

(2)沖突關系表。分析發(fā)現節(jié)點32 與節(jié)點22關系存在沖突(見表2)。

表2 沖突關系

(3)疏解關系表。對沖突關系疏解后見表3。

表3 疏解關系

3.2 節(jié)點初始權重賦值

迭代次數一:

(2)i=1?？疾烊~節(jié)點d21，存在s41＞d21，同時存在d21＞s3，b21=0。

(3)i= 2?？疾烊~節(jié)點d22，存在d22＞s3，b22=0。

(4)i= 3?？疾烊~節(jié)點d23，存在d23＞s3，b23=0。

(5)i=4。考察葉節(jié)點d31，存在d31＞s33，b31=0。

(6)i=5?？疾烊~節(jié)點d32，存在s2＞d32，不存在d32＞sj(j=1，2，…，n)，b32=1。

(7)i=6。考察葉節(jié)點d33，存在s2＞d33，同時存在d33＞s42，b33=0。

(8)i= 7?？疾烊~節(jié)點d41，存在d41＞s21，b41=0。

(9)i=8?？疾烊~節(jié)點d42，存在s33＞d42，不存在d42＞sj(j=1，2，…，n)，b42=1。

(10)i=9?？疾烊~節(jié)點d43，存在s31＞d43，不存在d43＞sj(j=1，2，…，n)，b43=1。

迭代次數二:完善節(jié)點關系，由于節(jié)點的刪除，調整節(jié)點關系見表4。

表4 節(jié)點關系

(2)i=1?？疾烊~節(jié)點d21，存在s41＞d21，同時存在d21＞s3，b21=0。

(3)i= 2?？疾烊~節(jié)點d22，存在d22＞s3，b22=0。

(4)i= 3。考察葉節(jié)點d23，存在d23＞s3，b23=0。

(5)i= 4。考察葉節(jié)點d31，存在d31＞s33，b31=0。

(6)i=6?？疾烊~節(jié)點d33，存在s2＞d33，不存在d33＞sj(j=1，2，…，n)，b33=1。

(7)i= 7?？疾烊~節(jié)點d41，存在d41＞s21，b41=0。

以此類推，迭代次數三、四、五、六，通過6 次迭代，得到如圖2 所示權重，方框內數字為節(jié)點權重。

圖2 序列樹權重

3.3 優(yōu)先關系搜索

(1)建立權重分層序列樹(如圖3 所示)。方框內數字為節(jié)點的權重與子節(jié)點數量。

圖3 序列樹

(2)搜索迭代。

迭代一:

考察第1 層。通過概率選擇葉節(jié)點22，同時，葉節(jié)點22 所有父節(jié)點的葉節(jié)點數目減一(見表5)。

重復迭代直至九:

考察第5 層。選擇葉節(jié)點43。由于節(jié)點4 沒有子節(jié)點，選擇節(jié)點4。同理，由于節(jié)點1 沒有了子節(jié)點，選擇節(jié)點1(見表6)。

搜索完畢，得到節(jié)點序列(22，41，23，21，2，31，33，42，32，3，43，4，1)。對照問題的條件:節(jié)點2 ＞節(jié)點3，節(jié)點32 ＞節(jié)點22，節(jié)點31 ＞節(jié)點33，節(jié)點33 ＞節(jié)點42，節(jié)點31 ＞節(jié)點43，節(jié)點41 ＞節(jié)點21，則有節(jié)點2 ＞節(jié)點3，可見該序列完全符合要求。

表5 節(jié)點信息熵(迭代一)

表6 節(jié)點信息熵(迭代九)

4 結 語

輸送序列是上級指示和首長意圖的直接體現，是作戰(zhàn)部署的重要內容之一，影響作戰(zhàn)企圖和作戰(zhàn)部署的實現?；谄蚣耐負渑判蚰軌蛎枋龃_定輸送序列的要求，并通過序列樹算法實現輸送序列定量化確定。

［1］ 曲開社，翟巖慧.偏序集、包含度與形式概念分析［J］. 計算機學報，2006，29(2):119-226.

［2］ 葉先一，張?；?偏序集上的一種拓撲排序［J］. 數學研究，2005，38(4):440-443.

［3］ 朱立華.并行拓撲排序算法PTSA 的設計與實現［J］. 計算機工程與應用，2004，35(2):111.

［4］ 王順鳳.一種有向權圖的拓撲排序算法及其應用［J］. 南京氣象學院學報，2002，25(5):711-714.

［5］ 王曉瑛，魏正軍.關于拓撲排序算法的討論［J］.西北大學學報，2002，32(4):344-347.