公共交通的數據庫設計和算法？

我們希望實施適用於Android的公共交通指南。輸入將是起點和終點。產出將是告訴我們如何使用巴士，地鐵，以及如何到達目的地的指令...... e.c 這對大城市來說並不容易，我們必須有一個設計良好的數據庫來快速回答。 Tranport算法必須爲passanger提供最佳線條。我想看看你珍貴的數據庫和算法設計的想法。非常感謝您的答覆。公共交通的數據庫設計和算法？

來源

2012-02-06 fiasco

我們希望看到你的解決問題的寶貴嘗試:) – dasblinkenlight 2012-02-06 20:11:30

首先 - 嘗試學習一些關於圖論的東西，其次 - 嘗試解決np-full「推銷員任務」8-） – 2012-02-06 20:16:31

最有可能你需要一個graph來計算最短路徑。

您的圖表將會是G=(V,E)，例如V = {all possible stations}和E = {(u,v) | there is a transport connecting station u to station v}。

如果你的圖形不能適應內存[這可能是一個大城市的情況]，你可能想要一個函數successors(u) = { v | (u,v) in E }，這將允許你在飛行中計算圖形。

在this older question有一些討論如何有效地找到一個動態環境中的兩個頂點之間的路徑類似於你正在描述的。

來源

2012-02-06 20:18:40 amit

我們沒有距離或時間，只有路線（例如：32-51-12-65-45，號碼是車站號）。我們還應該使用圖嗎？ – fiasco 2012-02-06 20:33:01

@ user1193197：即使沒有時間，使用圖表可以給你很多信息。例如，您可以在其上運行簡單的[BFS]（http://en.wikipedia.org/wiki/Breadth-first_search）以查找具有最少開關數的路徑。所以：是的，對於這些問題，我會說圖表是一個不錯的選擇。 – amit 2012-02-06 20:35:43

作爲@amit建議你應該使用圖形，因爲你沒有任何距離/時間，你可以使用'0'這些值。我要求使用'0'的原因是，將來可能爲下一個版本節省大量新的實現。 – 2012-02-06 20:46:10

公共交通的數據庫設計和算法？

回答

相關問題