Алгоритм для расписаний рейсов

Question

У меня есть список всех прямых рейсов. Из этого я хочу получить рейсы из А в Б с пересадками. Каков будет подходящий алгоритм или структура данных для этой проблемы? Спасибо.

Answer 1

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

Answer 2

Файл прямых рейсов дает график. Узлы являются аэропортами. Края находятся между аэропортами, которые имеют прямые рейсы, и говорят, что каждый край имеет вес на нем. Вы хотите найти все простые пути между A и B и, вероятно, хотели бы получить набор путей. Вы можете просто выполнить поиск в глубине графика.

Пара общих способов кодирования графа - это список смежности (т. Е. Для каждого узла - список узлов, для которых существует ребро); или матрица NxN (для N узлов), значение в местоположении (i, j) сообщает вам стоимость границы между узлом i и узлом j.

Учитывая эту структуру данных. Вы можете использовать поиск в глубину, начиная с узла A и заканчивая на узле B. Вы должны убедиться, что алгоритм не пересматривает узлы, которые уже находятся на текущем пути, чтобы предотвратить циклы.

Answer 3

Классическая задача Проблема кратчайшего пути . Если вы смотрите на алгоритмы, на странице Википедии есть несколько параметров, в качестве альтернативы есть такие алгоритмы, как ACO , но есть варианты, но это зависит от варианта использования и способа предоставления решения.

Для ясности обратите внимание, что это вариант задачи коммивояжера , в результате NP-complete .