Функциональная ширина Первый поиск

Функциональная глубина первого поиска прекрасна в ориентированных ациклических графах.

Однако в графах с циклами, как избежать бесконечной рекурсии? На процедурный язык я бы отмечал узлы, когда я их ударил, но позвольте сказать, что я не могу этого сделать.

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

Есть ли разумный способ решения этой проблемы? Или мне придется делать с посещенным списком или, богом запретить, изменчивое состояние?

Ответ 1

Одним из вариантов является использование индуктивных графов, которые представляют собой функциональный способ представления и работы с произвольными структурами графов. Они предоставлены библиотекой Haskell fgl и описаны в "Алгоритмы индуктивных графов и функциональных графов" Мартина Эрвига.

Более подробное введение (с иллюстрациями!) См. в моем блоге Создание лабиринтов с помощью индуктивных графиков.

Хитрость с индуктивными графами заключается в том, что они позволяют сопоставлять шаблоны на графиках. Обычная функциональная идиома для работы со списками состоит в том, чтобы разложить их на элемент head и остальную часть списка, а затем повторить:

map f []     = []
map f (x:xs) = f x : map f xs

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

_{(источник: jelv.is)}

Здесь мы сопоставляем узел 1 и все его ребра (выделены синим цветом) отдельно от остальной части графика.

Это позволяет нам написать map для графов (в псевдокоде на Haskellish, который может быть реализован с помощью синонимов шаблона):

gmap f Empty                     = Empty
gmap f ((in, node, out) :& rest) = f (in, node, out) :& gmap f rest

Основным недостатком этого подхода в отличие от списков является то, что графы не имеют единственного естественного способа декомпозиции: один и тот же граф можно построить несколькими способами. Приведенный выше код карты будет посещать все вершины, но в произвольном (зависящем от реализации) порядке.

Чтобы преодолеть это, мы добавляем еще одну конструкцию: функцию match, которая принимает определенный узел. Если этот узел находится на нашем графике, мы получаем успешное совпадение, как и выше; если это не так, все совпадение не будет выполнено.

Этой конструкции достаточно для написания DFS или BFS - с элегантным кодом, который выглядит практически одинаково для обоих!

Вместо того, чтобы вручную отмечать узлы как посещенные, мы просто повторяем на остальной части графика, за исключением узла, который мы видим сейчас: на каждом шаге мы работаем с меньшей и меньшей частью исходного графика. Если мы попытаемся получить доступ к узлу, который мы уже видели с match, его не будет на оставшемся графике, и эта ветвь потерпит неудачу. Это позволяет нашему коду обработки графиков выглядеть так же, как наши обычные рекурсивные функции над списками.

Вот DFS для такого рода графиков. Он сохраняет стек узлов для посещения в виде списка (границы) и запускает начальную границу. Вывод представляет собой список узлов, пройденных по порядку. (Точный код здесь не может быть написан непосредственно с библиотекой без некоторых синонимов пользовательских шаблонов.)

dfs _frontier Empty = []
dfs [] _graph = []
dfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
  dfs (neighbors' ctx ++ ns) rest
dfs (n:ns) graph =                         -- visited n
  dfs ns graph

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

bfs _frontier Empty = []
bfs [] _graph = []
bfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
  bfs (ns ++ neighbors' ctx) rest
bfs (n:ns) graph =                         -- visited n
  bfs ns graph

Да, это все, что нам нужно! Нам не нужно делать ничего особенного, чтобы отслеживать узлы, которые мы посетили, когда мы повторяем по графику, точно так же, как нам не нужно отслеживать ячейки списка, которые мы посетили: каждый раз, когда мы повторяем, мы ' только получить часть графика, которую мы не видели.

Ответ 2

Вы должны следить за узлами, которые вы посещаете. Списки не являются королями в семье ML, они всего лишь один из олигархов. Вы должны просто использовать набор (на основе дерева) для отслеживания посещенных узлов. Это добавит лог-фактор по сравнению с изменением состояния node, но настолько чище, что это не смешно. Если вы знаете больше о своих узлах, вы можете устранить фактор журнала, используя набор, не основанный на дереве (скажем, бит-вектор).

Ответ 3

См. пример реализации BFS, с объяснением в Мартин Эрвиг: индуктивные графики и алгоритмы функционального графика. Кроме того, Реализация DFS, основанная на Дэвид Кинг, Джон Лаунчбери: Структурирование глубины- Алгоритмы первого поиска в Haskell

(Подсказка для полиции SO: да, это похоже на ответ только для ссылок, но именно так работает наука - вы должны действительно читать газеты, перепечатывать их тезисы не очень полезно.)

Ответ 4

Хорошо, что внутри функции скрыто переменное состояние. Если это не видно, то этого не существует. Обычно для этого я использую хэш-множества. Но в общем, вы должны придерживаться этого, если ваш профилирование указывает на это. В противном случае просто используйте структуру данных набора. OCaml имеет отличный набор, основанный на жадно сбалансированных деревьях AVL.