станции возвращает список всех соседних с ней станций:
metroMap :: Station -> [Station]
metroMap x = case x of
St Black Kosmodrom
-> [St Black UlBylichova]
St Black UlBylichova
->
[St Black Kosmodrom, St Black Zvezda, St Red UlBylichova]
St Black
Zvezda
->
[St Black UlBylichova, St Blue
Zvezda, St Green Zvezda]
…
Приведён пример заполнения только для одной линии. Остальные линии заполняются аналогично. Об-
ратите внимание на то, что некоторые станции имеют одинаковые имена, но находятся на разных линиях.
Всё готово для того чтобы написать функцию поиска маршрута. Для этого мы воспользуемся алгоритмом
A*.
19.1 Алгоритм эвристического поиска А*
Наша задача относится к задачам поиска путей на графе. Путём на графе называют такую последователь-
ность узлов, в которой для любых двух соседних узлов существует ребро, которое их соединяет. В нашем
случае графом является карта метро, узлами~– станции, рёбрами~– линии между станциями, а путями~–
маршруты.
Представим, что мы находимся в узле A и нам необходимо попасть в узел B и единственное, что нам
известно~– это все соседние узлы с тем, в котором мы находимся. У нас есть возможность перейти в один
276 | Глава 19: Ориентируемся по карте
из соседних узлов и посмотреть нет ли среди их соседей узла B. В этом случае нам ничего не остаётся кроме
того как бродить по карте от станции к станции в случайном порядке, пока мы не натолкнёмся на узел B или
все узлы не кончатся. Такой поиск называют слепым.
Вот если бы у нас был компас, который в каждой точке указывал в сторону цели нам было бы гораздо
проще. Такой компас принято называть эвристикой. Это функция, которая принимает узел и возвращает
число. Чем меньше число, тем ближе узел к цели. Обычно эвристика указывает не точное расстояние до
цели, поскольку мы не знаем где цель, а приблизительную оценку. Мы не знаем расстояние до цели, но
догадываемся, нам кажется, что она где-то там, ещё чуть-чуть и мы найдём её. Примером эвристики для
поиска по карте может быть функция, которая вычисляет расстояние по прямой до цели. Предположим, что
мы не знаем где находится цель (какая дорога к ней ведёт), но мы знаем её координаты. Также мы знаем
координаты каждой вершины, в которой мы находимся. Тогда мы можем легко вычислить расстояние по
прямой до цели и наш поиск станет гораздо более осмысленным.
Так находясь в точке A мы можем сразу пойти в тот соседний узел, который ближе всех к цели. Такой
поиск называют поиском по первому лучшему приближению. В поиске A* учитывается не только расстояние
до цели, но и то расстояние, которое мы уже прошли. Мы выбираем не ту вершину, которая ближе к цели, а
ту для которой полный путь до цели будет минимальным. Ведь пока мы идём мы можем запоминать какое
расстояние мы уже прошли. Прибавив к этому значению, то которое мы получим с помощью эвристики мы
получим полный (предполагаемый) путь до цели.
Поиск А* гораздо лучше поиска по первому лучшему приближению. Его часто применяют в компьютерных
играх для поиска пути или принятия решений.
Принято разделять поиск на графе и поиск на дереве. Если мы идём по графу, то вершины могут по-
вторятся (они образуют циклы). В случае поиска на дереве мы считаем, что все вершины уникальны. При
поиске на графе очень важно запоминать те вершины, в которых мы уже побывали. Иначе мы будем очень
часто ходить кругами.
В Haskell очень удобно работать с данными, которые имеют иерархическую структуру. Их можно пред-
ставить в виде дерева, обычно в таких типах у нас есть конструкторы-константы и конструкторы, которые
собирают составные значения. Граф выходит за рамки этого класса данных, потому что рёбра графов могут
образовывать циклы. Но мы схитрим и представим граф поиска в виде дерева. Корнем нашего дерева будет
начальная точка поиска, а поддеревьями для данной вершины узла будут все вершины-соседи. В таком де-
реве будет очень много повторяющихся узлов, так например мы можем пойти в соседнюю вершину, потом
вернуться обратно, опять пойти в туже соседнюю вершину, и так до бесконечности. Для того, чтобы избежать
подобных ситуаций мы будем запоминать те вершины, в которых мы уже побывали и не рассматривать их,
если они встретятся нам ещё раз.
Сформулируем задачу поиска в типах. У нас есть дерево поиска, которое содержит все возможные раз-
ветвления, также каждая вершина содержит значение эвристики, по нему мы знаем насколько близка данная
вершина к цели. Также у нас есть специальный предикат, который определён на вершинах, по нему мы мо-
жем узнать является ли данная вершина целью. Нам нужно получить путь, или цепочку вершин, которая
будет начинаться в корне дерева поиска и заканчиваться в целевой вершине.
search :: Ord h => (a -> Bool) -> Tree (a, h) -> Maybe [a]
Здесь a – это значение вершины и h – значение эвристики. Обратите внимание на зависимость Ord h в
контексте, ведь мы собираемся сравнивать эти значения по близости к цели. При обходе дерева мы будем
запоминать повторяющиеся вершины, для этого мы воспользуемся типом множество из стандартного мо-
дуля Data.Set. Внутри Set могут хранится только значения, для которых определены операции сравнения,
поэтому нам придётся добавить в контекст ещё одну зависимость:
import Data.Tree
import qualified Data.Set as S
search :: (Ord h, Ord a) => (a -> Bool) -> Tree (a, h) -> Maybe [a]
Поиск будет заключаться в том, что мы будем обходить дерево от корня к узлам. При этом среди всех
узлов-альтернатив мы будем просматривать узлы с наименьшим значением эвристики. В этом нам помо-
жет специальная структура данных, которая называется очередью с приоритетом (priority queue). Эта очередь
хранит элементы с учётом их старшинства (приоритета). Мы можем добавлять в неё элементы и извлекать
элементы. При этом мы всегда будем извлекать элемент с наименьшим приоритетом. Мы воспользуемся
очередями из библиотеки fingertree. Для начала установим библиотеку:
cabal install fingertree
Теперь посмотрим в документацию и узнаем какие функции нам доступны. Документацию к пакету мож-
но найти на сайте http://hackage.haskell.org/package/fingertree. Пока отложим детальное изучение ин-
терфейса, отметим лишь то, что мы можем добавлять элементы к очереди и извлекать элементы с учётом
приоритета:
Алгоритм эвристического поиска А* | 277
insert
:: Ord k => k -> v -> PQueue k v -> PQueue k v
minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v)
Вернёмся к функции search. Я бы хотел обратить ваше внимание на то, как мы будем разрабатывать эту
функцию. Вспомним, что Haskell – ленивый язык. Это означает, что при обработке рекурсивных типов данных,
функция “углубляется” в значение лишь тогда, когда функция, которая вызвала эту функцию попросит её об
этом. Это даёт нам возможность работать с потенциально бесконечными структурами данных и, что более
важно, разделять сложный алгоритм на независимые составляющие.
В функции search нам необходимо обойти все элементы в порядке значения эвристики и остановиться
в вершине, на которой целевой предикат вернёт True. Но для начала мы добавим к вершинам их пути из
корня, для того чтобы в конце мы смогли узнать как мы попали в текущую вершину. Итак наша функция
