基于STP的零部件關(guān)系網(wǎng)簡單路徑搜索方法研究

魏美華，劉小龍，延衛(wèi)軍

（1.榆林學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，榆林 719000；2.榆林學(xué)院 管理學(xué)院，榆林 719000）

0 引言

制造業(yè)零部件的關(guān)系網(wǎng)、物聯(lián)網(wǎng)、運輸流、電網(wǎng)等共同的載體就是網(wǎng)絡(luò)，如交通流、管道輸送等涉及到有向無環(huán)網(wǎng)絡(luò)，任何一個網(wǎng)絡(luò)都可以用圖論來刻畫。在實際問題中，最短路徑不一定是最優(yōu)的路徑[1]，但最優(yōu)路徑應(yīng)該是無障礙的。從而尋找圖的簡單路徑[2]具有一定的實際意義和應(yīng)用前景，例如應(yīng)用于通信系統(tǒng)[3]、生物信息學(xué)[4]等領(lǐng)域中。

面對大批量定制，企業(yè)所制造的零部件種類多和數(shù)量大，零部件間存在著龐雜的隸屬關(guān)系。一個備受關(guān)注的問題就是零部件的總用量和零部件的總使用次數(shù)。為了滿足某零部件的總用量，有必要計算從產(chǎn)品族中的所有產(chǎn)品出發(fā)到該零部件的所有簡單路徑，然后計將該零部件的所有簡單路徑的用量累加，得出該零部件在產(chǎn)品族中的總用量[5]。將產(chǎn)品族零部件視為網(wǎng)絡(luò)中的節(jié)點，零部件間的隸屬關(guān)系視為網(wǎng)絡(luò)中的有向邊，表示上一級部件指向直接隸屬于該零部件的下一級零部件，這樣產(chǎn)品族零部件關(guān)系網(wǎng)絡(luò)就構(gòu)成一個有向無環(huán)圖。

上述問題涉及到尋找有向圖的簡單路徑.而列舉所有的簡單路徑和環(huán)是圖論中的NP難問題[6]。受文獻[7]啟發(fā)，本文基于矩陣半張量積（STP）理論[8,9]，通過定義鄰接矩陣，建立了簡單路徑和環(huán)的模型，采用矩陣方法約化搜索空間，并結(jié)合代數(shù)方法精確尋找有向圖的簡單路徑和環(huán)，得到一個新的搜索算法，并對該算法進行驗證。

1 模型建立和分析

給定有向圖G=（V，E），頂點集V={v1，v2，…，vn}，邊集E={e1，e2，…，em}，它的鄰接矩陣為A=（aij），其中元素aij=1當(dāng)且僅當(dāng)從頂點vi到頂點vj有一條有向邊，否則aij=0。簡單路徑（環(huán)）就是沒有重復(fù)頂點的路徑（環(huán)）。s為簡單路徑（環(huán)）就是具有s個頂點的簡單路徑（環(huán)），例如圖1表示5-簡單有向路徑。

圖1 5-簡單有向路徑的連接關(guān)系

模型1 設(shè)點集V1V，V1=，i1，i2，…，is{1，2，…，n}，5≤s≤n。頂點導(dǎo)出有向子圖G（V1）是s-簡單路徑當(dāng)且僅當(dāng)

1）AV1中一個元素為0，其余元素為1。這里：

2）若iσ≠iτ時，則jτ≠jσ。

3）V1的任意子集滿足：

其中：

注1：當(dāng)s≤2時，s為簡單路徑和環(huán)意義不大。當(dāng)s=3，4時，頂點導(dǎo)出有向子圖G（V1）是s為簡單路徑當(dāng)且僅當(dāng)模型1中的(i)和(ii)成立。

其中：

2）若當(dāng)iσ≠iτ時，則jτ≠jσ。

3）V1的任意子集滿足：

其中：

注2：當(dāng)2

2 基于STP的搜索算法

矩陣半張量積是矩陣普通乘積的一個推廣，其不同于矩陣的普通乘積，不要求前一個矩陣的列數(shù)與后一個矩陣的行數(shù)相等，然而它卻保持著矩陣的普通乘積的基本性質(zhì)。

給定有向圖G=（V，E），其中頂點集V={v1，v2，…，vn}，邊集E={e1，e2，…，em}，它的鄰接矩陣為A=（aij），其中矩陣中的元素aij=1當(dāng)且僅當(dāng)從頂點vi到頂點vj有一條有向邊，否則aij=0。算法的基本原理如下：

根據(jù)上述基本原理，按照下列步驟尋找有向圖的所有的或任意指定長度的s為簡單路徑和環(huán)。

步驟2：利用J=[1,0]提取MV1的第一行，并記為β=JMV1=[b1，b2，…，b2n]。若bi≠s-1，i=1，2，…，2n，則圖G沒有s為簡單路徑，計算終止.否則向量β中元素s-1的列標(biāo)分別記為r1，r2，…，rp。

步驟3：對于每一個rj，j=1，2，…，p，其對應(yīng)于。根據(jù)文獻[4]，令：

步驟4：檢驗上述含有s個頂點的S（rj）是否滿足模型1的條件。符合條件的子圖S（rj）構(gòu)成所有的s為簡單路徑。

注3 結(jié)合模型2類似可尋找簡單環(huán)的算法。

3 算法實例驗證

設(shè)有向圖G=（V，E）如圖2所示，并借助MATLAB軟件進行搜索尋找任意給定長度的簡單路徑和環(huán)，以尋找8-簡單路徑為例，以此驗證算法的有效性。

圖2 有向圖的連接關(guān)系

有向圖2的鄰接矩陣為：

根據(jù)算法步驟1易得MV1，并利用J=[1,1]提取第一行，則該行元素是7的列標(biāo)為r1，r2，…，r345，這是所有可能形成簡單路徑的元素。

根據(jù)算法的步驟3可知，元素個數(shù)是8的S（rj）僅有25個，根據(jù)步驟4對于復(fù)雜的有向圖2只有一條8-簡單路徑，如表1所示。

表1 圖2的8-簡單有向路徑

4 結(jié)論

制造業(yè)中產(chǎn)品族零部件關(guān)系網(wǎng)絡(luò)中，企業(yè)所關(guān)注的零建立部件的總用量和零部件的總使用次數(shù)，這涉及到有向圖的簡單路徑搜索問題。本文建立了簡單路徑和環(huán)的模型，通過鄰接矩陣，運用矩陣半張量積理論，得到了尋找有向圖所有的或任意給定長度的簡單路徑和環(huán)的新算法，運用該算法減少了搜索空間的范圍，并能精確尋找有向圖的指定長度或所有的簡單路徑和環(huán)。該算法對于企業(yè)零部件關(guān)系網(wǎng)的簡單路徑搜索問題有一定的參考價值。