TSP問題—近似演算法

本章涉及知識點

1、NP完全問題和其解題策略

2、TSP問題定義

3、案例引出

4、滿足三角不等式的TSP模型

5、近似演算法的解題步驟

6、圖的存儲結構

7、Prim最小生成樹演算法

8、樹的遍歷方法

9、哈密頓迴路

10、python編程實現近似演算法

11、結果分析

一、NP完全問題和其解題策略

一般的，我們將可以在多項式時間之內可求解的問題定義為易處理問題，而將需要超多項式時間才能求解的問題定義為難處理問題

對於一個規模為n的輸入，在最壞的情況下(窮舉法)求解的時間複雜度為

其中k是某個確定的常數，我們將這類問題定義為P類問題，直觀上，P類問題是在確定性計算模型下的易解問題類

而NP問題就是在非確定性計算模型下的難處理問題

至今為止，人類還沒有找到NP完全問題的多項式時間演算法，並且沒有人可以證明NP問題不存在多項式時間演算法，這也成為了理論計算機科學領域中最深奧的開放問題之一，也是NP完全問題令人驚奇的性質

21世紀至今，人類對於任何一個NP完全問題，還沒有多項式時間演算法，因此，在面對NP問題時，通常有以下幾種解題的策略

（1）只針對NP問題的特殊實例求解

（2）動態規劃或者分支限界法

（3）概率論演算法

（4）近似解法

（5）人工智慧啟發式演算法

可以看到，無論使用什麼上述策略解題，我們只能無限逼近其最優解，而不能保證得到通解，本章我們將使用近似解法來求解NP完全問題

二、TSP問題定義

旅行商問題(Traveling salesman problem)，簡稱為TSP問題，是1959年提出的數學規劃問題，TSP屬於典型的NP完全問題

TSP問題的語言描述為

在一個具有n個城市的完全圖中，旅行者希望進行一次巡迴旅行，或經歷一次哈密頓迴路，可以恰好訪問每一個城市一次，並且最終回到出發城市。而這次巡迴旅行的總費用為訪問各個城市費用的總和，故旅行者同時希望整個行程的費用是最低的，求這個路線的排列策略？

TSP問題的實質可以抽象為

在一個帶權重的完全無向圖中，找到一個權值總和最小的哈密頓迴路

TSP問題翻譯為數學語言為，在N個城市的完全無向圖G中

其中每個城市之間的距離矩陣為

目標函數為

需要求解的變數為w，w是使得目標函數達到最小值的一個排列

且w的最後一項滿足回到出發城市

顯然，TSP問題的組合解有N!種組合，隨著城市數量N的規模增加，組合數將呈指數級別遞增，故使用窮舉法將會面臨組合爆炸問題，因此TSP屬於NP完全問題

三、案例引出

有如下含有8個頂點的完全無向圖G，每一邊有非負的費用值，試著找出G的最小費用的哈密頓迴路？

其中各個城市的坐標為

這個案例的組合數為8!=40320種組合

四、滿足三角不等式的TSP模型和演算法步驟

接下來，我們選擇近似演算法來求解案例TSP問題

我們從費用函數出發，費用函數也叫代價函數，指的是兩個城市之間的費用指數或者代價程度的量化。在大多數的實際情況中，從一個地方u直接到另一個地方w，這個走法花費的代價總是最小的，而如果從u到w需要經過某個中轉站v，則這種走法花費的代價卻不可能比直接到達的走法花費的代價更小

將上述的理論轉化為數學語言為

其中c是費用函數，這個方程說明了，直接從u->w花費的代價，要比從u->v->w花費的代價要小，我們稱這個費用函數滿足三角不等式

三角不等式的定義為：任意一個歐拉平面的三角形兩邊之和始終大於第三邊，這是一個非常自然的不等式，其中歐拉平面上任意兩點之間的歐式距離就滿足三角不等式，

為此，我們只要設TSP中的費用函數為歐式距離，即可將TSP問題轉化為滿足三角不等式的TSP模型

五、近似演算法的解題步驟

求解上述TSP模型的近似演算法分為以下步驟

（1）選擇G的任意一個頂點r作為根節點(出發/結束點)

（2）用Prim演算法找出G的一棵以r為根的最小生成樹T

（3）前序遍歷訪問樹T，得到遍歷順序組成的頂點表L

（4）將r加到頂點表L的末尾，按L中頂點的次序組成哈密頓迴路H

數學上已經證明，當費用函數滿足三角不等式時，上述近似演算法找出的哈密頓迴路產生的總費用，不會超過最優迴路的2倍

下面我們就按照近似演算法的步驟來一步步求解案例TSP問題

六、圖的存儲結構

首先我們需要將圖表示為我們熟悉的數據結構，圖可以使用兩種存儲結構，分別是鄰接鏈表和鄰接矩陣

鄰接鏈表：是一個由鏈表組成的一維數組，數組中每個元素都存儲以每個頂點為表頭的鏈表

鄰接矩陣：以矩陣的形式存儲圖中所有頂點之間的關係

用鏈表表示圖的關係，會顯得數據結構較為複雜，但節省空間的開銷，而用矩陣來表示圖的關係就顯得非常清晰，但空間開銷較大，這裡我們選擇鄰接矩陣來表示TSP案例中的無向圖G

我們設歐式距離為費用函數，矩陣中的每一行代表G中每一個的頂點到其餘各個頂點的費用(歐式距離)，如果出現到達不了或者自身到達自身的情況，我們用無窮大inf來填充表示不可達

至此，我們就定義好了G的存儲結構，就可以很清晰的訪問翻譯G的每一個數據，如G[2][3]就翻譯為：從第2個城市到達第3個城市的費用為4.24264096

至此，我們就完成近似演算法的第一步

七、Prim最小生成樹演算法

我們知道，兩點可以確定一條直線，則最小生成樹的定義為：用n-1條邊連接具有n個頂點的無向圖G，並且使得邊長的總和最小

接下來我們需要找到G中的這顆最小生成樹T，從T的定義可知，T滿足

（1）T有且只有n-1條邊

（2）T的總長度達到最小值

這裡我們使用Prim演算法來生成T，Prim演算法的策略步驟為

（1）設集合V是G中所有的頂點，集合U是G中已經走過的頂點，集合U-V是G中沒有走過的頂點

（2）從G中的起點a開始遍歷，將a加入到集合U中，並將a從集合U-V替出

（3）在集合U-V中剩餘的n-1個頂點中尋找與集合U中的a關聯，且權重最小的那條邊的終點b，將b加入到集合U中，並將b從集合U-V替出

（4）同理，在集合U-V中剩餘的n-2個頂點中尋找與集合U中的a或b關聯，且權重最小的那條邊的終點c，將c加入到集合U中，並將c從集合U-V替出

（5）重複步驟(4)，直到G中所有的頂點都加入到集合U，且集合U-V為空，則集合U中的頂點就構成了T

顯然，Prim演算法的策略屬於貪心演算法，因為每一步所加入的邊，都必須是使得當前數T的總權重增加量最小的邊

按照Prim演算法，我們案例的最小生成樹T為

至此，我們就完成近似演算法的第二步

八、樹的遍歷方法

找到T之後，接下來需要遍歷T，我們知道，遍歷一棵樹有三種遍歷規則，前序遍歷、中序遍歷和後序遍歷

（1）前序遍歷：訪問根節點—>前序遍歷左子樹—>前序遍歷右子樹

（2）中序遍歷：前序遍歷左子樹—>訪問根節點—>前序遍歷右子樹

（3）後序遍歷：前序遍歷左子樹—>前序遍歷右子樹—>訪問根節點

上述案例中的T，以a為根節點開始前序遍歷，遍歷出的節點即組成頂點表L

至此，我們就完成近似演算法的第三步

九、哈密頓迴路

哈密頓迴路的定義為：由指定的起點前往指定的終點，途中經過的城市有且只經過一次，所以一個無向圖中含有若干個哈密頓迴路

按照近似演算法的最後一步，我們將T的根節點a加入到頂點表L的末尾，將L的頂點順序依次連接，就得到T的哈密頓迴路H

至此，我們就完成了近似演算法的計算，找到了一個在G中從a出發，最後回到a，中間每個城市只經過一次的最小費用的行程走法，即計算出了目標函數的頂點排列w為

按照這個排列，旅行線路的總費用x*=19.074

十、python編程實現近似演算法

接下來我們將近似演算法翻譯為代碼即可

費用函數（歐式距離）

找到代價最小的邊

維護未走過的點的集合

prim演算法

先序遍歷圖

生成哈密爾頓迴路H

運行結果

十一、結果分析

從結果上可以看出，近似演算法是解決TSP問題的一種有效方法，它可以在多項式時間內計算出一個近似解，來逼近真實的最優解，這個近似解盡量的逼近滿足TSP的條件

（1）從開始點回到開始點，每個點都要經過且只經過一次

（2）行程的總費用達到最小值

案例中，實際的最優解(頂點組合)應該是

實際的最優解的總費用為x=14.715

我們可以看到，近似演算法找出的近似解的總費用x*，和實際最優解的總費用x滿足比例

我們可以總結出以下幾點近似演算法求解TSP問題

（1）近似演算法是求解TSP問題的一個漸進式演算法

（2）近似解法求出的近似解和實際最優解的近似比不超過2，即w的總代價，在最優總代價的2倍之內

最後，要想真正的計算出案例的最優解，我們需要求解TSP問題的另一種演算法—人工智慧啟發式演算法，這個演算法我們在下一講中再來說明

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！