從Pt。 A到地址列表

Question

我想知道在谷歌地圖中是否有可能繪製從特定地址Pt A到目的地列表 （即Pt B，Pt C，Pt D等）的最快路徑 。如果這可能是通過API可用 ？我可能需要它在我正在開發的應用程序中。

非常感謝您的歉意！

Answer 1

你可能想看看這個項目：

• Google Maps Fastest Roundtrip Solver

它可以在一個GPL許可證。

Answer 2

你所描述的問題是Traveling Salesman Problem的一個例子。這是一個着名的問題，因爲這是一個無法用任何已知算法有效解決的問題的例子。也就是說，你不能有效地提出絕對的答案，因爲可能的解決方案的數量呈指數增長。可能的解決方案的數量是n !,這意味着5 x 4 x 3 x 2 x 1，其中n = 5。在這種情況下沒有什麼大不了的，當你試圖解決5個城市（120個組合），但即使起牀只有10個，可能的連擊數量也會增加到3628800。一旦你達到100個節點，你就可以數年計算你的CPU時間。這就是爲什麼上面列出的「最快往返求解器」只能保證15點的「最優」解決方案。儘管如此，它不可能是有效地解決了，（在這種情況下，「解決方案」意味着一個正確的答案，正如Gebweb所說，「最佳」答案），但你可以想出一個相當好的答案，只要你不掛斷它是絕對可行的最好的答案。如果您查看代碼，您會注意到一旦您獲得了15分，Gebweb的「最快往返」頁面將切換到「蟻羣優化」（技術上不是算法，而是啓發式）。沒有任何意義，我重複他說的更好，看看他的behind-the-scenes page。

無論如何，丹尼爾是對的，這應該做你想做的事情，但我忍不住說了一些事實，這是一個比看起來更復雜的問題。