[算法]巡回售貨員問題

blackuhlan

今天在看時間復雜度的時候看見有個據(jù)說是著名的巡回售貨員問題，據(jù)說目前的算法都是指數(shù)級的，我隨便想了想，搞了個算法，當然紕漏可能是大大的存在。各位牛哥、牛姐、牛弟、牛妹給拍拍磚，俺們討論討論。
1.將所有路徑倒排序。
2.嘗試刪除長度最大的路徑，如果有同樣長度路徑（按順序嘗試）。
2.1 如果要刪除的路徑的兩個端點中有一個的路徑數(shù)小于2，返回不允許刪除。
2.2 如果刪除該路徑后，圖中還存在哈密爾頓路徑（即回路），返回允許刪除。否則返回不允許刪除。
簡單吧。拍磚歡迎，證明的沒想到。

blackuhlan

再給介紹點背景資料吧：
巡回售貨員問題也稱為貨郎擔問題。有一個售貨員，從他所在城市出發(fā)去訪問n-1個城市，要求經(jīng)過每個城市恰好一次，然后返回原地，問他的旅行路線怎樣安排才最經(jīng)濟（即線路最短）？就是求最短的哈密爾頓路徑。
如果將所有城市以及所有路徑用圖表示出來就是賦值完全圖。每個城市作為節(jié)點，每兩個城市之間的路線長度作為賦值路徑（任意兩個城市之間都有路徑）。

blackuhlan

怎么沒人給提提意見，牛都不知道跑哪去吃草去了嗎？

blackuhlan

唉，牛兒還在山坡吃草，晚上再來看看吧

haohao06

貪心法么?
我舉個反例不知道對不對
ab=6,bc=1,cd=1,da=1,ac=5,bd=5.
這樣最短是abcda=9,
如果用你的算法豈不是第一次就把ab刪除了.

blackuhlan

原帖由 haohao06 于 2009-6-3 17:00 發(fā)表
貪心法么?
我舉個反例不知道對不對
ab=6,bc=1,cd=1,da=1,ac=5,bd=5.
這樣最短是abcda=9,
如果用你的算法豈不是第一次就把ab刪除了.

謝謝這位兄的，我再想想，想好了再卷土重來