吳曉東，楊 斌，朱桐生

(1.軍事交通學(xué)院 聯(lián)合投送系，天津300161;2.軍事交通學(xué)院 研究生管理大隊(duì)，天津300161;

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

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

1 模型描述

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

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

具有偏序關(guān)系R的集合L稱為偏序集［1］，記為(L，R)。如果對每個(gè)x，y∈L，必有xRy或yRx，則稱R是集合上的全序關(guān)系。由某個(gè)集合上的一個(gè)偏序加強(qiáng)為該集合上的一個(gè)全序，這個(gè)操作稱為拓?fù)渑判颉？梢杂脽o圈圖表示一個(gè)偏序集，每個(gè)節(jié)點(diǎn)表示一個(gè)元素。如將無圈圖G中的所有頂點(diǎn)排成一個(gè)線性序列，使得圖G中任意一對頂點(diǎn)u和v，若(u，y)∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡虻男蛄?，簡稱拓?fù)湫蛄校?］。對于部隊(duì)輸送而言，簡單的偏序關(guān)系還不能完全描述序列要求，本文再進(jìn)行如下定義。

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

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

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

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

(6)序列樹:?非父子的2 個(gè)節(jié)點(diǎn)間存在節(jié)點(diǎn)相關(guān)性或者節(jié)點(diǎn)無關(guān)性關(guān)系的樹稱為序列樹。序列樹有如下性質(zhì)。

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

②序列樹中的3 點(diǎn)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)是序列樹的中的點(diǎn)組成的2 個(gè)集合，如果有D＜S，則有D中的任一di﹤S中的任一sj。如果有D＞S，則有D中的任一di＞S中的任一sj。如果有D＞＜S，則有D中的任一di＞＜S中的任一sj。

根據(jù)以上定義，整個(gè)部隊(duì)輸送序列問題可以用序列樹來表示，每支部隊(duì)可以用節(jié)點(diǎn)來表示，部隊(duì)的隸屬關(guān)系可以用節(jié)點(diǎn)的父子關(guān)系表示，部隊(duì)輸送序列可以用節(jié)點(diǎn)間的相關(guān)關(guān)系表示。

2 決策樹算法

對于拓?fù)渑判蛞呀?jīng)有的方法［3-5］，拓?fù)渑判虻乃惴ㄋ枷胪ǔＣ枞缦隆?/p>

(1)在AOV 網(wǎng)中選一個(gè)沒有前趨的頂點(diǎn)且輸出。

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

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

當(dāng)過程結(jié)束時(shí)，如果網(wǎng)中的所有頂點(diǎn)均已輸出，則說明網(wǎng)中不存在回路，否則說明網(wǎng)中存在回路，相應(yīng)的排序是不可行的。

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

2.1 建立節(jié)點(diǎn)關(guān)系表

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

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

(2)為節(jié)點(diǎn)關(guān)系劃分優(yōu)先等級。根據(jù)節(jié)點(diǎn)關(guān)系的重要程度，可為節(jié)點(diǎn)關(guān)系明確優(yōu)先等級?？蓪⑺械墓?jié)點(diǎn)關(guān)系劃分為若干等級，等級低的關(guān)系服從于等級高的關(guān)系，其目的是為了節(jié)點(diǎn)關(guān)系出現(xiàn)沖突時(shí)進(jìn)行疏解，要有明確的劃分方法。

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

2.2 節(jié)點(diǎn)初始權(quán)重賦值

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

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

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

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

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

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

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

2.3 節(jié)點(diǎn)搜索排序

在介紹方法之前引入2 個(gè)定義。

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

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

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

2.3.1 建立權(quán)重分層序列樹

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

2.3.2 搜索權(quán)重分層序列樹

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

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

(2)在每一層搜索時(shí)，考察該層所有的葉節(jié)點(diǎn)的節(jié)點(diǎn)鏈，則所有葉節(jié)點(diǎn)的節(jié)點(diǎn)向量組成了一個(gè)節(jié)點(diǎn)矩陣?？疾炀仃嚨拿恳恍校容^其中每一節(jié)點(diǎn)的搜索信息熵，選擇最大者。如果信息熵最高的節(jié)點(diǎn)有多個(gè)，選擇葉節(jié)點(diǎn)數(shù)少的節(jié)點(diǎn);如果葉節(jié)點(diǎn)數(shù)最少的節(jié)點(diǎn)也有若干個(gè)，通過平均概率選擇其中某一節(jié)點(diǎn)。如果選中的某一節(jié)點(diǎn)出現(xiàn)在若干節(jié)點(diǎn)向量中，向下考察下一行，同樣方法搜索新的節(jié)點(diǎn)，直到搜索到葉節(jié)點(diǎn)。

(3)在對節(jié)點(diǎn)矩陣的每一行比較時(shí)，考慮節(jié)點(diǎn)的相對優(yōu)先關(guān)系。為每行的節(jié)點(diǎn)分層(分層方法同上)，首先為節(jié)點(diǎn)賦權(quán)重，再依據(jù)權(quán)重分層(同權(quán)重分層序列樹方法)。具有較高相對優(yōu)先關(guān)系的節(jié)點(diǎn)的層次高于具有較低相對優(yōu)先關(guān)系的節(jié)點(diǎn)。依據(jù)分層進(jìn)行節(jié)點(diǎn)的搜索，先搜索具有高層次的節(jié)點(diǎn)，后搜索低層次的節(jié)點(diǎn)?？梢钥吹剑?dāng)某節(jié)點(diǎn)的某一子節(jié)點(diǎn)搜索完畢后，其相對較高的優(yōu)先關(guān)系取消，節(jié)點(diǎn)放入下一層次。同理易見，任一節(jié)點(diǎn)的相對較低優(yōu)先關(guān)系直到其所有子節(jié)點(diǎn)搜索完畢后才取消。同層次的節(jié)點(diǎn)搜索方法同思路(2)，優(yōu)先選擇信息熵最大的節(jié)點(diǎn)。

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

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

3 算 例

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

3.1 建立節(jié)點(diǎn)關(guān)系表

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

圖1 序列樹

表1 初始節(jié)點(diǎn)關(guān)系

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

表2 沖突關(guān)系

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

表3 疏解關(guān)系

3.2 節(jié)點(diǎn)初始權(quán)重賦值

迭代次數(shù)一:

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

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

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

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

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

(7)i=6?？疾烊~節(jié)點(diǎn)d33，存在s2＞d33，同時(shí)存在d33＞s42，b33=0。

(8)i= 7。考察葉節(jié)點(diǎn)d41，存在d41＞s21，b41=0。

(9)i=8。考察葉節(jié)點(diǎn)d42，存在s33＞d42，不存在d42＞sj(j=1，2，…，n)，b42=1。

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

迭代次數(shù)二:完善節(jié)點(diǎn)關(guān)系，由于節(jié)點(diǎn)的刪除，調(diào)整節(jié)點(diǎn)關(guān)系見表4。

表4 節(jié)點(diǎn)關(guān)系

(2)i=1。考察葉節(jié)點(diǎn)d21，存在s41＞d21，同時(shí)存在d21＞s3，b21=0。

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

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

(5)i= 4?？疾烊~節(jié)點(diǎn)d31，存在d31＞s33，b31=0。

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

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

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

圖2 序列樹權(quán)重

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

(1)建立權(quán)重分層序列樹(如圖3 所示)。方框內(nèi)數(shù)字為節(jié)點(diǎn)的權(quán)重與子節(jié)點(diǎn)數(shù)量。

圖3 序列樹

(2)搜索迭代。

迭代一:

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

重復(fù)迭代直至九:

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

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

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

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

4 結(jié) 語

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

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

［2］ 葉先一，張?；?偏序集上的一種拓?fù)渑判颍跩］. 數(shù)學(xué)研究，2005，38(4):440-443.

［3］ 朱立華.并行拓?fù)渑判蛩惴≒TSA 的設(shè)計(jì)與實(shí)現(xiàn)［J］. 計(jì)算機(jī)工程與應(yīng)用，2004，35(2):111.

［4］ 王順鳳.一種有向權(quán)圖的拓?fù)渑判蛩惴捌鋺?yīng)用［J］. 南京氣象學(xué)院學(xué)報(bào)，2002，25(5):711-714.

［5］ 王曉瑛，魏正軍.關(guān)于拓?fù)渑判蛩惴ǖ挠懻摚跩］.西北大學(xué)學(xué)報(bào)，2002，32(4):344-347.