2

我正在为我的一些工作寻求一些帮助。

任务是创建一个伦敦地铁旅程规划器。

编辑：-

目前我有一个哈希表中带有边缘数据的节点的邻接列表。

我想找到一种方法来使用广度优先搜索来获得任意两个顶点之间的最短路径。

顶点按照管图的外观进行逻辑连接。每个车站的边缘都使用： (this_station, next_station, tube_line) <- 这是我对每个车站的信息。

遍历这个非常棘手。任何帮助都非常感谢！

4

4 回答 4

3

正如Brian 暗示的那样，您需要一个加权图 - 每条边上的权重应该是火车在两端车站之间行驶的时间。然而，这还不够：您还需要考虑火车在站台上停留的时间、在车站不同线路的站台之间行走所花费的时间，以及您在到达站台后等待火车所花费的时间。平台。

令人高兴的是，您可以在加权有向图的框架内执行此操作。您只需要将每个站点表示为一个小的子图。以芬斯伯里公园（Finsbury Park）为例，它是整个网络乃至整个宇宙的中心，您将拥有以下节点：

  1. 车站入口（一共有三个，但你只能选一个）
  2. 一名乘客站在维多利亚线南行月台上
  3. 列车抵达维多利亚线南行月台
  4. 列车从维多利亚线南行月台发车
  5. 其他三个平台的节点 2-4 的等效项

然后你在它们之间有边缘：

  1. 从入口到站在每个平台上，根据在它们之间行走的时间加权
  2. 从每个平台回到入口，以相同的方式加权（这可能是同一时间，所以你可以让这个边缘双向）
  3. 从火车到达站台，重量为零（因为下火车不需要时间）
  4. 在每对平台之间，重量等于在它们之间行走的时间
  5. 从站台到火车出发，重量等于连续火车之间间隔的一半（因为如果您在随机时间到达站台，那是您必须等待火车的平均时间）
  6. 从火车到站到火车在同一个站台发车，重量等于停留时间（只要小于半间隔，否则每站换车会更快！）

然后，您将每个出发节点连接到该线路下一个车站的到达节点。

要规划从 A 到 B 的路线，您需要在车站入口的节点之间找到一条路径。该路线不仅包括在火车上花费的时间，还包括它们之间的变化。对于许多车站，您可以将许多停留和换乘时间视为零，但对于某些车站来说，它们很重要：例如，在 Green Park 的 Victoria 和 Piccadilly 线之间转换，或者在 Aldgate 的 Circle 线上的停留时间. 你应该考虑这些，否则你会为短途旅行制定错误的计划。你肯定也需要考虑频率 - 它在以环线为特色的计划和中央线之间产生显着差异, 只有一个。

这种方法仍然没有考虑的一件事是分支之间的频率分裂方式。例如，您可以将在 Tufnell 公园等待北行火车的时间建模为在高峰期需要 1.5 分钟，但如果您要去 Mill Hill East，您可能需要等待更长时间，因为大多数火车将开往 Barnet。您可能需要在 Finchley Central - Mill Hill East 边缘添加一些时间来解决此问题，但我不确定这通常适用的程度如何。

至于搜索算法，Dijkstra 算法可以，但A*将是经典选项。

于 2011-01-04T22:19:45.350 回答
3

这是一个经典的图论问题。您可以将停靠点表示为节点，将停靠点之间的连接表示为边。

为了直接回答您的问题，我相信将线段表示为一条线的最佳方法是制作一个代表所有线的图表。您可以使用数据标志（或一组标志）标记边缘，以表示节点属于哪条线。最终，无论线路、车站和路段如何，这都是一个图表。如果您对表示这些概念感兴趣，我建议将它们存储为节点（或边）的属性。

如果您对移除这些边缘感兴趣，您可以迭代地移除纯粹中间的边缘。因此，如果 A->B->C，并且 B 没有其他连接，则可以删除 B 并将其 B->C 权重添加到 A->C 权重中。

使用图形表示将允许您将现有的最短路径算法应用于您的问题。

祝你好运！

-Brian J. Stinar-

于 2011-01-04T21:20:24.433 回答
2

一种选择是将问题表示为图形问题，并针对最短路径应用成本优化来解决问题的旅程规划器方面。一种常见的选择是应用Dijkstra。引用维基百科的定义：

对于图中的给定源顶点（节点），该算法会找到该顶点与所有其他顶点之间成本最低的路径（即最短路径）。一旦确定了到目标顶点的最短路径，它也可以用于通过停止算法来查找从单个顶点到单个目标顶点的最短路径的成本。

对于 Java，您可以在此处和此处找到一些有趣的注释

Dijkstra 的改进算法是性能更好的 A*。这里有一个实现它的项目。

于 2011-01-04T22:07:49.423 回答
1

这确实是一个单独的问题，所以我会尝试给你一个单独的答案。

我认为您选择散列的内部表示可能会让您感到困惑。您应该仍然可以使用散列来使事情正常工作，但是如果您查看Wikipedia上的伪代码 ，您会注意到队列正在用于邻接列表。我还尝试将邻接列表视为此应用程序的队列。这使得获取每个节点的邻接列表变得更加直接，这是您想要在广度优先搜索下操作的内容。然后，如果您想将其更改为堆栈，您将获得超级、超级轻松的深度优先搜索。在我看来，您似乎已经阅读过该算法，并且您具有一般的软件开发能力。在我看来，如果我处于您的境地，这会让我绊倒，但它可能是任何数量的事情。

祝你好运！

-Brian J. Stinar-

于 2011-01-10T17:42:58.520 回答