0

我实际上正在开发一个巴士票预订系统。提供商有许多路线和不同的行程。我已经建立了一个相当全面的数据库，将所有这些映射在一起，但是当我进行交叉路线预订时，我无法让路径算法正常工作。

例如，用户想从蒙特利尔到舍布鲁克，他只会走我们这里所说的 Route #47。但如果他去萨顿而不是舍布鲁克，他现在必须在某个时候转入 53 号路线。

现在，检测一个且只有一个转移并不难。但是当我谈到他可以做哪些选择来穿越多条路线时，我有点害怕。我设计了一种可爱且相对有效的方法，仅使用 SQL 在 1-3 跳上执行此操作，但我想知道我应该如何在更广泛的范围内组织所有这些，因为客户端可能不会在其余的路径中停留是生命。

到目前为止我所想到的示例：

StartingStop
joins to Route
joins to StopsOfTheRoute
joins to TransfersOnThatStop
joins to TargetStopOfThatTransfer
joins to RouteOfThatStop
joins to StopsOfThatNewRoute
[wash rince repeat for more hops]
where StopsOFThatNewRoute = EndingStop

问题是，如果我有超过 3 个跃点，我确信我的 SQL 服务器在压力下会很快窒息，即使我正确索引我的数据库，我也可以很容易地预测最终会出现重大故障......

谢谢

4

1 回答 1

1

我对您的问题的理解：您正在寻找一种算法来帮助您确定合适的路径（覆盖一条或多条路线的路段）。

正如杰森正确指出的那样，这是一个寻路问题。对于这类问题，你可能应该先看看维基百科关于寻路的文章，然后深入了解Djikstra 算法的细节。这可能会让你开始。

然而，您很可能很快就会意识到您的数据模型可能会从结构和性能的角度提出问题。典型的例子是，如果您需要管理时间限制：假设您找到多条路径，哪条路径的行程时间最短？一条路径可能最短，但每天只提供一次骑行，而另一条路径可能更长，但每天提供几次骑行。

处理此问题的一种可能方法是创建一个图表，其中每个节点对应于特定时间的特定停靠点。一条边会在房间时间内从这个站点连接到其他地理站点，以及在下一个时间点连接到它自己。

我的建议是首先阅读寻路算法，然后根据您可能遇到的任何限制重新审视您的数据模型。然后，关注存储数据的结构，以及搜索路径的结构。

建议（效率不高，但如果您有足够的 RAM 可用，则可以使用）。使用关系数据库服务器存储基本信息：停靠点、哪些路线连接到哪些停靠点等。似乎你已经涵盖了这个。然后在给定约束的情况下构建图形的内存表示。您可能会为此非常快地构建自己的库（我不知道有任何此类 PHP 库）。

另一种选择是使用图形数据库，例如Neo4j及其 REST 接口。我想这将需要对您的应用程序进行重大的重新设计。

希望这能给你一些有用的指示。

于 2012-10-16T00:29:00.210 回答