旅行售貨員問題

旅行售貨員問題(travelling salesman problem)是一類組合最最佳化問題，設有一個售貨員從城市1出發，到城市2，3，…，n去推銷貨物，最後回到城市1.假定任意兩個城市i，j間的距離d_ij(d_ij=d_ji)是已知的，問他應沿著什麼樣的路線走，才能使走過的路線最短?容易看出，中國郵遞員問題要求走遍所有“線”，而後者要求走遍所有“點”，旅行售貨員問題就是在一個完全網路中，找出一個具有最小權的哈密頓圈，尋求旅行售貨員問題的有效算法似乎是沒有希望的，它屬於NP完全類，一個可行的辦法是首先求一個哈密頓圈，然後適當修改，以得到具較小權的另一個哈密頓圈，旅行售貨員問題有著明顯的實際意義，除售貨員之外，郵局裡負責到各個信箱取信的郵遞員，以及去各個分局送郵件的汽車等都會類似地遇到這個問題，還有一些問題表面上似乎與之無關，而實質上卻可以歸結為旅行售貨員問題求解，如計算機線路問題、無中間存儲的工件加工問題等。

基本介紹

• 中文名：旅行售貨員問題
• 外文名：travelling salesman problem
• 所屬學科：數學
• 簡介：一類組合最最佳化問題

基本介紹

設有p個城鎮，已知每兩個城鎮之間的距離，一個售貨員從某一城鎮出發巡迴售貨，問這個售貨員應如何選擇路線，能使每個城鎮經過一次且僅一次，最後返回到出發地，而使總的行程最短？這個問題稱為旅行售貨員問題。容易看出，旅行售貨員問題就是在一個賦權完全圖中找一個具有最小權的Hamilton圈，我們稱這種圈為最優Hamilton圈。

除旅行售貨員問題之外，郵局中負責到各個信箱取信的郵遞員，以及去各個分局送郵件的汽車等都會類似遇到這種問題，還有一些問題表面上似乎與之無關，而實質上卻可以歸結為旅行售貨員問題來解決，既然這個問題有著如此廣泛的套用，那么找一個求解最優Hamilton圈的有效算法就成為一件非常重要的事。

問題解法

目前還沒有一個求解最優Hamilton圈的有效算法，所以希望有一個方法以獲得相當好（但不一定是最優）的解，下而我們給出一個較好的近似算法——最鄰近算法，以及一個修改的方法。

設是一個賦權完全圖，根據實際問題，我們可作如下的規定：對中任何三個頂點，滿足。

求近似最優Hamilton圈的最鄰近算法：

(1) 任選一個頂點作為起點，找一條與關聯其權最小的一條邊e₁，e₁的另一個端點記為v₁，得一條路；

(2)設已選出路，在中取一個與v_i最近的相鄰頂點，得；

(3)若，用i代i+i返回(2)，否則記，停止。

最後所得的C就是G的一個近似最優的Hamilton圈。

例如，在圖1中，粗邊表示了起點選a並用最鄰近法求得的一個Hamilton圈C=adbcea，該Hamilton圈的長度為40。

圖1 圖G的一個Hamilton圈C

用最鄰近法求得的Hamilton圈一般不是最優的，但通過以下的修改可獲得更短的Hamilton圈，其修改方法如下：

設是G的一個Hamilton圈，若存在i，j適合，並且

則Hamilton圈（它是由C中刪去邊和，添加邊和而得到的（如圖2所示））的權和

因而Hamilton圈將是C的一個改進。

圖2修改Hamilton圈的圖示圖

圖3 H-圈C=adbcea的一個修改方法

在接連進行上述的一系列修改後，最後得到的一個Hamilton圈不能再用此方法改進了，這個Hamilton圈雖然未必是最優的，但有理由認為它常常是比較好的。

例如，用最鄰近法得到的圖1所示的G的Hamilton圈為C=adbcea，用此方法修改後可得C'= acebda（見圖3），其長度為37。

我們可以利用Kruskal算法給出最優Hamilton圈下界的一個估計式，設v是賦權完全圖G的任意一個頂點，用Kruskal算法求出G-v的一棵最優樹T，設C是G的一個最優Hamilton圈，顯然C-v是G-v的一棵生成樹，因此

設G中與v關聯且權最小和權次小的兩條邊分別是e和f，則

因此將是G的最優Hamilton圈的一個下界估計式。以圖1中的G為例，G-c的圖為圖4(a)所示，用Kruskal算法求得G-c的一棵最優樹T(如圖4(b)所示），T的權為22，G中與c關聯而權最小的兩條邊為ce和西cb，因此G的最優Hamilton圈C滿足

圖4（a）

圖4（b）

由此可見，結合上面兩個方法所得到的Hamilton圈是一個較好的近似解，其實C'就是圖1所示的圖G的一個最優Hamilton圈。