Разбор: самый ранний приезд по расписанию

Если ты знаешь, почему кратчайший путь по длительностям не годится для расписаний, и что такое просмотр соединений, листай до «Теперь сам».

Как думаешь, когда приедешь

Из A в C на метро 20 минут, из C в E на трамвае 5, из E в D на маршрутке 7. Выезжаешь в 8:00. Когда будешь в D?

Ответь себе до чтения. Сумма длительностей - 32 минуты, «в 8:32». Но метро уходит в 8:05, трамвай - в 8:28, маршрутка - в 8:35: на каждой пересадке ждёшь, и приезжаешь в 8:42. А если выйти из дома в 8:06, утреннее метро уже ушло, следующее - в 8:45, и до D в этот день не добраться вовсе. Длительности знают о поездках, но не знают о времени.

На что это похоже

Пересадка в аэропорту. Перелёт в Москву два часа, из Москвы в Казань - полтора: «три с половиной часа в пути». Но второй рейс вылетает через пять часов после посадки первого, а если первый опоздал - завтра утром. Время в пути определяют не длительности перелётов, а то, на какой рейс ты успеваешь.

Механизм: от просьбы к модели

Вход - расписание: каждый рейс делится на соединения - отрезки «станция отправления, станция прибытия, время отправления, время прибытия». Вид ответа - лучший маршрут; что значит «лучше» - раньше приехать, или меньше пересадок, или и то и другое (второй разбор). Размер - у большого города миллионы соединений в сутки, а ответ нужен за доли секунды. Уложится ли в это алгоритм, проверяют замером на своём расписании: оценка O(m) говорит о росте, а не о секундах.

Модель с длительностями превращает расписание в граф, где ребро A → C весит 20 минут. Она отбрасывает главное - когда ребро «существует». Эту ошибку видно на маленьком примере, поэтому её и надо сделать до кода.

Просмотр соединений (Connection Scan, Диббельт, Пайор, Штрассер, Вагнер, 2013) работает прямо со списком. Соединения один раз сортируются по времени отправления. Для каждой станции хранится самое раннее известное время прибытия; в начале известно только «в A в момент выезда». Проход по списку: если на станцию отправления соединения успеваем к его отправлению, оно может улучшить время прибытия на свою станцию прибытия. Порядок по отправлению гарантирует, что к моменту рассмотрения соединения все способы успеть на него уже учтены: всё, что могло привезти на его станцию раньше, отправилось раньше.

Правило

Если ребро графа доступно только в определённые моменты, модель «граф с весами-длительностями» неверна. Для расписаний модель - список соединений, отсортированный по отправлению, и один проход по нему даёт самое раннее прибытие на все станции. Если критериев несколько, ответ - множество маршрутов, ни один из которых не хуже другого по всем критериям сразу.

Разбор: просмотр соединений против графа длительностей

Пять станций, шесть рейсов, восемь соединений: автобус 12 идёт тремя перегонами. Время - минуты после 8:00.

# соединения: [откуда, куда, отправление, прибытие, рейс]; рейс - один
# конкретный рейс, а не вид транспорта; время - минуты после 8:00
soedineniya = [
    ["A", "B", 0, 15, "автобус 12"], ["B", "C", 15, 40, "автобус 12"],
    ["C", "D", 40, 90, "автобус 12"], ["B", "D", 20, 50, "электричка"],
    ["A", "C", 5, 25, "метро 8:05"], ["C", "E", 28, 33, "трамвай 3"],
    ["E", "D", 35, 42, "маршрутка 41"], ["A", "C", 45, 65, "метро 8:45"],
]

def vremya(m):
    return str(8 + m // 60) + ":" + str(m % 60 // 10) + str(m % 10)

def po_otpravleniyu(c):
    return c[2]

# сортировка - один раз, до всех запросов
po_vremeni = sorted(soedineniya, key=po_otpravleniyu)

def skan(start, t0):
    # просмотр соединений по времени отправления: если на станцию
    # отправления успеваем, соединение улучшает прибытие туда, куда едет;
    # privez[станция] - соединение, которое привезло туда раньше всех
    rano = {}
    privez = {}
    rano[start] = t0
    for c in po_vremeni:
        if c[0] in rano and rano[c[0]] <= c[2]:
            if c[1] not in rano or c[3] < rano[c[1]]:
                rano[c[1]] = c[3]
                privez[c[1]] = c
    return [rano, privez]

def marshrut(privez, start, cel):
    # от цели назад по соединениям, которые привезли раньше всех
    put = []
    st = cel
    while st != start:
        c = privez[st]
        put = [c[4] + " " + c[0] + "->" + c[1]] + put
        st = c[0]
    return put

def po_dlitelnostyam(start):
    # модель «граф с длительностями»: ребро - самая короткая поездка,
    # ожидание и расписание не учитываются (Дейкстра на 5 станциях)
    ves = {}
    for c in soedineniya:
        k = c[0] + c[1]
        if k not in ves or c[3] - c[2] < ves[k]:
            ves[k] = c[3] - c[2]
    dist = {}
    dist[start] = 0
    gotovo = []
    while len(gotovo) < len(dist):
        v = ""
        for u in sorted(dist.keys()):
            if u not in gotovo and (v == "" or dist[u] < dist[v]):
                v = u
        gotovo.append(v)
        for k, w in sorted(ves.items()):
            if k[0] == v:
                if k[1] not in dist or dist[v] + w < dist[k[1]]:
                    dist[k[1]] = dist[v] + w
    return dist

for t0 in [0, 4, 6]:
    otvet = skan("A", t0)
    rano = otvet[0]
    if "D" in rano:
        print("по расписанию, выезд в", vremya(t0) + ":",
              vremya(rano["D"]))
        print("   ", marshrut(otvet[1], "A", "D"))
    else:
        print("по расписанию, выезд в", vremya(t0) + ": не доехать")
print("граф длительностей:         ", vremya(po_dlitelnostyam("A")["D"]))

по расписанию, выезд в 8:00: 8:42
    ['метро 8:05 A->C', 'трамвай 3 C->E', 'маршрутка 41 E->D']
по расписанию, выезд в 8:04: 8:42
    ['метро 8:05 A->C', 'трамвай 3 C->E', 'маршрутка 41 E->D']
по расписанию, выезд в 8:06: не доехать
граф длительностей:          8:32

Маршрут восстановлен назад от D по соединениям, которые привезли на каждую станцию раньше всех, - для этого skan запоминает их в privez. Граф длительностей уверенно отвечает «8:32» - время, к которому приехать невозможно. Просмотр соединений отвечает 8:42, и, что важнее, его ответ зависит от времени выезда: в 8:04 ещё успеваешь на метро, в 8:06 - уже нет, и маршрута не существует. Метро 8:45 не спасает: оно привозит в C к 9:05, а из C к этому времени всё ушло - трамвай в 8:28, автобус в 8:40. Автобус из A ушёл в 8:00, раньше выезда. Граф длительностей этот ответ дать не может в принципе: в нём нет времени. Цена просмотра - один проход по отсортированному списку, O(m) на запрос, если сортировка сделана заранее. Для города с миллионом соединений в день это миллион простых сравнений на запрос - сколько это в миллисекундах, зависит от языка и машины, а рост линейный при любой реализации.

Края, которые модель пока не учитывает и которые спросит заказчик: время на пересадку (с платформы на платформу не за ноль минут) и ходьба между близкими станциями. Первое одним числом на станцию не учесть: тому, кто остаётся в рейсе, запас не нужен, а тому, кто пересаживается, нужен. Поэтому полная версия просмотра помнит ещё рейсы, в которые уже удалось сесть: соединение годится, если его рейс уже «наш» или на станцию успеваем с запасом на пересадку. Ходьба - не соединение: у неё нет времени отправления, выйти можно в любой момент. Поэтому её учитывают в момент улучшения: как только просмотр улучшил прибытие на станцию A, он сразу улучшает и соседей пешком - rano[B] = min(rano[B], rano[A] + минуты пешком).

Разбор: раньше всех или меньше пересадок

Теперь перебор всех поездок из A в D и подсчёт пересадок: смена рейса - одна пересадка.

soedineniya = [
    ["A", "B", 0, 15, "автобус 12"], ["B", "C", 15, 40, "автобус 12"],
    ["C", "D", 40, 90, "автобус 12"], ["B", "D", 20, 50, "электричка"],
    ["A", "C", 5, 25, "метро 8:05"], ["C", "E", 28, 33, "трамвай 3"],
    ["E", "D", 35, 42, "маршрутка 41"], ["A", "C", 45, 65, "метро 8:45"],
]
poezdki = []

def vremya(m):
    return str(8 + m // 60) + ":" + str(m % 60 // 10) + str(m % 10)

def obhod(stanciya, t, rejs, peresadok, put):
    # все поездки: следующее соединение отправляется не раньше прибытия
    if stanciya == "D":
        poezdki.append([t, peresadok, put])
        return
    for c in soedineniya:
        if c[0] == stanciya and c[2] >= t:
            p = peresadok
            if rejs != "" and c[4] != rejs:
                p = p + 1
            obhod(c[1], c[3], c[4], p, put + [c[4]])

obhod("A", 0, "", 0, [])
# оставляем поездки, которых никто не обгоняет: не хуже по обоим
# критериям и строго лучше хотя бы по одному
for p in sorted(poezdki):
    luchshe_est = False
    for q in poezdki:
        ne_huzhe = q[0] <= p[0] and q[1] <= p[1]
        if ne_huzhe and (q[0] < p[0] or q[1] < p[1]):
            luchshe_est = True
    if not luchshe_est:
        print("прибытие", vremya(p[0]), "| пересадок", p[1], "|", p[2])
print("всего поездок из A в D:", len(poezdki))

прибытие 8:42 | пересадок 2 | ['метро 8:05', 'трамвай 3', 'маршрутка 41']
прибытие 8:50 | пересадок 1 | ['автобус 12', 'электричка']
прибытие 9:30 | пересадок 0 | ['автобус 12', 'автобус 12', 'автобус 12']
всего поездок из A в D: 4

Самый ранний маршрут - с двумя пересадками. Один автобус без пересадок - на 48 минут позже, зато сел и доехал. Посередине - одна пересадка и 8:50. Программа оставила маршруты, которые никто не обгоняет, - нет другого, не худшего по обоим критериям и строго лучшего хотя бы по одному: это множество Парето. Четвёртая поездка выброшена - она и позже, и с пересадками. Какой маршрут лучше, решает человек: с чемоданом или ребёнком выбирают автобус.

Это граница правила про просмотр соединений: в базовом виде он оптимизирует один критерий. Для двух критериев есть свои алгоритмы - например, RAPTOR (Деллинг, Пайор, Вернек, 2012) идёт раундами: в раунде k находит самые ранние прибытия с не более чем k поездками и сразу выдаёт множество Парето по времени и числу пересадок.

Что ломается без этого

Приложение обещает невозможное. «Будете в 8:32» по графу длительностей - и человек опаздывает, поверив.

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

Один «лучший» ответ при двух критериях. Пользователь с чемоданом получает маршрут с двумя пересадками, потому что он на восемь минут быстрее, - как 8:42 против 8:50 в разборе выше.

Зачем это в работе

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

Теперь сам

1. В расписание урока добавили маршрутку C → D, отправление 8:26, прибытие 8:38. Когда теперь самое раннее прибытие в D при выезде в 8:00? Изменится ли ответ графа длительностей?
2. Почему порядок отправления гарантирует, что просмотр ничего не упустит? Годится ли порядок прибытия?
3. Маршруты: (8:40, 3 пересадки), (8:45, 1), (8:45, 2), (9:10, 0). Какие входят в множество Парето?