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

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

0 引言

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

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

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

1 模型建立和分析

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

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

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

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

2）若iσ≠iτ時(shí)，則jτ≠jσ。

3）V1的任意子集滿足：

其中：

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

其中：

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

3）V1的任意子集滿足：

其中：

注2：當(dāng)2

2 基于STP的搜索算法

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

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

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

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

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

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

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

3 算法實(shí)例驗(yàn)證

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

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

有向圖2的鄰接矩陣為：

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

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

表1 圖2的8-簡(jiǎn)單有向路徑

4 結(jié)論

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