Is there a route from city a to city b in no more than x days?

Question

I was in an interview with a trading company, I was asked this question,

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

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

At first I tried to model the problem in the shortest path algorithm, but at that moment I could not understand, I screwed up the interview.

Answer 1

I thought that if you are given a day to start (which seems to be wrong), it should be easy to apply Dijkstra's algorithm .

It is trivial to create a schedule for the problem. Each node is a city, each of which is a directional edge from one node to another. The weight of the rib is not really determined at all (we cannot just take the trip time) and will be determined during its processing.

So, reduce the problem to a few sub-problems where you know the starting day , as follows:

From a there are k buses to other cities. Thus, bus b _i goes from a to b _i from the beginning of day _i to the end of day _i . For each of these tires, create a sub-problem starting at b _i at the end of day _i (and remember start _i ).

To do Dijkstra, considering the starting day and the city:

When studying the schedule, we need to track the current day.

When creating neighbors in 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 you leave from c1> = the current day) (if buses can take different numbers of days, to get from c1 to c2, consider that the earliest arrived at c2). The value of c2 will simply be the number of days from the original start day (beginning _i from above) to the day when the bus arrives from c2.

Optimization:

You don’t need to do a full Dijkstra run for each subtask, if you arrived in the city on a specific day, any next subtask that arrives in this city on the same day will have the same path from there, Performing them at the same time will not should be too complex and should lead to increased productivity than to them one at a time.

You can create a heuristic function to be able to use A * .

Feel free to indicate if I missed something.

Answer 2

An interesting problem. Here is my attempt. Let me know if I ignore something important or if something in my decision is unclear.

Tip 1: If the problem looks complicated, reduce it to something simpler. Solve a simpler problem and see if you can generalize the solution in a more difficult case.

Now apply the trick. We know that buses pass between two cities. To simplify, suppose that if a bus leaves from one city to another, we can always go between these two nodes. So build an undirected graph where the peaks are cities. Now there is an edge between the vertices i and j, if there is ever a bus that will go from i to j (just like the transition from j to i). Now in this case the problem is simply that we are interested in starting with a and ending with b of length <n, the shortest path has a length of less than n. Excellent!

Now back to a more complex problem. We plot two graphs G_1 and G_2, G_1 represents the places we can get, given that the day is odd (for example, day 1), and G_2 represents the places we can get, given that the day is even numbered (for example, day 2). Now both of these graphs are directed, unlike the previous ones. Now we combine these two graphs to build the graph G. The vertices of G are just the union of G_1 G_2. Now for each directed edge in G_1 we denote the initial vertex s and the final vertex t. Connect the vertex s in G_1 (as a subgraph G) to the vertex t in G_2 (as a subgraph G). For each directed edge in G_2, we denote the initial vertex s and the final vertex t. Connect the vertex s in G_2 (as a subgraph of G) with the vertex t in G_1 (as a subgraph of G). All directed edges in G have weight 1. Now the problem is that there simply exists a shortest path in G of length <n.

The idea is to overlay two G_1 graphs on top of G_2 so that we take into account that the routes change on even and odd days.

Answer 3

Here is an example in Haskell with real slow buses, building routes from destination to source:

import Data.List (elemIndex) import Data.Maybe (fromJust) cities = ["New York", "Philadelphia", "Washington", "Buffalo"] buses = [([0,1],2), ([0,2],1), ([1,2],1), ([2,3],4)] --buses (cities a1 b1 as indexes, num days of travel) solve origin destination maxDays = do lastBus <- filter ((== fromJust (elemIndex destination cities)) . last . fst) buses solve' [lastBus] where solve' result | sum (map snd result) > maxDays = [] | cities !! (head . fst . head $ result) == origin = [(map (map (cities !!) . fst) result, show (sum . map snd $ result) ++ " Days Travel")] | otherwise = let potentialBuses = filter ((== (head . fst . head $ result)) . last . fst) buses in if null potentialBuses then [] else do bus <- potentialBuses solve' (bus:result) OUTPUT: *Main> solve "New York" "Buffalo" 6 [([["New York","Washington"],["Washington","Buffalo"]],"5 Days Travel")] *Main> solve "New York" "Buffalo" 3 [] --trip longer than D *Main> solve "New York" "Washington" 3 [([["New York","Washington"]],"1 Days Travel"), ([["New York","Philadelphia"],["Philadelphia","Washington"]],"3 Days Travel")] 

Answer 4

There is another method that you will find now and later. It is based on a matrix that determines the possible transitions between cities. Suppose that the matrix is ​​M, then M [i, j] is 1, if there is a road from city j to city i, otherwise 0. Starting from the unit vector for the starting city and multiplying this vector with the transition matrix, you will get a vector with the value more than zero in all cities, which can be achieved in one step. You repeat this step for the requested number of days.

When modeling your case, the problem is that you have a balanced schedule, i.e. not every transition takes the same time. However, this cost is an integer, so you can introduce artificial stops (i.e. peaks) in routes that take more than one day to simulate. Then you get an unweighted schedule. In addition, you can assume from the question that the weight is low, so it probably does not cause a lot of overhead.

Since matrix multiplication is associative, you can multiply the matrix by yourself several times before applying the initial vector to it. Since the actual values ​​are not of interest, only whether they are 0 or 1, you could further reduce this and effectively beat the matrix. In addition, you can calculate MxMxMxM as (MxM) x (MxM) to reduce overhead. Then there are also some optimizations for matrix multiplication (Strassen Algorithm, IIRC) that can be compiled.

Note. I know this description is a bit sketchy, just write to me and I will try to clarify it.