data Name = Kosmodrom | UlBylichova | Zvezda
| Zapad | Ineva | De | Krest | Rodnik | Vostok
| Yug | Sirius | Til | TrollevMost | Prizrak | TainstvenniyLes
| DnoBolota | PlBakha | Lao | Sever
| PlShekspira
deriving (Show, Eq)
Предположим, что нам известны координаты каждой из станций. По ним мы можем вычислять расстояние
между станциями по прямой:
| 275
data Point = Point
{ px :: Double
, py :: Double
} deriving (Show, Eq)
place :: Name -> Point
place x = uncurry Point $ case x of
Kosmodrom
-> (-3,7)
UlBylichova
-> (-2,4)
Zvezda
-> (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 или
все узлы не кончатся. Такой поиск называют слепым.
Вот если бы у нас был компас, который в каждой точке указывал в сторону цели нам было бы гораздо
проще. Такой компас принято называть эвристикой. Это функция, которая принимает узел и возвращает
число. Чем меньше число, тем ближе узел к цели. Обычно эвристика указывает не точное расстояние до
цели, поскольку мы не знаем где цель, а приблизительную оценку. Мы не знаем расстояние до цели, но
догадываемся, нам кажется, что она где-то там, ещё чуть-чуть и мы найдём её. Примером эвристики для
поиска по карте может быть функция, которая вычисляет расстояние по прямой до цели. Предположим, что
мы не знаем где находится цель (какая дорога к ней ведёт), но мы знаем её координаты. Также мы знаем