旅行商問題

     旅行商問題（Traveling Saleman Problem，TSP）又譯為旅行推銷員問題、貨郎擔問題，簡稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點出發，通過所有給定的需求點之後，最後再回到原點的最小路徑成本。最早的旅行商問題的數學規劃是由Dantzig（1959）等人提出。

問題描述

由n個城市組成的網絡，編号為V1,V2,....,Vn, Dij 表示Vi到Vj的距離(或時間，費用等)，一般Dij ≠ Dji，一個推銷員從V1開始，通路每個城市一次且僅一次，然後傳回V1。這個推銷員如何選擇線路，才能使行程最短？

問題抽象

一個有向圖G(V,E)，從某個頂點出發，經過每個結點一次且僅一次，傳回出發結點。對于任意Vi,Vj ∈ V , 存在Eij和Eji，0 < Eij < ∞ ，0 < Eji < ∞，如果沒有此條件，問題有可能無解，也就是說，此圖是一個有向完全圖。

問題求解

(1)枚舉法

相當于對V1,V2,V3,....,Vn做圓周排列，圓周排列為n!/n = (n-1)!，也即有(n-1)!條路徑，需要(n-1)(n-1)!次加法，(n-1)!-1次比較。

(2)動态規劃

令f(Vi ; V)表示結點從結點Vi出發，周遊V中的點一次且僅一次，然後傳回V1的最短距離，其中V是某些結點構成的集合，且V1,Vi  V。

多段判決公式： f(Vi ; V ) = min { Dij + f(Vj ; V\{Vj} }  (Vj ∈ V)

是以問題就成了求 f(V1 ; { V2,V3,V4,...,Vn} } 的最小值

本文轉自nxlhero 51CTO部落格，原文連結：http://blog.51cto.com/nxlhero/696905，如需轉載請自行聯系原作者