公共交通的数据库设计和算法？

我们希望实施适用于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

公共交通的数据库设计和算法？

回答

相关问题