我在一家贸易公司的采访中，有人问我这个问题，

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

您旅行防空火炮的状态在公交车，公交车可以停在任何C可能的城市，你需要找到一种方法，从城市到走至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.

正在给出A1，B1，d1和d2是乙总线。描述了一种算法，确定是否存在从城市的路线，以B市不超过d天，并分析运行时间。

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.

因此​​，问题缩小到多个子问题，你知道开始日，如下：

这是一个有k个公共汽车到其他城市。因此，总线B 我从进入B 我从第一天开始我一天结束我。对于这些总线的，创建一个子问题，从B 我在日终 i开始（记住启动我）

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

要做到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的值，简直是从原来的出发日的天数（启动我从上面）的公交车到达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 (starti 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.