Учебник по Haskell

-> (0,1)

Zapad

-> (1,7)

Ineva

-> (0.5, 4)

De

-> (0, -1)

Krest

-> (0, -3)

Rodnik

-> (0, -5)

Vostok

-> (-1, -7)

Yug

-> (-7, -1)

Sirius

-> (-3,0)

Til

-> (3,2)

TrollevMost

-> (5,4)

Prizrak

-> (8,6)

TainstvenniyLes

-> (11,7)

DnoBolota

-> (-7, -4)

PlBakha

-> (-3, -3)

Lao

-> (3.5,0)

Sever

-> (6,1)

PlShekspira

-> (3, -3)

dist :: Point -> Point -> Double

dist a b = sqrt $ (px a - px b)^2 + (py a - py b)^2

stationDist :: Station -> Station -> Double

stationDist (St n a) (St m b)

| n /= m && a == b

= penalty

| otherwise

= dist (place a) (place b)

where penalty = 1

Расстояние между точками вычисляется по формуле Евклида (dist). Если у станций одинаковые имена,

но они расположены на разных линиях мы будем считать, что расстояние между ними равно единице. Теперь

нам необходимо описать связность станций. Мы опишем связность в виде функции, которая для данной

станции возвращает список всех соседних с ней станций:

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 очень удобно работать с данными, которые имеют иерархическую структуру. Их можно пред-

ставить в виде дерева, обычно в таких типах у нас есть конструкторы-константы и конструкторы, которые

собирают составные значения. Граф выходит за рамки этого класса данных, потому что рёбра графов могут

образовывать циклы. Но мы схитрим и представим граф поиска в виде дерева. Корнем нашего дерева будет