大黃蜂如何找到最短迴路

大黃蜂如何解決TSP問題

（作為《智在民間》社會實踐試驗活動的一部分，如有能對本文找出重大錯誤或對本文提出重要改進意見並被採納的讀者，將給予1000元獎勵並在本文正式發表時享有共同署名權。本文是原創論文，我們一定會遵守承諾，本文演算法已申請專利，謝絕剽竊。本聲明自刊出一年內有效，謝謝）

1：前言

TSP，即Traveling Salesman Problem，也就是旅行商問題，簡稱為TSP問題。該問題是在尋求單一旅行者由起點出發，通過所有給定的需求點之後，最後再回到原點的最小路徑成本。

2010年10月25日。英國倫敦大學皇家霍洛韋學院等機構研究人員報告說，大黃蜂顯示出了輕而易舉破解這個問題的能力（見文獻[1]）。對於大黃蜂是如何快速找到最短迴路的問題，目前對科學界來說還是個謎，本文提出了一個新穎、高效的演算法，能很好的回答這個問題。

在本文中，我們把最短哈密頓迴路（Hamiltonian cycle）簡稱為最短迴路。

2：演算法簡介

2.1：問題的提出

如圖一，從城市A出發，如果按照貪心演算法構造的路徑為 ABCDA，總費用是2+3+23+5=33，而路徑ACBDA的費用是 4+3+7+5=19。

我們自然會問：為什麼要選擇邊AC，而不能選擇邊AB呢？我們該如何判斷一條邊是否屬於該圖的最短迴路？我們能不能定量計算出某條邊屬於最短迴路的可能性大小呢？

2.2：組團比賽和計分規則：

對於圖一中的邊AB和AC，如果直接比較的話，很難判斷出優劣。我們的解決方案是用路徑和路徑進行比賽。

定義：有效路徑EPk (K>=4)是指一條由K個點組成的可能屬於該圖最短迴路中的一條路徑。

推論：如果a0a1….ak-1是一條EPk，那麼它一定是從a0到ak-1經過a1、a2、。。。、ak-2點的最短路徑。

例如：CBDA就是圖一的一條EP4。它是C到A經過B、D點的最短路徑。從C到A經過B、D點共有兩條路徑：CBDA和CDBA。在這次比賽中，CBDA勝出，邊CB、BD、DA各得一分，CD、BA得零分。邊CB、BD、DA、CD、BA都參加了一次比賽。

我們把上述的過程稱作一次比賽。

2.3：鏈接度

我們把邊X在所有比賽中的勝率稱為邊X的鏈接度。

把一張圖的所有EPk (K>=4)都找出，計算算出每條邊在所有比賽的得分之和和參加比賽的總次數，記邊X的得分總和為S(X)，邊X參加比賽的總次數為T(X)。

邊X鏈接度LK(X)=S(X) /T(X) （K>=4）。

例如：對圖一，我們取K=4，我們可以計算出：S(AB)=1，S(AC)=3，S(AD)=5，S(BC)=5，S(BD)=3，S(CD)=1。每條邊參與比賽的總次數T(X)=5，所以我們可以算出每條邊的鏈接度，L4(AB)=0.2，L4(AC)=0.6，L4(AD)=1，L4(BC)=1，L4(BD)=0.6，L4(CD)=0.2。

某種意義上說，每條邊的鏈接度代表了它在K劃分下屬於最短迴路的可能性大小。按鏈接度的大小，使用貪心演算法我們可以輕而易舉的找到圖一的最短迴路ACBDA。

3：大黃蜂如何尋找最短迴路？

3.1：四邊形劃分

大黃蜂採用的是k=4的情況下來計算每條邊的鏈接度。它把整個圖形劃分成多個四邊形來處理。如果圖的結點數N=6，就需要處理=15個四邊形。

在歐幾里得空間里，四邊形可以分成凸四邊形（如圖二）和凹四邊形兩大類（如圖三）。

對四邊形的處理有下面的簡單方法。

對每個四邊形，存在6條EP4。這裡計算有如下簡單的規則：假設l(X)是邊X的長度，

a)凸四邊形(圖二)：如果l(AD)+l(CB)>l(CD)+l(AB)，則每條邊的得分 S(CD)=S(CD)+5，S(AB)=S(AB)+5，S(AD)=S(AD)+3，S(BC)=S(BC)+3，S(AC)=S(AC)+1，S(BD)=S(BD)+1。每條邊參與比賽的次數T(X)=T(X)+5，X = AB、AC、AD、BC、BD、CD。

b)凹四邊形（圖三）如果 l(AD)+l(BC)<l(AC)+l(BD)<l(AB)+l(CD)，則每條邊的得分 S(AD)=S(AD)+5，S(BC)=S(BC)+5，S(AC)=S(AC)+3，S(BD)=S(BD)+3，S(AB)=S(AB)+1，S(CD)=S(CD)+1。每條邊參與比賽的次數T(X)=T(X)+5，X = AB、AC、AD、BC、BD、CD。

這樣，大黃蜂每次處理一個四邊形平均只需要做二次判斷。

3.2：鏈接度的計算

大黃蜂對每條邊X計算出它S(X)和T(X)（大黃蜂在實際計算過程中，我們推測只計算S(X)），然後根據每條邊L4(X)的大小，用貪心演算法來產生出一條最短迴路。

如圖四，我們可以計算出每條邊參與比賽的總次數T(X)=75。每條邊的總得分如下：

S(AB)=27 S(AC)=41 S(AD)=75 S(AE)=65 S(AF)=41 S(AG)=43 S(AH)=23

S(BC)=45 S(BD)=21 S(BE)=57 S(BF)=57 S(BG)=35 S(BH)=73

S(CD)=51 S(CE)=21 S(CF)=39 S(CG)=51 S(CH)=67

S(DE)=53 S(DF)=39 S(DG)=51 S(DH)=25

S(EF)=43 S(EG)=37 S(EH)=39

S(FG)=53 S(FH)=43

S(GH)=45

由於T(X)都是75，所以我們只需比較S(X)的大小。

根據貪心演算法，我們第一次找到邊AD，然後BH，CH，AE，BE，FG，CG,最後DF。

所以，最短迴路為 ADFGCHBEA。

3.3：尋找最短迴路

大黃蜂在尋找最短迴路的過程中，遵循以下三個規則：

一：最短迴路不會自我相交；

二：最短迴路里每連續四個點都構成一個有效路徑；

三：如果找到的迴路里有邊的鏈接度小於0.5，則去掉該邊，嘗試尋找另外的迴路。並選其中最短的迴路作為最短迴路。

例如圖四，因為S(BE)=57，S(BF)=57，如果你選擇了BF的話，我們可以找到這樣一條迴路：ADCHBFGEA。這裡S(GE)=37，鏈接度小於0.5，去掉邊EG，可以找到EB，這樣我們就找到了另外一條迴路：ADFGCHBEA。

對於規則三，從嚴格的意義上來說，我們還沒找到實例。因為圖四的例子可以用兩條路徑都計算一次的方法來尋找最短迴路。但我們推測，在某些極端的情況下，大黃蜂可能會使用到規則三。

3.4：計算量和有效計算量

大黃蜂在尋找最短迴路的過程中，對N=6，需要處理15個四邊形，對N=8，需要處理70個四邊形。每個四邊形平均需要做兩次判斷和6次加法。根據統計學原理，大黃蜂處理到一定數量的四邊形時，其實已經能夠尋找出最短迴路了。

實驗表明，對N=6的情況，大概只需處理7-8個四邊形；在N=8的時候，大概需處理25個四邊形。

我們推測，大黃蜂的定址過程和四邊形的處理過程是兩個獨立而且平行的行為，在尋找最短迴路的過程中，大黃蜂會處理完全部的四邊形，不過當它處理到一定數量的四邊形後，已經能夠產生出最短迴路了，剩下的工作對觀察者來說已沒有實際意義了。

3.5：實驗結果

根據國外的實驗報道，有關大黃蜂的實驗大多集中在6個結點上，只有一小部分實驗是8個結點，我們用計算機分別模擬了這兩種狀況。

對N=6，我們進行了上百次的實驗，全部都能根據貪心演算法直接產生出最短迴路。

對N=8，作為一次獨立的實驗，我們隨機一次性產生出20個圖形。其中16個圖形根據貪心演算法和規則一直接找到了最短迴路。另外4個圖形用貪心演算法和規則一先找出一條迴路，然後根據規則二，連續的四個點都需構成一個EP4來進行優化，同樣也順利找到了最短迴路。

4：大黃蜂演算法和一些討論

TSP問題的難點在於當節點數N很大的時候，如何能否找到最短迴路。對於本文所介紹的演算法，在大節點數N的情況下，我們作如下改進：

Ⅰ：取一個合適的K (K>=4)來對圖形進行劃分（我們希望用一個較小的K來解決一個大N的問題） 。

Ⅱ：在當前解集的基礎上計算每條邊的鏈接度LK(X)。

Ⅲ：取出具有最大鏈接度且與解集不衝突的邊加入解集。如果解集中有N條邊，結束。否則返回Ⅱ。

該演算法的計算複雜度為。

這個演算法有一些有趣和非常重要的性質，同時也可以產生出很多變化，我們下一步的研究工作將主要在以下幾個方面展開：

一：如果邊X的LK(X)=1 ，邊X一定屬於最短迴路嗎？（核心定理？）

對K=4 或K=5時，回答是對的，在一般情況下，目前為止我們既不能證明成立也沒有找到反例。

我們的猜想是：在歐幾里得空間里，該定理成立。

二：隨著K的增大，鏈接度LK(X)是否具有單調性和它的趨勢問題

三：對不同的K的每條邊的不完全鏈接度的統計。

四：K和N之間的關係。

TSP是一個NPC問題，對它的研究具有極其重要的意義，我們希望通過對該演算法的研究，能對TSP問題做出一點有益的工作。

如果可以的話，我們希望能把這種演算法稱為大黃蜂演算法。

參考文獻：

[1] Mathieu Lihoreau, Lars Chittka, and Nigel E.Raine. Travel Optimization by Foraging Bum

blebees through Readjustments of Traplines after Discovery of New Feeding Location VOL.176, NO.6 THE AMERICAN NATURALIST DECEMBER 2010

（作者E-MAIL : bob_yunet@163.com）

推薦閱讀：