改進(jìn)的Prim算法在求解旅行商問(wèn)題中的應(yīng)用

?

改進(jìn)的Prim算法在求解旅行商問(wèn)題中的應(yīng)用

劉 朝 霞

(集寧師范學(xué)院 數(shù)學(xué)系，內(nèi)蒙古 烏蘭察布市 012000 )

摘要：旅行商問(wèn)題是圖論中一個(gè)典型的組合優(yōu)化問(wèn)題，它的問(wèn)題描述與圖論中最小生成樹問(wèn)題的描述具有很多相似之處,在一些情形下，可以用最小生成樹形成的路徑來(lái)獲得旅行商問(wèn)題的最短巡回路徑。首先給出了最小生成樹Prim算法，然后對(duì)其算法進(jìn)行了改進(jìn)，通過(guò)改進(jìn)的Prim算法成功求解了旅行商問(wèn)題。

關(guān)鍵詞：最小生成樹；旅行商問(wèn)題；Prim算法

1引言

旅行商問(wèn)題(TravelingSalesmanProblem)簡(jiǎn)稱TSP問(wèn)題，也被稱為“貨郎擔(dān)貨問(wèn)題”，是經(jīng)典的組合優(yōu)化問(wèn)題[1]。問(wèn)題描述為：給定n個(gè)城鎮(zhèn)組成的交通圖，其中任意兩個(gè)城鎮(zhèn)i、j之間的距離已知，一個(gè)售貨員從住地出發(fā)到每個(gè)城鎮(zhèn)僅一次巡回推銷商品，最后又回到住地，問(wèn)這個(gè)售貨員怎樣選擇路線使總行程(或費(fèi)用)最小。

旅行商問(wèn)題在實(shí)際生活中具有廣泛的應(yīng)用，如郵遞員如何選取一條最短路線到各個(gè)信箱取信、物流公司如何沿最短路線將各個(gè)客戶的訂貨全部送達(dá)等問(wèn)題，本質(zhì)上都屬于TSP問(wèn)題，都可以用求解TSP問(wèn)題的算法來(lái)求解。因此，研究求解旅行商問(wèn)題的算法具有非常重要的理論意義和應(yīng)用價(jià)值。求解旅行商問(wèn)題的算法有搜索算法、遺傳算法、免疫算法以及螞蟻群算法等多種算法，其中神經(jīng)網(wǎng)絡(luò)算法和遺傳算法是目前最流行的算法[2]。本文是在構(gòu)造最小生成樹Prim算法的基礎(chǔ)上，通過(guò)對(duì)其算法的改進(jìn)來(lái)求解旅行商問(wèn)題。

2TSP問(wèn)題與最小生成樹問(wèn)題分析

對(duì)于n個(gè)城市的TSP問(wèn)題，每?jī)蓚€(gè)城市之間都有連通的路徑，其連通路徑數(shù)目為n*(n-1)/2，這與具有n個(gè)頂點(diǎn)的無(wú)向完全圖所含的邊數(shù)相同。因此，TSP問(wèn)題的已知條件可以用含有n個(gè)頂點(diǎn)的無(wú)向帶權(quán)完全圖來(lái)描述，用完全圖的頂點(diǎn)表示TSP問(wèn)題中的城鎮(zhèn)，邊權(quán)值表示每?jī)蓚€(gè)城鎮(zhèn)之間的距離。所以，TSP問(wèn)題就是在一個(gè)由n個(gè)頂點(diǎn)組成的無(wú)向帶權(quán)完全圖G=(V,E)中的n*(n-1)/2條巡回路徑中找出一條權(quán)值之和最小的回路，這是求解旅行商問(wèn)題的關(guān)鍵與根本。

對(duì)于n個(gè)頂點(diǎn)的無(wú)向連通帶權(quán)圖G=(V,E)，在產(chǎn)生的包含n-1條邊且各個(gè)頂點(diǎn)相互連通的眾多生成樹中，找出一棵各邊權(quán)值之和最小的樹的過(guò)程，即為構(gòu)造最小生成樹的過(guò)程[3]。由此，完全可以用含n個(gè)頂點(diǎn)的無(wú)向帶權(quán)完全圖G=(V,E)來(lái)描繪最小生成樹問(wèn)題。因此，可以用最小生成樹來(lái)分析旅行商問(wèn)題。

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

3.1最小生成樹Prim算法基本思想

Prim算法是構(gòu)造最小生成樹的一種常用方法，其基本思想是：設(shè)無(wú)向連通帶權(quán)圖G=(V,{E})，其中V={1,2，…,n}，T=(U,TE)是圖G中的最小生成樹，其中TE是邊的集合，當(dāng)U=V,TE ?E時(shí)，算法結(jié)束。算法從U={ u0}，u0∈V,TE={ }開(kāi)始，重復(fù)執(zhí)行如下貪心選擇：

從i∈U, j∈V-U的所有邊(i,j)中選取一條權(quán)值最小的邊(i0,j0)將其加入集合TE，同時(shí)將j0加入U(xiǎn)，直至U=V為止，此時(shí)，TE選取到的n-1條邊就構(gòu)成了G的一棵最小生成樹T=(V,TE)[4]。

3.2改進(jìn)的最小生成樹Prim算法

雖然可以用最小生成樹的路徑構(gòu)造旅行商問(wèn)題的最優(yōu)解，但旅行商問(wèn)題的最終解是一條回路,而最小生成樹是形成一棵無(wú)回路的樹，所以改進(jìn)了最小生成樹Prim算法。改進(jìn)的算法描述如下：

步驟1：由最小生成樹Prim算法求出最小生成樹T。

步驟2：按非降序排列T中的邊權(quán)值，如果某邊關(guān)聯(lián)頂點(diǎn)的度大于2，則按邊權(quán)值的順序依次將該邊刪掉。

步驟3：如果存在兩個(gè)以上的孤立點(diǎn)，選擇其中一個(gè)孤立點(diǎn)與其距離最短的另一個(gè)孤立點(diǎn)相連接，如此重復(fù)，直至僅有一個(gè)孤立點(diǎn)，則與距離最近的度為1的頂點(diǎn)進(jìn)行連接。

步驟4：如果不存在孤立點(diǎn)，而度為1的頂點(diǎn)超過(guò)2個(gè)時(shí)，需要將處于不同連通分支的1度點(diǎn)中邊權(quán)值最小的1度點(diǎn)進(jìn)行連接，如此重復(fù)，直至度為1的點(diǎn)只有2個(gè)時(shí)，則僅需將這兩個(gè)頂點(diǎn)進(jìn)行連接。

步驟5：每連一次邊，重復(fù)步驟3、4，直至形成一個(gè)每個(gè)頂點(diǎn)的度都為2的環(huán)，即為旅行商環(huán)游的最小回路。

4算法在TSP中的應(yīng)用

例1:如圖1的無(wú)向連通帶權(quán)圖，其中頂點(diǎn)表示城市，邊上的權(quán)值表示兩個(gè)城市之間的距離。

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

應(yīng)用改進(jìn)的Prim算法求解該TSP問(wèn)題的步驟如下：

步驟1：使用Prim算法構(gòu)造最小生成樹的算法：

(1)初始化。令集合U={a}，a∈V，V-U={b,c,d,e}，TE={}，此時(shí)，

lowcost[b]=12,lowcost[c]=10,lowcost[d]=13,lowcost[e]=12。

(3) U={a,c},V-U={b,d,e},TE={(a,c)}。

(4)lowcost[b]=lowcost[c][b]=8，lowcost[e]=lowcost[c][e]=5，lowcost[d]=

lowcost[c][d]=11。

(6) U={a,c,e},V-U={b,d},TE={(a,c),(c,e)}。

(8) U={a,c,e,b},V-U=j5i0abt0b,TE={(a,c),(c,e),(e,b)}。

(9) U={a,c,e,d},V-U={}, TE={(a,c),(c,e),(e,b),(b,d)}，算法結(jié)束。最終求得的最小生成樹如圖2所示。

圖2：最小生成樹

圖3：旅行商環(huán)路

步驟2：非降序排列樹T的邊權(quán)值為5(e，c)、6(b，d)、7(a，d)、8(b，c)，檢查這些頂點(diǎn)，沒(méi)有度大于2的頂點(diǎn)。

步驟3：只存在兩個(gè)度為1的點(diǎn)，只須將其連接即可。

算法結(jié)束時(shí)，如圖3所示，五個(gè)城市的旅行商最優(yōu)環(huán)路為a,c,e,b,d,a，該路線的長(zhǎng)度為37。

例2：下面的矩陣給出了10個(gè)城市之間的距離，其中每個(gè)元素的值代表兩兩城市之間的距離。

應(yīng)用改進(jìn)的Prim算法求解該TSP問(wèn)題的步驟如下：

步驟1：使用Prim算法得到的最小生成樹如圖4。

圖4：最小生成樹

圖5：刪除度大于2的頂點(diǎn)相關(guān)聯(lián)邊的圖

步驟2：非降序排列樹T的邊權(quán)值，檢查權(quán)值最大的邊51(3,10)的關(guān)聯(lián)頂點(diǎn)的度，其中頂點(diǎn)10的度為3，所以將邊(3,10)刪掉，同理刪除邊(4,7)。如圖5所示。

步驟3：從圖5看，度為0的點(diǎn)只有3，度為1的點(diǎn)有1、2、7、5，從中選擇權(quán)值最小的邊(3,7)，將頂點(diǎn)3與頂點(diǎn)7連接起來(lái)，如圖6所示。

圖6：孤立點(diǎn)連接后的圖

圖7：旅行商最優(yōu)環(huán)路

步驟4：從圖6看，度為2的點(diǎn)有1、2、3、5，要把圖分成兩個(gè)連通分量，分別從不同的連通分量中選擇邊(1,5)、(2,3)連接起來(lái)，形成一條回路，如圖6所示。算法結(jié)束，該售貨員的最短環(huán)游路徑為1-8-9-4-10-6-2-3-7-5-1，長(zhǎng)度為323。

5結(jié)語(yǔ)

旅行商問(wèn)題除了應(yīng)用于實(shí)際生活中，還被廣泛應(yīng)用于網(wǎng)絡(luò)、機(jī)器控制以及VLSI等領(lǐng)域，所以求解旅行商問(wèn)題的算法也一直被長(zhǎng)期研究和探討。本文通過(guò)對(duì)構(gòu)造最小生成樹Prim算法的改進(jìn)，成功求出了旅行商問(wèn)題的最優(yōu)解，并予以實(shí)例進(jìn)行了驗(yàn)證。

〔參考文獻(xiàn)〕

[1]王秋芬.呂聰穎.周春光.算法設(shè)計(jì)與分析[M].北京：清華大學(xué)出版社，2011.

[2]卜月華.圖論及其應(yīng)用[M].南京：東南大學(xué)出版社，2012.

[3]盧開(kāi)澄.盧華明.圖論及其應(yīng)用[M].北京：清華大學(xué)出版社，2011.

[4]江波.張黎.基于Prim算法的最小生成樹優(yōu)化研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，(30)31:3 244-3 246.

Application of Improved Prim Algorithm to Traveling Salesman Problem

LIU Zhao-xia

(Department of Mathematics,Jining Normal University,Wulanchabu 012000)

Abstract:Traveling salesman problem is a typical combinatorial optimization problem in graph theory, which has many similarities to the minimum cost spanning tree problem description of the problem .In some cases, the shortest tour path can be path formed by the minimum spanning tree to obtain the traveling salesman problem. This paper gives Prim algorithm, and the algorithm is improved, the improved Prim algorithm successfully solves the traveling salesman problem.

Key words:minimum cost spanning tree;traveling salesman problem; Prim algorithm

中圖分類號(hào)：O157

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-1869(2015)01-0008-03

作者簡(jiǎn)介：劉朝霞(1980-)，女，內(nèi)蒙古烏蘭察布察右中旗人，碩士，講師，研究方向：數(shù)學(xué)與計(jì)算數(shù)學(xué)。

收稿日期：2014-10-08