在地圖上爲一組座標創建最佳路線

Question

我有一組座標，我將從一個位置的地址中提取座標。 現在，我的任務是爲這些點生成最佳路徑。 我怎樣才能完成這項任務？我見過兩點生成路線的例子。但是當有多個目的地被覆蓋時，我無法想象它在更大的範圍內。 我正在使用此功能的Android應用程序。

Answer 1

如果您必須以特定順序訪問它們，問題可以簡化爲解決兩點的路徑：使用相鄰座標對以相同方式簡單解決問題，然後將路徑連接起來，將起點連接到終點。

如果您必須以任意順序訪問它們並優化行進距離，那麼您正在解決實際上是NP-Hard的traveling salesman problem。唯一確切的解決方案是嘗試所有排列，事實上，它與前一種情況相似，但是對於大量點而言，練習需要太多時間。首先，解決每對點的最短路徑，只保留距離以節省內存。這將需要n（n-1）/ 2次操作。接下來，使用之前計算的數據生成座標集的每個排列並計算與它們相關的路徑。具有最小距離的置換（以及與其相關的路徑）將是您的最佳序列。再次使用第一段中提到的方法生成路徑。

該算法的第一步似乎很費時，但實際上它是第二步是非多項式。有非確切的解決方案運行速度更快，但它們的可靠性各不相同。您將必須使用試驗和錯誤來決定它們是否適合您的應用程序。

Answer 2

這是一種 「尋路」 或 「路由」 問題：

http://en.wikipedia.org/wiki/Pathfinding

而且往往面臨着Dijikstra的算法：

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

或者其概括稱爲「 A *算法「：

http://en.wikipedia.org/wiki/A-star_algorithm

在最近幾年，這個東西已經演變成「收縮層次」的算法：

http://en.wikipedia.org/wiki/Contraction_hierarchies

這是更快，更高效。

這裏有幾個尋路/路由引擎。最好的一個可以說是開源路由機械：

http://project-osrm.org/

你可以多找幾個引擎在那裏。只是谷歌周圍的「地圖路由」或「尋路」。

通常，引擎是一個（RESTful）Web服務，您必須通過網絡訪問，而不是您可以嵌入到Java/Android項目中的庫。