乘公共汽车旅行

Question

如果你有一个国家的完整公交时刻表,你怎么能找到最远的人可以在一天内旅行而不会两次访问同一站点？

我假设一个公共汽车时刻表为您提供每个公共​​汽车站的离开和到达时间的完整列表.

一种缓慢而天真的方法如下.

您当然可以根据公交车时刻表制作一个图表,并在公交车站之间设置多个有向边.然后,您可以进行深度优先搜索,记住您到达每个节点所花费的边缘的到达时间,并且仅在您到达那里之后离开该止挡的边缘.如果你去过一个你曾经去过的节点,那么如果你的遍历中的当前时间是你之前访问过该节点的最早时间之前,那么你只能从那里继续.您可以记录每个节点可以获得的最远距离,然后您可以检查每个节点以找到您可以整体旅行的最远距离.

然而,这似乎非常低效,并且它实际上不是正常的图形问题.问题是在正常的有向图中,如果你可以从A到B,从B到C,那么你可以从A到C.这里不是这样.

你能解决这个问题最快的是什么？

Answer 1

我认为你原来的算法非常好.

在尝试找到每个节点的最短路径时,您可以将您的方法视为Dijkstra算法的一个版本.

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

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

总的来说,方法是:

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

因此对于n个起点和e总线路径,复杂度约为O(n(n + e)log(n))以获得最佳答案.

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