Traveling Salesman Problem (TSP)
72500 公里長征 ?!
剛剛看到一篇文章，提到在 2004 年 5 月的時候，有人拿瑞典的 24978 個城鎮的資料來跑 TSP (這裡有另一個解釋；簡單說，就是如果要你全國走透透，但是規定你一個地方只能去一次，而且最後還要回到原出發地，你要怎麼走才是最短路徑 ? 這是一個 NP-Complete 的問題…)，然後找出了一個長達 72500 公里的路線圖…
然後呢，這傢伙看了覺得很有趣，就寫了一個產生器；你可以用 Google Earth 產生一個包含最多 9 個點的 KML 檔 (超過 10 個點的話速度會慢到無法接受…)，丟給它以後，它會吐回一個 KML 檔，打開以後就是你所指示的那些點的 TSP 問題的解了 :p 這當然只是好玩的啦，因為他算的距離是照 大圓線
去算的，並不是照真的路去走；不過這倒是一個有趣的課題，以後不知道會不會有 GPS 導航系統新增這種功能 ? 你只要指定說要去哪幾個定點玩，它就會自動算出開車路線圖，你就照著跑，最後安全回家 :Q
Comments
Comment from Blair
Date: 2006/08/28, 9:05 上午
原來現在還沒有這功能喔? 去年過年出去玩拿到一台PDA+GPS就一直在找這功能說…這麼重要的功能怎麼沒人實做出來勒?
Write a comment