是否有不超过 x 天从 a 城市到 b 城市的路线? [英] is there is a route from city a to city b in no more than x days?

问题描述

我在一家贸易公司面试时，被问到这个问题，

I was in a trading firm interview, I was asked this question,

您乘坐公共汽车穿越州，公共汽车可以停在任何 C 个可能的城市，您需要找到从城市 a 到城市 b 的方法.共有 B 辆巴士，每辆巴士都在两个城市之间行驶.所有公交车都以每日为基础运行，例如每辆公交车 x 在第 d1 天离开某个城市 c1，并在另一天 d2(d2>d1)到达另一个城市 b1.假设如果您在 d 天到达一个城市，您可以搭乘任何在 d 天或之后离开该城市的巴士.

you are travelling accross the state in a buses, the buses can stop at any C possible cities and you need to find a way to go from city a to city b. There are total B buses, each of which travels between two cities. All buses travel on a daily bases, for example each bus x leaves some city c1 on day d1 and arrives at another city b1 on another day d2 (d2>d1). Assume that if you arrive at a city on day d, you can catch any bus leaving the city on day d or after.

您将获得 B 总线的 a1、b1、d1 和 d2.描述一个算法，判断是否存在不超过D天从a城市到b城市的路线，并分析运行时间.

you are given a1, b1,d1, and d2 for B buses. describe an algorithm that determines whether there exist a route from city a to city b in no more than D days, and analyze the run time.

我最初尝试将问题建模为最短路径算法，但当时我无法弄清楚，我搞砸了面试.

I was initially try to model the problem in to shortest path algorithm but I could not figure out at that moment, I screwed the interview.

推荐答案

我想如果给你一天开始的时间(似乎不是这样)，应该很容易申请 Dijkstra 算法.

I thought if you were given a day to start from (which doesn't seem to be the case), it should be easy to apply Dijkstra's algorithm.

为问题创建图表很简单.每个节点都是一个城市，每辆公交车都是从一个节点到另一个节点的有向边.一条边的权重在一般情况下并没有真正定义(我们不能只取行程时间)，将在我们处理它时确定.

It's trivial to create a graph for the problem. Each node is a city, each bus is a directed edge from one node to another. The weight of an edge isn't really defined in general (we can't just take the trip time) and will be determined when we process it.

因此，将问题简化为您知道开始日期的多个子问题，如下所示:

从 a 有 k 辆公共汽车到其他城市.所以总线 b_i 从 a 到 b_i 从开始_i 到结束_i.对于这些总线中的每一个，创建一个从 b_i 在 day end_i 开始的子问题(记住 start_i).

From a there are k busses to other cities. So bus b_i goes from a to b_i from day start_i to day end_i. For each of these busses, create a sub-problem starting from b_i on day end_i (and remember start_i).

在给定起始日期和城市的情况下做 Dijkstra:

在浏览图表时，我们需要跟踪当天.

When exploring the graph, we need to keep track of the current day.

当从第 d1 天开始在城市 c1 生成邻居时，对于每个城市 c2，其中有从 c1 到 c2 的巴士，我们生成从 c1 到 c2(从 c1 出发)最早的巴士= 当天)(如果公交车从 c1 到 c2 需要不同的天数，请考虑最早到达 c2).c2 的值只是从原始开始日期(上面的 start_i)到巴士到达 c2 的天数.

When generating neighbors at a city c1 from day d1, for each city c2 where there is a bus from c1 to c2, we generate the earliest bus from c1 to c2 (where depart at c1 >= the current day) (if busses can take different amounts of days to get from c1 to c2, consider the earliest arrive at c2). The value of c2 would simply be the number of days from the original starting day (start_i from above) to the day the bus arrives at c2.

优化:

您不需要对每个子问题进行 完整 次 Dijkstra 运行，如果您在某一天到达一个城市，那么在同一天到达该城市的任何下一个子问题都会从那里开始有相同的路径.同时执行所有这些操作应该不会太难，而且应该比一次执行一个操作会产生更好的性能.

You don't need to do a complete run of Dijkstra on each subproblem, if you arrived at a city on a certain day, any next subproblem that arrives at that city on the same day would have the same path from there onward. Doing them all at the same time shouldn't be too difficult and should result in better performance than doing them one at a time.

人们可以想出一个启发式函数来应用A*.

One may be able to come up with a heuristic function to be able to apply A*.

如果我遗漏了什么，请随时指出.

Feel free to point out if I missed something.

这篇关于是否有不超过 x 天从 a 城市到 b 城市的路线?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！