Unknown - haskell-notes

поиске на графе очень важно запоминать те вершины, в которых мы уже побывали. Иначе мы будем очень

часто ходить кругами.

В Haskell очень удобно работать с данными, которые имеют иерархическую структуру. Их можно пред-

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

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

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

начальная точка поиска, а поддеревьями для данной вершины узла будут все вершины-соседи. В таком де-

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

вернуться обратно, опять пойти в туже соседнюю вершину, и так до бесконечности. Для того, чтобы избежать

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

если они встретятся нам ещё раз.

Сформулируем задачу поиска в типах. У нас есть дерево поиска, которое содержит все возможные раз-

ветвления, также каждая вершина содержит значение эвристики, по нему мы знаем насколько близка данная

вершина к цели. Также у нас есть специальный предикат, который определён на вершинах, по нему мы мо-

жем узнать является ли данная вершина целью. Нам нужно получить путь, или цепочку вершин, которая

будет начинаться в корне дерева поиска и заканчиваться в целевой вершине.

search :: Ordh =>(a -> Bool) -> Tree(a, h) -> Maybe[a]

Здесь a – это значение вершины и h – значение эвристики. Обратите внимание на зависимость Ordh в

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

запоминать повторяющиеся вершины, для этого мы воспользуемся типом множество из стандартного мо-

дуля Data.Set. Внутри Setмогут хранится только значения, для которых определены операции сравнения,

поэтому нам придётся добавить в контекст ещё одну зависимость:

import Data.Tree

import qualified Data.Set asS

search ::( Ordh, Orda) =>(a -> Bool) -> Tree(a, h) -> Maybe[a]

Поиск будет заключаться в том, что мы будем обходить дерево от корня к узлам. При этом среди всех

узлов-альтернатив мы будем просматривать узлы с наименьшим значением эвристики. В этом нам помо-

жет специальная структура данных, которая называется очередью с приоритетом (priority queue). Эта очередь

хранит элементы с учётом их старшинства (приоритета). Мы можем добавлять в неё элементы и извлекать

элементы. При этом мы всегда будем извлекать элемент с наименьшим приоритетом. Мы воспользуемся

очередями из библиотеки fingertree. Для начала установим библиотеку:

cabal install fingertree

Теперь посмотрим в документацию и узнаем какие функции нам доступны. Документацию к пакету мож-

но найти на сайте http://hackage.haskell.org/package/fingertree. Пока отложим детальное изучение ин-

терфейса, отметим лишь то, что мы можем добавлять элементы к очереди и извлекать элементы с учётом

приоритета:

Алгоритм эвристического поиска А* | 277

insert

:: Ordk =>k ->v -> PQueuek v -> PQueuek v

minView :: Ordk => PQueuek v -> Maybe(v, PQueuek v)

Вернёмся к функции search. Я бы хотел обратить ваше внимание на то, как мы будем разрабатывать эту

функцию. Вспомним, что Haskell – ленивый язык. Это означает, что при обработке рекурсивных типов данных,

функция “углубляется” в значение лишь тогда, когда функция, которая вызвала эту функцию попросит её об

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

важно, разделять сложный алгоритм на независимые составляющие.

В функции search нам необходимо обойти все элементы в порядке значения эвристики и остановиться

в вершине, на которой целевой предикат вернёт True. Но для начала мы добавим к вершинам их пути из

корня, для того чтобы в конце мы смогли узнать как мы попали в текущую вершину. Итак наша функция

разбивается на три составляющие:

search ::( Ordh, Orda) =>(a -> Bool) -> Tree(a, h) -> Maybe[a]

search isGoal =

findPath isGoal .flattenTree .addPath

выпишем типы составляющих функций и проверим код в интерпретаторе.