18

If you have the full bus schedule for a country, how can you find the furthest anyone can travel in one day without visiting the same stop twice?

I assume a bus schedule gives you the full list of leaving and arriving times for every bus stop.

A slow and naive method would be as follows.

You can of course make a graph from the bus schedule with multiple directed edges between bus stops. You could then do a depth first search remembering the arrival time of the edge you took to get to each node and only taking edges from that stop that leave after the one that you took to get there. If you go to a node you have been to before you would only carry on from there if the current time in your traversal is before the earliest time you had ever visited that node before. You could record the furthest you can get from each node and then you could check each node to find the furthest you can travel overall.

This seems very inefficient however and it really isn't a normal graph problem. The problem is that in a normal directed graph if you can get from A to B and from B to C then you can get from A to C. This isn't true here.

What is the fastest you can solve this problem?

4

5 回答 5

8

我认为您的原始算法非常好。

您可以将您的方法视为Dijkstra 算法的一个版本，试图找到到每个节点的最短路径。

请注意，最好在此阶段根据时间对图中的边进行加权。这个想法是使用类似 Dijkstra 的算法来计算在 1 天内可到达的所有节点，然后选择这些节点中距离起点最远的节点。

Dijkstra 的实现可以使用堆来检索下一个要在 O(logn) 中探索的节点，我认为这对您的方法也是一个很好的增强。如果您始终选择最早可以到达的节点，则无需为该节点重复计算。

总的来说，方法是：

  1. 对于每个起点
  2. 使用修改后的 Dijkstra 计算 1 天内可到达的所有节点
  3. 找到所有这些节点中最远的空间。

所以对于n个起点和e条公交路线，复杂度约为O(n(n+e)log(n))才能得到最优答案。

您应该能够通过在A* 搜索中使用适当的启发式来提高性能。启发式需要低估到一个点的最大可能距离，因此您可以使用总线的最大速度乘以剩余时间。

于 2013-07-08T19:00:05.223 回答
4

您可以在每个位置/时间创建多个节点，而不是为每次离开一个位置创建多个边。

  1. 每个出发时间每个位置创建一个节点。
  2. 每个到达时间每个位置创建一个节点。
  3. 创建边以连接出发地和到达地。
  4. 创建边以在最近的未来时间将给定节点连接到属于同一位置的节点。

通过这样做，您可以通过图表遍历的任何路径都是“有效的”（这意味着旅行者将能够通过公共汽车旅行的组合或选择坐在某个位置并等待未来的公共汽车来实现这一点）。

于 2013-07-08T19:32:03.560 回答
2

简单的图形表示将不起作用。IE。每个城市都是一个节点，边代表时间。那是因为“边缘”并不总是活跃的——它只在一天中的特定时间活跃。

想到的第二件事是 Edward Tufte 的巴黎火车时刻表巴黎火车时刻表，这是一种不同的图表。但这也不太适合这个问题。对于火车时刻表，车站之间具有顺序关系，但对于城市和公共汽车时刻表，情况通常并非如此。

但是 Tufte 鼓励采用以下方式将其建模为图形。您可以仅编写代码来构建图形并使用包含最短路径算法的标准图形库。

  • 每趟巴士都是一条边，权重 = 覆盖距离
  • 每个（城市，出发）和（城市，到达）都是一个节点
  • 给定城市的所有节点都由零权重边按时间顺序连接，忽略它是到达还是离开。这个子图看起来像一个链。
  • （这是一个有向图）

线性时间解决方案：请注意，该图将是一个有向无环图。在这样的图中找到最长的路径是线性的。“加权图 G 中两个给定顶点 s 和 t 之间的最长路径与图中的最短路径相同 - G 通过将每个权重更改为否定来从 G 派生。因此，如果可以在 - G，那么最长的路径也可以在 G 中找到。”

希望这可以帮助！如果有人可以发布图表的可视化，那就太好了。如果我自己可以这样做，我会再做 1 次编辑。

于 2013-07-08T18:35:51.523 回答
2

很抱歉，但正如所描述的，这个问题具有相当高的复杂性。最初误读了这个问题，并认为它是 np-hard，但事实并非如此。然而，它确实具有我个人不想处理的相当高的复杂性。这个算法是一个非常好的近似值，可以节省相当多的复杂度，我个人认为这是值得的。

然而，如果你想要的只是一个“相当不错”的答案，那么有很多相当有效的算法会很快接近。

我个人建议在这里使用一个简单的贪心算法。

我已经在几个（公认的、小型的和人为的）示例上做到了这一点，它工作得很好并且nlog(n)效率很高。

  • 将 avelocity与每个节点相关联，速度是您可以离开给定节点的最快速度。在我的例子中，这个速度是distance_travelled/(wait_time + travel_time)。我使用离开节点的所有行程的最大速度作为该节点的速度分数。
  • 从您的节点/时间计算所有相邻节点的速度并移动到“最快”节点。

该算法非常适合复杂性，因为它基本上将问题转换为静态搜索，但有几个潜在的陷阱可以根据您的数据集进行调整。

这个算法最大的问题是一辆非常快的公共汽车可能会进入偏僻的地方。您可以通过在速度计算中添加“流行度”术语来解决这个问题（使更流行的站点更有效地更快），但取决于您的数据集，这很容易使事情变得更好或更糟。

于 2013-07-08T18:47:33.287 回答
-1

天真是你会得到的最好的——http: //en.wikipedia.org/wiki/Longest_path_problem

编辑：

所以问题是两方面的。

  1. 创建一个可以从 A 点移动到 B 点的图表列表。可能是根据公共汽车A从A点到B点的可用时间。

  2. 从上面所有可能的生成路径中找到最长的路径。

另一种方法是在每个节点遍历时重新评估图并找到最长的路径。它仍然简化为寻找最长的可能路径，即 NP-Hard。

于 2013-07-08T18:38:21.103 回答