Миран Липовача - Изучай Haskell во имя добра!

1. На минуту забудьте о языке Haskell и подумайте, как бы вы решали эту задачу в уме. При решении предыдущей задачи мы выясняли, что для вычисления в уме нам нужно держать в памяти некоторое подобие стека и проходить выражение по одному элементу за раз.

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

3. Выясните, как манипулировать данными в языке Haskell так, чтобы получить результат. В прошлом разделе мы воспользовались левой свёрткой списка строк, используя стек в качестве аккумулятора свёртки.

Итак, как мы будем искать кратчайший путь от Хитроу до Лондона, не используя программных средств? Мы можем посмотреть на картинку, прикинуть, какой путь может быть оптимальным – и, вероятно, сделаем правильное предположение… Вероятно , если дорога небольшая; ну а если у неё насчитывается 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. Запоминаем кратчайший путь и производим те же расчёты для параллельной дороги. Так мы анализируем все секции, пока не достигнем конца. Когда все секции пройдены, самый короткий из двух путей можно считать оптимальным.