Вычисление кратчайшего пути

Итак, как мы будем искать кратчайший путь от Хитроу до Лондона, не используя программных средств? Мы можем посмотреть на картинку, прикинуть, какой путь может быть оптимальным – и, вероятно, сделаем правильное предположение… Вероятно, если дорога небольшая; ну а если у неё насчитывается 10 000 секций? Ого! К тому же мы не будем знать наверняка, что наше решение оптимально: можно лишь сказать, что мы более или менее в этом уверены. Следовательно, это плохое решение.

Посмотрим на упрощённую карту дорожной системы. Можем ли мы найти кратчайший путь до первого перекрёстка (первая точка на A, помеченная A1)? Это довольно просто. Легко увидеть, что будет быстрее – проехать по A или проехать по B и повернуть на A. Очевидно, что выгоднее ехать по B и поворачивать: это займёт 40 минут, в то время как езда напрямую по дороге A займёт 50 минут. Как насчёт пересечения B1? То же самое! Значительно выгоднее ехать по B (включая 10 минут), так как путь по A вместе с поворотом займёт целых 80 минут.

Теперь мы знаем, что кратчайший путь до A1 – это движение по дороге B и переезд на дорогу A по отрезку, который мы назовём C (общее время 40 минут), а также знаем кратчайший путь до B1 – проезд по дороге B (10 минут). Поможет ли нам это, если нужно узнать кратчайший путь до следующего перекрёстка? Представьте себе, да!

Найдём кратчайший путь до пункта A2. Мы можем проехать до A2 из А1 напрямую или ехать через B1 (далее – до B2 либо повернуть на перпендикулярную дорогу). Поскольку мы знаем время пути до A1 и B1, можно легко определить кратчайший путь до A2. Наименьшее время пути до A1 – 40 минут, и ещё за 5 минут мы доберёмся до A2; в результате минимальное время пути на отрезке B–C–A составит 45 минут. Время пути до B1 – всего 10 минут, но затем потребуется ещё целых 110, чтобы добраться до B2 и проехать поворот. Очевидно, кратчайший путь до A2 – это B–C–A. Аналогично кратчайший путь до B2 – проезд до A1 и поворот на другую дорогу.

ПРИМЕЧАНИЕ. Возможно, вы задались вопросом: а что если добраться до A2, переехав на B1 и затем двигаясь прямо? Но мы уже рассмотрели переезд из B1 в A1, когда искали лучший путь до A1, так что нам больше не нужно анализировать этот вариант.

Итак, мы вычислили кратчайшие пути до A2 и B2. Продолжать в том же духе можно до бесконечности, пока мы не достигнем последней точки. Как только мы выясним, как быстрее всего попасть в пункты А4 и В4, можно будет определить самый короткий путь – он и будет оптимальным.

В общем-то для второй секции мы повторяли те же шаги, что и для первой, но уже принимая во внимание предыдущие кратчайшие пути до A и B. Мы можем сказать, что на первом шаге наилучшие пути были пустыми, с «нулевой стоимостью».

Подведём итог. Чтобы вычислить наилучший путь от Хитроу до Лондона, для начала следует найти кратчайший путь до перекрёстка на дороге A. Есть два варианта: сразу ехать по A или двигаться по параллельной дороге и затем сворачивать на дорогу A. Мы запоминаем время и маршрут. Затем используем тот же метод для нахождения кратчайшего пути до следующего перекрёстка дороги B и запоминаем его. Наконец, смотрим, как выгоднее ехать до следующего перекрёстка на дороге A: сразу по A или по дороге B с поворотом на A. Запоминаем кратчайший путь и производим те же расчёты для параллельной дороги. Так мы анализируем все секции, пока не достигнем конца. Когда все секции пройдены, самый короткий из двух путей можно считать оптимальным.

Вкратце: мы определяем один кратчайший путь по дороге A и один кратчайший путь по дороге B; когда мы достигаем точки назначения, кратчайший из двух путей и будет искомым. Теперь мы знаем, как решать эту задачу в уме. Если у вас достаточно бумаги, карандашей и свободного времени, вы можете вычислить кратчайший путь в дорожной сети с любым количеством секций.