一種基于二進(jìn)制編碼的最小生成樹(shù)算法

王防修

(武漢工業(yè)學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北武漢430023)

許多應(yīng)用問(wèn)題都是一個(gè)求帶權(quán)無(wú)向連通圖［1］的最小生成樹(shù)［2］問(wèn)題。例如：要在n個(gè)城市之間鋪設(shè)光纜，主要目標(biāo)是使這n個(gè)城市的任意兩個(gè)之間都可以通信，但鋪設(shè)光纜的費(fèi)用很高，且各個(gè)城市之間鋪設(shè)光纜的費(fèi)用不同;另一個(gè)目標(biāo)是使鋪設(shè)光纜的總費(fèi)用最低。這就需要找到帶權(quán)的最小生成樹(shù)。

在求帶權(quán)無(wú)向連通圖的最小生成樹(shù)時(shí)，最經(jīng)典的算法就是Prim算法和Kruskal算法［3］。這兩個(gè)算法都是通過(guò)求解局部最優(yōu)達(dá)到求解全局最優(yōu)，即我們通常所說(shuō)的貪心算法。一般來(lái)講，局部最優(yōu)解往往不是整體最優(yōu)解，而是近似最優(yōu)解。由于最小生成樹(shù)的特殊性，用貪心算法［4］能夠準(zhǔn)確地計(jì)算出它的全局最優(yōu)解。然而，無(wú)論P(yáng)rim算法還是Kruskal算法，都只能找到帶權(quán)無(wú)向連通圖的一個(gè)最小生成樹(shù)。如果一個(gè)帶權(quán)無(wú)向連通圖有多個(gè)最小生成樹(shù)，要想找出所有的最小生成樹(shù)，用 Prim算法或Kruskal算法都是無(wú)能為力的。至于所謂用遺傳算法求最小生成樹(shù)，由于該算法是一種近似算法，可能連一個(gè)最小生成樹(shù)都找不到，最好的情形也是只能找到一個(gè)最小生成樹(shù)。因此，能否找到一種在全局范圍內(nèi)尋找所有最小生成樹(shù)的算法?到目前為止，還沒(méi)有相關(guān)文獻(xiàn)作這方面的工作。本文試圖用二進(jìn)制編碼的方式來(lái)解決這個(gè)問(wèn)題。

1 理論基礎(chǔ)

定義1用深度優(yōu)先法或廣度優(yōu)先法遍歷一個(gè)無(wú)向圖，如果所有頂點(diǎn)都能被訪問(wèn)到，則稱該圖是連通圖;否則，稱該圖是不連通圖。

定義2設(shè)一個(gè)帶權(quán)無(wú)向連通圖［5］有n個(gè)頂點(diǎn)和m條邊，如果刪除m-n+1條邊后，該剩余圖仍然是連通的，則稱該剩余圖為生成樹(shù)。

定義3在一個(gè)帶權(quán)無(wú)向連通圖的所有生成樹(shù)中，所有邊的權(quán)值之和最小的生成樹(shù)是最小生成樹(shù)。

性質(zhì)1如果一個(gè)帶權(quán)無(wú)向連通圖有n個(gè)頂點(diǎn)，那么它的生成樹(shù)只有n-1條邊。

證明：如果它有n條邊，那么它一定有回路，因此它就不是生成樹(shù)。另一方面，如果它只有n-2條邊，那么這n-2條邊最多只能連接n-1個(gè)頂點(diǎn)，還有一個(gè)頂點(diǎn)沒(méi)有被連接。

定義4對(duì)于一個(gè)無(wú)向圖，如果用字符‘1’表示圖中的兩個(gè)頂點(diǎn)之間存在邊，用字符‘0’表示兩個(gè)頂點(diǎn)間不存在邊，則我們稱這種用二進(jìn)制字符串表示的圖為對(duì)圖的二進(jìn)制編碼。

定義5設(shè)一個(gè)無(wú)向連通圖有m條邊，如果我們用長(zhǎng)度為m的二進(jìn)制字符串表示它的生成樹(shù)，則稱該二進(jìn)制字符串是對(duì)應(yīng)該生成樹(shù)的染色體，其中染色體的每一位對(duì)應(yīng)無(wú)向圖的一條邊。

性質(zhì)2設(shè)G是一個(gè)含有n個(gè)頂點(diǎn)m條邊的無(wú)向連通圖，如果用染色體表示該無(wú)向圖的生成樹(shù)，則染色體是長(zhǎng)度為m的含有n-m+1個(gè)‘1’字符和2m-n-1個(gè)‘0’字符的字符串。

定義6如果一個(gè)染色體對(duì)應(yīng)帶權(quán)無(wú)向連通圖的最小生成樹(shù)，則稱該染色體是最優(yōu)染色體。

性質(zhì)3如果找打一個(gè)帶權(quán)無(wú)向連通圖的最優(yōu)染色體，則它所對(duì)應(yīng)的最小生成樹(shù)確定。

2 算法設(shè)計(jì)

2.1 帶權(quán)無(wú)向連通圖的矩陣表示法

設(shè)G是一個(gè)含有n個(gè)頂點(diǎn)m條邊的帶權(quán)無(wú)向連通圖，則可以用一個(gè)n×n階矩陣表示：

其中

2.2 連通的判斷

算法的中心思想就是從帶權(quán)無(wú)向連通圖的生成樹(shù)中找出最小生成樹(shù)。雖然生成樹(shù)是從圖的m條邊中去掉m-n+1條邊形成的，但僅僅刪除m-n+1邊還是不夠的，還必須保證刪除的剩余圖還是連通的，否則就不是生成樹(shù)。

可以通過(guò)使用深度優(yōu)先法或廣度優(yōu)先法對(duì)剩余圖進(jìn)行遍歷，如果圖的所有結(jié)點(diǎn)經(jīng)過(guò)一次遍歷都可以搜索到，則該剩余圖就是生成樹(shù)。否則，剩余圖一定不是生成樹(shù)。

因此，通過(guò)深度優(yōu)先法或廣度優(yōu)先法對(duì)剩余圖進(jìn)行遍歷，可以將帶權(quán)無(wú)向連通圖的所有生成樹(shù)找出來(lái)。然后，從生成樹(shù)集中找出最小生成樹(shù)就比較自然了。

2.3 對(duì)生成樹(shù)進(jìn)行二進(jìn)制編碼

由于帶權(quán)無(wú)向連通圖有m條邊，因此需要用長(zhǎng)度為m的二進(jìn)制字符串即染色體表示該圖。當(dāng)染色體的每一位都是字符‘1’時(shí)，該染色體就是表示該帶權(quán)無(wú)向連通圖。一方面，帶權(quán)無(wú)向連通圖的生成樹(shù)只有n-1條邊，故它所對(duì)應(yīng)的染色體只有n-1個(gè)字符‘1’和m-n+1個(gè)字符‘0’;另一方面，由n-1個(gè)字符‘1’和m-n+1個(gè)字符‘0’組成的染色體不一定對(duì)應(yīng)一棵生成樹(shù)，故需要判斷該染色體所對(duì)應(yīng)的剩余圖是否連通。

因此，判斷一根染色體是否對(duì)應(yīng)一棵生成樹(shù)，執(zhí)行步驟：(1)從“00…011…1”(該染色體由左邊的m-n+1個(gè)‘0’字符和右邊的n-1個(gè)‘1’字符組成)到“11…100…0”(該染色體由左邊的n-1個(gè)‘1’字符和右邊的m-n+1個(gè)‘0’字符組成)的染色體中篩選出只含有n-1個(gè)字符‘1’的染色體;(2)從(1)篩選出的染色體中進(jìn)一步篩選出生成樹(shù)連通的染色體。

3 算法描述

設(shè)G是一個(gè)含有n個(gè)頂點(diǎn)m條邊的帶權(quán)無(wú)向連通圖，則生成圖G的算法過(guò)程如下。

Step1：初始化i=2n-1-1，最優(yōu)值shortpath=-1，長(zhǎng)度為m的二進(jìn)制字符串 str=“00…0”(m個(gè)‘0’字符組成)，以及建立染色體每一位與帶權(quán)無(wú)向連通圖的某一邊的對(duì)應(yīng)關(guān)系。

Step2：將i轉(zhuǎn)化為長(zhǎng)度為m的二進(jìn)制字符串，具體轉(zhuǎn)換過(guò)程如下。

(1)執(zhí)行語(yǔ)句 itoa(i，str1，2)，可以將整數(shù) i轉(zhuǎn)換為二進(jìn)制字符串。

(2)求出二進(jìn)制字符串str1的長(zhǎng)度，只需執(zhí)行l(wèi)=strlen(str1)。

(3)執(zhí)行 strcpy(str+m-l，str1)，就可以得到 i所對(duì)應(yīng)的染色體str。

Step3：統(tǒng)計(jì)染色體str中所含字符‘1’的個(gè)數(shù)c。如果c≠n-1，則轉(zhuǎn)向step6。

Step4：判斷染色體str所對(duì)應(yīng)的圖是否連通。如果不連通，則轉(zhuǎn)向step6。

Step5：求 str所對(duì)應(yīng)的生成樹(shù)的邊權(quán)之和curpath。如果 curpath＜shortpath，則執(zhí)行 shortpath=curpath，同時(shí)保存該染色體;否則，只保存該染色體。

Step6：執(zhí)行 i=i+1。

Step7：如果 i≤2m-2m-n+1+1 ，則返回 Step2。

Step8：從保存的生成樹(shù)染色體中將邊權(quán)之和等于shortpath的染色體(最優(yōu)染色體)選擇出來(lái)。

Step9：輸出所有最優(yōu)染色體所對(duì)應(yīng)的最優(yōu)生成樹(shù)。

4 算法測(cè)試及比較

4.1 算法實(shí)例

例已知如圖1所示的帶權(quán)無(wú)向連通圖G，求G的最小生成樹(shù)。

圖1 帶權(quán)無(wú)向連通圖G

解：由于帶權(quán)無(wú)向連通圖G的定點(diǎn)數(shù)n=5和邊數(shù)m=8，因此程序執(zhí)行算法的過(guò)程如下。

Step1：i = 15，shortpath = -1，str=“00000000”，染色體的8個(gè)二進(jìn)制位從左到右依次與邊 (v1，v2) 、(v1，v3) 、(v1，v4) 、(v2，v3) 、(v2，v5) 、(v3，v4) 、(v3，v5) 、(v4，v5) 相對(duì)應(yīng)。

Step2：執(zhí)行語(yǔ)句：itoa(i，str1，2);l=strlen(str1);strcpy(str+m-l，str1);得到i所對(duì)應(yīng)的染色體str。

Step3：如果str所含字符‘1’的個(gè)數(shù)不等于4，則轉(zhuǎn)向step6。

Step4：如果染色體str所對(duì)應(yīng)的圖不連通，則轉(zhuǎn)向step6。

Step5：求str所對(duì)應(yīng)的生成樹(shù)的4條邊的權(quán)值之和curpath。如果curpath＜shortpath，則用curpath替換shortpath，同時(shí)保存染色體str;否則只保存染色體。

Step6：執(zhí)行 i=i+1。

Step7：如果 i≤241 ，則返回 Step2。

Step8：從保存的生成樹(shù)染色體中將4條邊權(quán)值之和等于 shortpath=14的染色體“01101001”和“11100001”選擇出來(lái)。

Step9：染色體“01101001”和“11100001”所對(duì)應(yīng)的最優(yōu)生成樹(shù)分別如圖2，圖3所示。

圖2 01101001所對(duì)應(yīng)的最小生成樹(shù)

圖3 11100001所對(duì)應(yīng)的最小生成樹(shù)

4.2 算法比較

如果分別用Prim算法和Kruskal算法求解圖1的最小生成樹(shù)，都只能得到如圖2所示的一棵最小生成樹(shù)。因此，當(dāng)一個(gè)帶權(quán)無(wú)向連通圖的最小生成樹(shù)不止一個(gè)時(shí)，Prim算法和Kruskal算法都無(wú)法求出所有的最小生成樹(shù)，它們永遠(yuǎn)只能求出其中的一個(gè)最優(yōu)解。

本算法先利用染色體表示各種不同的生成樹(shù)，然后從所有這些生成樹(shù)中找出所有最小生成樹(shù)。因此，本算法通過(guò)巧妙地利用二進(jìn)制編碼來(lái)達(dá)到全局尋優(yōu)的目的。

Prim算法和Kruskal算法本質(zhì)上都是通過(guò)局部最優(yōu)達(dá)到全局最優(yōu)，因此尋優(yōu)的速度快。本算法由于是全局尋優(yōu)，故尋優(yōu)的速度比較慢，但它可以找到所有的最優(yōu)解。

5 結(jié)束語(yǔ)

針對(duì)Prim算法和Kruskal算法都不能尋找一個(gè)帶權(quán)無(wú)向圖所有最小生成樹(shù)的缺點(diǎn)，本文提出了一種從全局范圍內(nèi)尋找一個(gè)帶權(quán)無(wú)向圖所有最小生成樹(shù)的二進(jìn)制編碼算法。該算法充分利用深度優(yōu)先遍歷算法和最小生成樹(shù)的性質(zhì)，將不滿足生成樹(shù)的染色體淘汰，從而極大地提高了全局范圍內(nèi)的尋優(yōu)速度。實(shí)驗(yàn)表明該算法能夠?qū)崿F(xiàn)全局尋優(yōu)和找出全部最小生成樹(shù)，并使尋優(yōu)效率在整體上得到改善。

［1］ Fred Bucldey，MaryLewinter.圖 論 簡(jiǎn) 明 教 程［M］.北京：清華大學(xué)出版社，2005.

［2］ CormenTH，Lleiserxon CE，RivestRL.Introducton to Algorithms［M］.USA：MIT Press，2001.

［3］ 高一凡.《數(shù)據(jù)結(jié)構(gòu)》算法實(shí)現(xiàn)及解析［M］.西安：西安電子科技大學(xué)出版社，2002.

［4］ 候識(shí)忠.數(shù)據(jù)結(jié)構(gòu)算法程序集［M］.北京：中國(guó)水利水電出版社，2005.

［5］ 劉瓚武.應(yīng)用圖論［M］.長(zhǎng)沙：國(guó)防科技大學(xué)出版社，2006.