俞健明

摘要：本文介紹了一種新穎的關(guān)于TSP問(wèn)題的算法，它通過(guò)計(jì)算每條邊屬于最短哈密頓回路的概率來(lái)找到最佳路徑，是目前關(guān)于TSP問(wèn)題的最新解決方案

關(guān)鍵詞：NP 問(wèn)題；旅行商問(wèn)題 ；數(shù)理統(tǒng)計(jì)；大黃蜂

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）30-0258-02

TSP問(wèn)題（Travelling Salesman Problem）又譯為旅行推銷員問(wèn)題、貨郎擔(dān)問(wèn)題，是數(shù)學(xué)領(lǐng)域中著名問(wèn)題之一。假設(shè)有一個(gè)旅行商人要拜訪N個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。

2010年英國(guó)科學(xué)家的一項(xiàng)研究發(fā)現(xiàn)，大黃蜂顯示出能輕易破解“旅行商問(wèn)題”的能力。進(jìn)行研究的奈杰爾·雷恩博士說(shuō)，蜜蜂每天都要在蜂巢和花朵間飛來(lái)飛去，為了采蜜而在不同的花朵間飛行是一件很耗精力的事情，因此蜜蜂每天都在解決“旅行商”問(wèn)題。

本文介紹了一種新的旅行商問(wèn)題的算法，實(shí)驗(yàn)表明，該算法能較好的解釋大黃蜂是如何解決旅行商問(wèn)題，本文同時(shí)還探討了該算法在解決旅行商問(wèn)題中的一些問(wèn)題和思路。

因?yàn)榇簏S蜂在覓食的過(guò)程中采用了和本算法類似的策略，所以把這算法稱為大黃蜂算法。

1 問(wèn)題的提出

我們知道，在一個(gè)有n個(gè)結(jié)點(diǎn)的圖中，較短的邊不一定會(huì)屬于該圖的最短哈密頓回路，有些較長(zhǎng)的邊反而屬于最短哈密頓回路。

那么，我們自然會(huì)問(wèn)：每個(gè)邊屬于最短哈密頓回路的可能性是多少呢？

我們能否量化它嗎？

對(duì)一個(gè)n個(gè)結(jié)點(diǎn)的圖中，當(dāng)我們找出該圖的最短哈密頓回路時(shí)，我們知道這n個(gè)邊的概率是1，其他邊的概率是0.

但這對(duì)問(wèn)題的解決沒(méi)有任何幫助，當(dāng)n變大時(shí)，問(wèn)題仍然很困難。

我們的基本思路是：對(duì)一個(gè)大的圖按照一定的方法劃分成很多個(gè)子圖，對(duì)每個(gè)子圖我們進(jìn)行計(jì)算，然后匯總并計(jì)算出每條邊在該劃分下屬于最短哈密頓回路的概率。

2 算法介紹

為了方便理解同時(shí)不失一般性，我們假定討論的圖只存在一個(gè)最短哈密頓回路。

同時(shí)，本算法同樣適用一般的拓?fù)鋱D。

2.1 K_劃分（K>=4）

對(duì)一個(gè)有n個(gè)結(jié)點(diǎn)的圖，我們可以對(duì)它劃分為由K個(gè)點(diǎn)的所組成的子圖。這樣，該圖共有[nk]個(gè)這樣的子圖。

例如 對(duì)圖1（n=5）?？梢陨蒀（5，4）個(gè) 4_劃分圖（見(jiàn)圖2）

2.2 K_路徑（K>=4）

是指在一個(gè)K_劃分圖中，過(guò)每個(gè)頂點(diǎn)一次的一條路徑。例如圖3是圖1的一個(gè)4_劃分圖，BECD就是一條從B到D，經(jīng)過(guò)E、C的4_路徑。

2.3 K_有效路徑（K>=4）

K_有效路徑是指一條可能屬于最短哈密頓回路中的一個(gè)連續(xù)段的K_路徑。

一般來(lái)說(shuō)，從A到B的K_路徑里最短的一條是K_有效路徑。

在不同的假設(shè)下，會(huì)有不同的K_有效路徑。

對(duì)每一個(gè)K_劃分圖，我們可以找出它的所有K_有效路徑。例如，對(duì)（圖1）的一個(gè)4_劃分圖（圖3）。

它的有效路徑有：

B到C：只有一條唯一路徑 BEDC 所以BEDC是一條4_有效路徑。

B到D ：這里存在兩條4_路徑 BCED和BECD，因?yàn)長(zhǎng)（BCED）=17，L（BECD）=16，所以BECD是4_有效路徑。

B到E：只有一條有效路徑 BCDE。

C到D：只有一條有效路徑 CBED。

C到E：無(wú)有效路徑

D到E：只有一條有效路徑 DCBE。

2.4 K_統(tǒng)計(jì)

對(duì)圖中每條邊添加成功和失敗兩個(gè)屬性。假設(shè)a1a2…an 是一條K_有效路徑。對(duì)aiai+1（ i=1，2…n-1）邊在成功屬性上加1，其他邊在失敗屬性上加1，邊a1an不做處理。

我們有S（X）代表邊X成功的次數(shù)，用F（X）代表邊X失敗的次數(shù)。

K_統(tǒng)計(jì)是指對(duì)每一個(gè)K_劃分圖，計(jì)算出每條邊的成功和失敗的次數(shù)。然后對(duì)每條邊統(tǒng)計(jì)出它的成功和失敗的總次數(shù)。

以（圖3）為例，總共有5條4_有效路徑： BEDC、BECD、BCDE、CBED和DCBE。

對(duì)每條可能路徑作以下分析：以 BEDC為例，總共有 BE、DE、CD、CE參與競(jìng)爭(zhēng)（B和C是端點(diǎn)，所以BC不參與競(jìng)爭(zhēng)），結(jié)果BE、DE和CD勝出。勝出的成功上加1，沒(méi)選上的失敗上加1。

2.5 K_鏈接度（K>=4）

對(duì)每條邊X我們定義以下公式， LK（X）=[S（X）SX+FX] （K>=4） ，（稱LK（X）為邊X的K_鏈接度。

對(duì)于圖1，根據(jù)匯總表（圖4），我們可以計(jì)算出每條邊的鏈接度L4（X）。

LK（X）代表了X邊在k_劃分下的屬于最短哈密頓回路的概率。

對(duì)于LK（X）有一個(gè)重要的定理。

定理：在一個(gè)有n個(gè)結(jié)點(diǎn)的圖中（假設(shè)存在最短哈密頓回路），如果LK（X）=1，則邊X一定屬于該圖的最短哈密頓回路（證明較簡(jiǎn)單，在這里就不作具體詳述了）。

根據(jù)匯總表，我們可以簡(jiǎn)單的算出最短哈密頓回路是ABCDA。

2.6 條件K_鏈接度（K>=4）

當(dāng)我們假定某條邊或幾條邊屬于最短哈密頓回路時(shí)，其他邊的K_鏈接度就會(huì)發(fā)生變化，我們把在某種條件下的K_鏈接度稱為條件鏈接度，用 CLK（X）來(lái)表示變X的條件K_鏈接度。

CLK（X）有類似于LK（X）的定理。

2.7解集M

是指包含能構(gòu)成一條最短哈密頓回路的邊的集合。當(dāng)把一條邊要加入到解集M的時(shí)候，要檢查它和解集M里的邊是否會(huì)發(fā)生沖突。只有相容的邊才能加入解集M。

對(duì)有n個(gè)結(jié)點(diǎn)的圖來(lái)說(shuō)，解集M最多只能包含N條邊。

3 算法描述

一個(gè)廣義的TSP問(wèn)題是一個(gè)有n個(gè)結(jié)點(diǎn)的拓?fù)鋱D，為了算法描述方便，我們假設(shè)該圖只存在一條最短哈密頓回路。

算法描述如下：

確定K值（K>=4）；

K_統(tǒng)計(jì)；

計(jì)算圖中每條邊的K_鏈接度；

REPEAT

{

找到一條具有最大（條件）K_鏈接度的邊X && X與解集M相容；

將X加入解集M；

K_統(tǒng)計(jì)；

計(jì)算每條邊的條件K_鏈接度。

}

UNTIL 解集M包含了N條邊。

該算法可以實(shí)現(xiàn)用一個(gè)較小的K來(lái)解決一個(gè)較大n的TSP 問(wèn)題，它的復(fù)雜度是： O（nK+3）。

4 對(duì)大黃蜂算法的一些思考和今后的方向

對(duì)于大黃蜂算法，我們還有很多工作要做，重點(diǎn)有以下幾個(gè)方面：

1）k和之間的關(guān)系，一個(gè)很大的n，如何選取一個(gè)合適的k來(lái)進(jìn)行計(jì)算。我們還需要更多的實(shí)驗(yàn)來(lái)確定。

2）對(duì)CLK（X）的一些思考，我們現(xiàn)在是認(rèn)為CLK（X） 最大，該邊屬于最短哈密頓回路的可能性就最大。我們是否能對(duì)k進(jìn)行插值，CLK（X） 的單調(diào)上升的邊也許是屬于最短哈密頓回路的可能性最大。不過(guò)現(xiàn)在還是一個(gè)猜想，需要更多實(shí)驗(yàn)和嚴(yán)格的數(shù)學(xué)證明

3）對(duì)大n的算法驗(yàn)證。

參考文獻(xiàn)：

[1]Travel Optimization by Foraging Bumblebees through Readjustments of Traplines after Discovey of New Feeding Locations The American Naturalist December 2010，176（6）.

[2] How to Solve It：Modern Heuristics Zhigniew Michalewicz David B.Fogel