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

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

Следующий наш шаг: как представить дорожную систему в системе типов языка Haskell? Один из способов – считать начальные точки и перекрёстки узлами графа, которые ведут к другим перекрёсткам. Если мы представим, что начальные точки связаны друг с другом дорогой единичной длины, мы увидим, что каждый перекрёсток (или узел графа) указывает на узел на противоположной стороне, а также на следующий узел с той же стороны. За исключением последних узлов они просто показывают на противоположную сторону.

data Node = Node Road Road | EndNode Road

data Road = Road Int Node

Узел – это либо обычный узел, указывающий путь до противоположной дороги и путь до следующего узла по той же дороге, либо конечный узел, который содержит информацию только о противоположной дороге. Дорога хранит информацию о длине отрезка и об узле, к которому она ведёт. Например, первая часть дороги Aбудет представлена как Road 50 a1, где a1равно Node x y; при этом xи y– дороги, которые ведут к B1и A2.

Мы могли бы использовать тип Maybeдля определения данных Road, которые указывают путь по той же дороге. Все узлы содержат путь до параллельной дороги, но только те узлы, которые не являются конечными, содержат пути, ведущие вперёд.

data Node = Node Road (Maybe Road)

data Road = Road Int Node

Можно решить задачу, пользуясь таким способом представления дорожной системы; но нельзя ли придумать что-нибудь попроще? Если вспомнить решение задачи в уме, мы всегда проверяли длины трёх отрезков дороги: отрезок по дороге A, отрезок по дороге Bи отрезок C, который их соединяет. Когда мы искали кратчайший путь к пунктам A1и B1, то рассматривали длины первых трёх частей, которые были равны 50, 10 и 30. Этот участок сети дорог назовём секцией. Таким образом, дорожная система в нашем примере легко может быть представлена в виде четырёх секций: (50, 10, 30), (5, 90, 20), (40, 2, 25)и (10, 8, 0).