本章涉及知識(shí)點(diǎn)

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

2咏删、TSP問題定義

3、案例引出

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

5、近似算法的解題步驟

6嘀粱、圖的存儲(chǔ)結(jié)構(gòu)

7激挪、Prim最小生成樹算法

8、樹的遍歷方法

9锋叨、哈密頓回路

10垄分、python編程實(shí)現(xiàn)近似算法

11、結(jié)果分析

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

一般的薄湿，我們將可以在多項(xiàng)式時(shí)間之內(nèi)可求解的問題定義為易處理問題，而將需要超多項(xiàng)式時(shí)間才能求解的問題定義為難處理問題

對(duì)于一個(gè)規(guī)模為n的輸入偷卧，在最壞的情況下(窮舉法)求解的時(shí)間復(fù)雜度為

P類問題的時(shí)間復(fù)雜度

其中k是某個(gè)確定的常數(shù)豺瘤，我們將這類問題定義為P類問題，直觀上听诸，P類問題是在確定性計(jì)算模型下的易解問題類

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

至今為止坐求，人類還沒有找到NP完全問題的多項(xiàng)式時(shí)間算法，并且沒有人可以證明NP問題不存在多項(xiàng)式時(shí)間算法晌梨，這也成為了理論計(jì)算機(jī)科學(xué)領(lǐng)域中最深?yuàn)W的開放問題之一桥嗤，也是NP完全問題令人驚奇的性質(zhì)

最深?yuàn)W的開放問題之一

21世紀(jì)至今，人類對(duì)于任何一個(gè)NP完全問題仔蝌，還沒有多項(xiàng)式時(shí)間算法泛领，因此，在面對(duì)NP問題時(shí)敛惊，通常有以下幾種解題的策略

（1）只針對(duì)NP問題的特殊實(shí)例求解

（2）動(dòng)態(tài)規(guī)劃或者分支限界法

（3）概率論算法

（4）近似解法

（5）人工智能啟發(fā)式算法

（6）神經(jīng)網(wǎng)絡(luò)算法

可以看到渊鞋，無論使用什么上述策略解題，我們只能無限逼近其最優(yōu)解豆混，而不能保證得到通解篓像，本章我們將使用近似解法來求解NP完全問題

二、TSP問題定義

旅行商問題(Traveling salesman problem)皿伺，簡稱為TSP問題员辩，是1959年提出的數(shù)學(xué)規(guī)劃問題，TSP屬于典型的NP完全問題

TSP問題的語言描述為

在一個(gè)具有n個(gè)城市的完全圖中鸵鸥，旅行者希望進(jìn)行一次巡回旅行奠滑，或經(jīng)歷一次哈密頓回路丹皱，可以恰好訪問每一個(gè)城市一次，并且最終回到出發(fā)城市宋税。而這次巡回旅行的總費(fèi)用為訪問各個(gè)城市費(fèi)用的總和摊崭，故旅行者同時(shí)希望整個(gè)行程的費(fèi)用是最低的，求這個(gè)路線的排列策略杰赛？

TSP問題的實(shí)質(zhì)可以抽象為

在一個(gè)帶權(quán)重的完全無向圖中呢簸，找到一個(gè)權(quán)值總和最小的哈密頓回路

TSP問題翻譯為數(shù)學(xué)語言為，在N個(gè)城市的完全無向圖G中

完全無向圖G

其中每個(gè)城市之間的距離矩陣為

城市之間的距離

目標(biāo)函數(shù)為

目標(biāo)函數(shù)

需要求解的變量為w乏屯，w是使得目標(biāo)函數(shù)達(dá)到最小值的一個(gè)排列

城市排列

且w的最后一項(xiàng)滿足回到出發(fā)城市

回到出發(fā)城市

顯然根时，TSP問題的組合解有N!種組合，隨著城市數(shù)量N的規(guī)模增加辰晕，組合數(shù)將呈指數(shù)級(jí)別遞增蛤迎，故使用窮舉法將會(huì)面臨組合爆炸問題，因此TSP屬于NP完全問題

三含友、案例引出

有如下含有8個(gè)頂點(diǎn)的完全無向圖G替裆，每一邊有非負(fù)的費(fèi)用值，試著找出G的最小費(fèi)用的哈密頓回路窘问？

案例無向圖G

其中各個(gè)城市的坐標(biāo)為

各個(gè)城市坐標(biāo)

這個(gè)案例的組合數(shù)為8!=40320種組合

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

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

我們從費(fèi)用函數(shù)出發(fā)南缓，費(fèi)用函數(shù)也叫代價(jià)函數(shù)胸遇，指的是兩個(gè)城市之間的費(fèi)用指數(shù)或者代價(jià)程度的量化。在大多數(shù)的實(shí)際情況中汉形，從一個(gè)地方u直接到另一個(gè)地方w纸镊，這個(gè)走法花費(fèi)的代價(jià)總是最小的，而如果從u到w需要經(jīng)過某個(gè)中轉(zhuǎn)站v概疆，則這種走法花費(fèi)的代價(jià)卻不可能比直接到達(dá)的走法花費(fèi)的代價(jià)更小

將上述的理論轉(zhuǎn)化為數(shù)學(xué)語言為

直接走法的代價(jià)小于中轉(zhuǎn)走法

其中c是費(fèi)用函數(shù)逗威，這個(gè)方程說明了，直接從u->w花費(fèi)的代價(jià)岔冀，要比從u->v->w花費(fèi)的代價(jià)要小凯旭，我們稱這個(gè)費(fèi)用函數(shù)滿足三角不等式

三角不等式的定義為：任意一個(gè)歐拉平面的三角形兩邊之和始終大于第三邊，這是一個(gè)非常自然的不等式使套，其中歐拉平面上任意兩點(diǎn)之間的歐式距離就滿足三角不等式罐呼，

為此，我們只要設(shè)TSP中的費(fèi)用函數(shù)為歐式距離侦高，即可將TSP問題轉(zhuǎn)化為滿足三角不等式的TSP模型

五嫉柴、近似算法的解題步驟

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

（1）選擇G的任意一個(gè)頂點(diǎn)r作為根節(jié)點(diǎn)(出發(fā)/結(jié)束點(diǎn))

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

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

（4）將r加到頂點(diǎn)表L的末尾奉呛，按L中頂點(diǎn)的次序組成哈密頓回路H

數(shù)學(xué)上已經(jīng)證明计螺，當(dāng)費(fèi)用函數(shù)滿足三角不等式時(shí)夯尽，上述近似算法找出的哈密頓回路產(chǎn)生的總費(fèi)用，不會(huì)超過最優(yōu)回路的2倍

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

六登馒、圖的存儲(chǔ)結(jié)構(gòu)

首先我們需要將圖表示為我們熟悉的數(shù)據(jù)結(jié)構(gòu)匙握，圖可以使用兩種存儲(chǔ)結(jié)構(gòu)，分別是鄰接鏈表和鄰接矩陣

鄰接鏈表：是一個(gè)由鏈表組成的一維數(shù)組陈轿，數(shù)組中每個(gè)元素都存儲(chǔ)以每個(gè)頂點(diǎn)為表頭的鏈表

鄰接矩陣：以矩陣的形式存儲(chǔ)圖中所有頂點(diǎn)之間的關(guān)系

用鏈表表示圖的關(guān)系圈纺，會(huì)顯得數(shù)據(jù)結(jié)構(gòu)較為復(fù)雜，但節(jié)省空間的開銷麦射，而用矩陣來表示圖的關(guān)系就顯得非常清晰赠堵，但空間開銷較大，這里我們選擇鄰接矩陣來表示TSP案例中的無向圖G

TSP案例中G的鄰接矩陣

我們?cè)O(shè)歐式距離為費(fèi)用函數(shù)法褥，矩陣中的每一行代表G中每一個(gè)的頂點(diǎn)到其余各個(gè)頂點(diǎn)的費(fèi)用(歐式距離)，如果出現(xiàn)到達(dá)不了或者自身到達(dá)自身的情況酬屉，我們用無窮大inf來填充表示不可達(dá)

至此半等，我們就定義好了G的存儲(chǔ)結(jié)構(gòu)，就可以很清晰的訪問翻譯G的每一個(gè)數(shù)據(jù)呐萨，如G[2][3]就翻譯為：從第2個(gè)城市到達(dá)第3個(gè)城市的費(fèi)用為4.24264096

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

七、Prim最小生成樹算法

我們知道谬擦，兩點(diǎn)可以確定一條直線切距，則最小生成樹的定義為：用n-1條邊連接具有n個(gè)頂點(diǎn)的無向圖G，并且使得邊長的總和最小

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

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

（2）T的總長度達(dá)到最小值

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

（1）設(shè)集合V是G中所有的頂點(diǎn)北秽，集合U是G中已經(jīng)走過的頂點(diǎn)葡幸，集合U-V是G中沒有走過的頂點(diǎn)

（2）從G中的起點(diǎn)a開始遍歷，將a加入到集合U中贺氓，并將a從集合U-V替出

（3）在集合U-V中剩余的n-1個(gè)頂點(diǎn)中尋找與集合U中的a關(guān)聯(lián)蔚叨，且權(quán)重最小的那條邊的終點(diǎn)b，將b加入到集合U中辙培，并將b從集合U-V替出

（4）同理蔑水，在集合U-V中剩余的n-2個(gè)頂點(diǎn)中尋找與集合U中的a或b關(guān)聯(lián)，且權(quán)重最小的那條邊的終點(diǎn)c扬蕊，將c加入到集合U中搀别，并將c從集合U-V替出

（5）重復(fù)步驟(4)，直到G中所有的頂點(diǎn)都加入到集合U厨相，且集合U-V為空领曼，則集合U中的頂點(diǎn)就構(gòu)成了T

顯然鸥鹉，Prim算法的策略屬于貪心算法，因?yàn)槊恳徊剿尤氲倪吺荆急仨毷鞘沟卯?dāng)前數(shù)T的總權(quán)重增加量最小的邊

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

案例最小生成樹T

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

八单刁、樹的遍歷方法

找到T之后灸异，接下來需要遍歷T，我們知道羔飞，遍歷一棵樹有三種遍歷規(guī)則肺樟，前序遍歷、中序遍歷和后序遍歷

（1）前序遍歷：訪問根節(jié)點(diǎn)—>前序遍歷左子樹—>前序遍歷右子樹

（2）中序遍歷：前序遍歷左子樹—>訪問根節(jié)點(diǎn)—>前序遍歷右子樹

（3）后序遍歷：前序遍歷左子樹—>前序遍歷右子樹—>訪問根節(jié)點(diǎn)

上述案例中的T逻淌，以a為根節(jié)點(diǎn)開始前序遍歷么伯，遍歷出的節(jié)點(diǎn)即組成頂點(diǎn)表L

案例前序遍歷

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

九卡儒、哈密頓回路

哈密頓回路的定義為：由指定的起點(diǎn)前往指定的終點(diǎn)田柔，途中經(jīng)過的城市有且只經(jīng)過一次，所以一個(gè)無向圖中含有若干個(gè)哈密頓回路

按照近似算法的最后一步骨望，我們將T的根節(jié)點(diǎn)a加入到頂點(diǎn)表L的末尾硬爆，將L的頂點(diǎn)順序依次連接，就得到T的哈密頓回路H

案例哈密頓回路

至此擎鸠，我們就完成了近似算法的計(jì)算缀磕，找到了一個(gè)在G中從a出發(fā)，最后回到a劣光，中間每個(gè)城市只經(jīng)過一次的最小費(fèi)用的行程走法袜蚕，即計(jì)算出了目標(biāo)函數(shù)的頂點(diǎn)排列w為

案例的頂點(diǎn)排列

按照這個(gè)排列，旅行線路的總費(fèi)用x*=19.074

十绢涡、python編程實(shí)現(xiàn)近似算法

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

費(fèi)用函數(shù)（歐式距離）

找到代價(jià)最小的邊

維護(hù)未走過的點(diǎn)的集合

prim算法

先序遍歷圖

生成哈密爾頓回路H

運(yùn)行結(jié)果

十一廷没、結(jié)果分析

從結(jié)果上可以看出，近似算法是解決TSP問題的一種有效方法垂寥，它可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算出一個(gè)近似解颠黎，來逼近真實(shí)的最優(yōu)解，這個(gè)近似解盡量的逼近滿足TSP的條件

（1）從開始點(diǎn)回到開始點(diǎn)滞项，每個(gè)點(diǎn)都要經(jīng)過且只經(jīng)過一次

（2）行程的總費(fèi)用達(dá)到最小值

案例中狭归，實(shí)際的最優(yōu)解(頂點(diǎn)組合)應(yīng)該是

案例的實(shí)際最優(yōu)解

實(shí)際的最優(yōu)解的總費(fèi)用為x=14.715

我們可以看到，近似算法找出的近似解的總費(fèi)用x*文判，和實(shí)際最優(yōu)解的總費(fèi)用x滿足比例

近似比

我們可以總結(jié)出以下幾點(diǎn)近似算法求解TSP問題

（1）近似算法是求解TSP問題的一個(gè)漸進(jìn)式算法

（2）近似解法求出的近似解和實(shí)際最優(yōu)解的近似比不超過2过椎，即w的總代價(jià)，在最優(yōu)總代價(jià)的2倍之內(nèi)

最后戏仓，要想真正的計(jì)算出案例的最優(yōu)解疚宇，我們需要求解TSP問題的另一種算法—人工智能啟發(fā)式算法亡鼠，這個(gè)算法我們?cè)谙乱恢v中再來說明

案例代碼見：求解TSP問題—近似算法