Изучай Haskell во имя добра! (Липовача) - страница 167
>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 и запоминаем его. Наконец, смотрим, как выгоднее ехать до следующего перекрёстка на дороге