Есть ли маршрут от города a до города b не более, чем x дней?

Question

Я был в интервью торговой фирме, мне задали этот вопрос,

Вы путешествуете по штату в автобусах, автобусы могут останавливаться в любых возможных городах C, и вам нужно найти способ отправиться из города a до города b. Есть общие автобусы B, каждый из которых путешествует между двумя городами. Все автобусы ходят на ежедневной основе, например, каждый автобус x оставляет какой-то город c1 в день d1 и прибывает в другой город b1 в другой день d2 (d2> d1). Предположим, что если вы приедете в город в день d, вы можете поймать любой автобус, покидающий город в день d или после.

Вам даны a1, b1, d1 и d2 для автобусов B. описать алгоритм, определяющий, существует ли маршрут от города a до города b не более, чем D дней, и анализировать время выполнения.

Сначала я попытался смоделировать проблему в алгоритме кратчайшего пути, но в тот момент я не мог понять, я опрокинул интервью.

Answer 1

Забавные проблемы. Вот моя попытка. Дайте мне знать, если я буду игнорировать что-то важное или если что-то в моем решении неясно.

Совет 1: Если проблема выглядит тяжело, уменьшите ее до чего-то более простого. Решите более простую проблему и посмотрите, можете ли вы обобщить решение в более трудном случае.

Давайте применим трюк здесь. Мы знаем, что автобусы проходят между двумя городами. Чтобы упростить, предположим, что если автобус отправляется из одного города в другой, мы всегда можем идти между этими двумя узлами. Так постройте неориентированный граф, где вершины - это города. Теперь есть ребро между вершинами i и j, если есть когда-либо шина, которая будет идти от i до j (так же, как переход от j к i). Теперь в этом случае проблема просто в том, что нам интересно начать с а и заканчивая на b длины < n, самый короткий путь имеет длину меньше n. Большой!

Теперь вернемся к более сложной проблеме. Мы строим два графика G_1 и G_2, G_1 представляет собой места, которые мы можем получить, учитывая, что день нечетный (например, день 1), а G_2 представляет собой места, которые мы можем получить, учитывая, что день даже пронумерован (например, день 2). Теперь оба этих графика направлены в отличие от предыдущих. Теперь мы объединим эти два графика для построения графа G. Вершины G - это просто объединение G_1 G_2. Теперь для каждого направленного ребра в G_1 обозначим начальную вершину s и конечную вершину t. Подключите вершину s в G_1 (как подграф G) к вершине t в G_2 (в качестве подграфа G). Для каждого направленного ребра в G_2 обозначим начальную вершину s и конечную вершину t. Соедините вершину s в G_2 (как подграф G) с вершиной t в G_1 (как подграф G). Все направленные ребра в G имеют вес 1. Теперь проблема в том, что существует просто кратчайший путь в G длины < n.

Идея состоит в том, чтобы наложить два графика G_1 на вершину G_2, чтобы мы учитывали, что маршруты изменяются на четные и нечетные дни.

Answer 2

Вот пример в Haskell с реальными медленными автобусами, строительство маршрута из пункта назначения обратно происхождения:

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 3

Я думал, что если бы вы дали день, чтобы начать с (что, кажется, не так), его следует легко применить Dijkstra's algorithm.

Тривиально создавать график проблемы. Каждый узел является городом, каждая из которых является направленным фронтом от одного узла к другому. Вес ребра на самом деле не определен вообще (мы не можем просто взять время поездки) и будет определяться при его обработке.

Таким образом, свести задачу к несколько подзадаче, где вы знаете, начало день следующим образом:

Из а имеется к автобусам в другие города. Таким образом, автобус b _i переходит от a к b _i с начала дня _i до конца дня i. Для каждой из этих автобусов создайте подзадачу, начиная с b _i на конец дня _i (и не забудьте начать _i).

Для Алгоритм Дейкстры дал стартовый день и город:

При изучении графика, мы должны следить за текущий день.

При создании соседей в городе c1 от дня d1, для каждого города c2, где находится автобус от с1 до с2, мы генерируем раннего автобуса от с1 до с2 (где отбывают в c1> = текущий день) (если автобусы могут принимать разные количества дней, чтобы добраться от c1 до c2, считайте, что самые ранние прибыли при c2). Значение c2 будет просто числом дней с исходного начального дня (начало _i сверху) до того дня, когда автобус достигнет c2.

Оптимизация:

Вам не нужно делать полный пробег Дейкстров на каждую подзадаче, если вы приехали в городе в определенный день, любая следующая подзадача, который прибывает в этом городе на в тот же день будет идти один и тот же путь оттуда. Выполнение их в одно и то же время не должно быть слишком сложным и должно приводить к повышению производительности, чем к ним по одному.

Можно использовать эвристическую функцию, чтобы иметь возможность применять A*.

Не стесняйтесь указать, пропустил ли я что-то.

Answer 4

Существует другой способ, который вы найдете упомянутым сейчас и затем. Он основан на матрице, которая определяет возможные переходы между городами. Предположим, что матрица равна M, тогда M [i, j] равно 1, если есть дорога из города j в город i, иначе 0. Начиная с единичного вектора для стартового города и умножая этот вектор с матрицей перехода, вы получит вектор со значением больше нуля во всех городах, который может быть достигнут за один шаг. Вы повторяете этот шаг за запрошенное количество дней.

При моделировании вашего случая проблема в том, что у вас есть взвешенный график, т. Е. Не каждый переход занимает одно и то же время. Однако эта стоимость является целым числом, поэтому вы можете ввести искусственные остановки (то есть вершины) в маршрутах, которые занимают больше одного дня, чтобы моделировать это. Тогда вы получите невзвешенный график. Кроме того, вы можете предположить из вопроса, что вес низкий, поэтому он, вероятно, не вызывает больших накладных расходов.

Поскольку матричное умножение является ассоциативным, вы можете умножить матрицу на себя несколько раз, прежде чем подавать ей начальный вектор. Поскольку фактические значения не представляют интереса, только то, являются ли они 0 или 1, вы могли бы дополнительно уменьшить это и эффективно битовать матрицу. Кроме того, вы можете вычислить MxMxMxM как (MxM) x (MxM), чтобы уменьшить накладные расходы. Затем также есть некоторые оптимизации для матричного умножения (Strassen Algorithm, IIRC), которые можно собрать.

Примечание: Я знаю, что это описание немного отрывочно, просто напишите мне, и я попытаюсь его прояснить.