Изучай Haskell во имя добра!

Найдём кратчайший путь до пункта 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

Следующий наш шаг: как представить дорожную систему в системе типов языка 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).

Всегда лучше делать типы данных настолько простыми, насколько это возможно – но не проще!