林農(nóng)

(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東東莞 523808)

旅行商問題圖論近似算法有效性分析

林農(nóng)

(東莞理工學(xué)院 計(jì)算機(jī)學(xué)院，廣東東莞 523808)

給出旅行商問題四種圖論近似算法及有效性分析，改進(jìn)第一種近似算法證明，修正第二、三、四種近似算法有效性的上界。

旅行商問題;NP難題;圖論;近似算法;算法有效性

旅行商問題是組合數(shù)學(xué)中著名的NP難題［1，2］，它在實(shí)際中有著廣泛而深入的應(yīng)用，在超大規(guī)模集成電路設(shè)計(jì)和路徑規(guī)劃都有重要應(yīng)用價值，它的計(jì)算復(fù)雜性研究在形成NP完全理論中起到奠基作用［3］。因而這幾年對它的研究一直是熱點(diǎn)問題。目前對它的研究方法有兩類，第一類：思想性和構(gòu)造性方法，如分支限界法和近似算法。第二類：隨著智能算法在各個領(lǐng)域的應(yīng)用，而產(chǎn)生的一些仿生優(yōu)化算法，如遺傳算法和螞蟻算法，這一類方法和經(jīng)典組合數(shù)學(xué)方法結(jié)合，能夠加速算法速度，提高解的質(zhì)量［3］。本文在旅行商問題的四種圖論近似算法的基礎(chǔ)上，對第一種近似算法證明給予改進(jìn)，對第二、三、四種近似算法效率的上界給予修正。

1 最近鄰法［4］

算法思想和基本步驟：

1) 從一個頂點(diǎn)開始，令P=(j1)。

2) 設(shè)當(dāng)前路徑為P=(j1，j2，…，jk)，從尚未搜查的n-k個頂點(diǎn)中加入和jk，最鄰近的點(diǎn)jk+1，得到新的路徑 P=(j1，j2，…，jk，jk+1)，直至包含 n 個頂點(diǎn)。

3)連接起始頂點(diǎn)和終止頂點(diǎn)，得到就是最近鄰法的旅行回路。設(shè)最短哈密頓回路長度為，最近鄰法旅行回路長度為Nn。

證明 設(shè)結(jié)點(diǎn)集 A={v1，v2，…，vmin{2k，n}}，

使得與vi相關(guān)聯(lián)的最短邊li，滿足l1≥l2≥…≥lmin{2k，n}。

由最近鄰法知：dij≥min{li，lj}，

故

其中至多有k個αi=0，則至少有min{2k，n}－k個αi=2，

在最小的情況下，k個 αi=0，對應(yīng)l1，l2，…，lk，

min{2k，n}－ k 個 αi=2 ，對應(yīng) lk+1，lk+2，…，lmin{2k，n}，

(證畢)

2 最近鄰插入法［4］

算法思想和基本步驟：

1)從一個頂點(diǎn)開始，構(gòu)造不斷擴(kuò)大的回路。

2)設(shè)包含k個頂點(diǎn)的最佳回路為Tk，加入和Tk最鄰近的頂點(diǎn)，插入位置使得回路增量最小，成新的最佳回路Tk+1，直至包含n個頂點(diǎn)，即得最近鄰插入法旅行回路。設(shè)最短哈密頓回路長度為，最鄰近插入法旅行回路長度為In。

由最近鄰插入法知，存在旅行回路上點(diǎn)p，及點(diǎn)p相鄰但不在旅行回路上點(diǎn)q(有時q=i)，及點(diǎn)i在同一道路上。這樣點(diǎn)i和邊pq建立一一對應(yīng)關(guān)系。當(dāng)插入點(diǎn)i時，回路增量記為δi，則δi=dij+dikdjk。

δi和dpq的關(guān)系如下：

由三角不等式，有dik-djk≤dij，從而 δi=dij+dik-djk≤2dij，又由最近鄰插入法，有dij≤dpq，因此δi≤2dpq。

In和T*n的關(guān)系如下：

(證畢)

3 生成樹加倍算法［5］

算法的思想和基本步驟：

1)求最小生成樹;

2)利用深探法遍歷最小生成樹，回頭時遍歷邊計(jì)算在內(nèi)，即每條邊計(jì)算兩次，得一回路;

3)刪除回路中后面重復(fù)出現(xiàn)的結(jié)點(diǎn)，最后一個除外，得生成樹加倍算法旅行回路。

證明

(證畢)

4 生成樹加匹配算法［5］

算法的思想和基本步驟：

1)求最小生成樹;

2)最小生成樹上的奇點(diǎn)，共有偶數(shù)個，求最小權(quán)匹配;

3)最小生成樹及最小生成樹奇點(diǎn)的最小權(quán)匹配構(gòu)成歐拉圖，求歐拉回路;

4)刪除歐拉回路中后面重復(fù)出現(xiàn)的結(jié)點(diǎn)，最后一個除外。即得生成樹加匹配算法旅行回路。

定理4 算法有效性為

設(shè)訪問最小生成樹上奇次結(jié)點(diǎn)的順序和訪問最短哈密頓回路結(jié)點(diǎn)的順序相同，得到一個回路。該回路有偶數(shù)個結(jié)點(diǎn)，可以分解成兩個匹配M1，M2。

由三角不等式，得

(證畢)

［1］Lawler E L，Lenstra J K，Rinnooy Kan A H G，et al．The traveling salesman problem：a guided tour of combinatorial optimization［M］．New York：Wiley，1985．

［2］Garey M R，Johnson D S．Computers and intractability：a guide to the theory of NP-Completeness［M］．San Francisco：W H Freeman，1979．

［3］陳繼業(yè)．旅行商問題的近似算法研究［D］．長沙：國防科技大學(xué)，2005．

［4］盧開澄．計(jì)算機(jī)算法導(dǎo)引-設(shè)計(jì)與分析［M］．2版．北京：清華大學(xué)出版社，2006：276-384．

［5］謝政，李建平．網(wǎng)絡(luò)算法與復(fù)雜性理論［M］．長沙：國防科技大學(xué)出版社，1995：332-353．

An Analysis of the Effectiveness of Approximate Algorithms Based on Graph Theory for the Traveling Salesman Problem

LIN Nong
(College of Computer，Dongguan University of Technology，Dongguan 523808，China)

Based on graph theory and their effectiveness，four approximate algorithms are given，adapting the proof technique of the first，modifying the upper bound of the second，third and fourth ．

traveling salesman;graph theory;approximate algorithm;effectiveness of algorithm

O157．5;TP301．6

A

1009-0312(2012)01-0010-04

2011-04-12

林農(nóng) (1975—)，女，福建龍巖人，講師，碩士，主要從事圖論及其算法研究。