В информатике поиск по краям (англ. fringe search) — это алгоритм поиска по графу, который находит путь с наименьшей стоимостью от заданного начального узла до одного целевого узла.
По сути, поиск по краям — это золотая середина между алгоритмом поиска A* и вариантом (IDA*IDA* — сокращение английского словосочетания Iterative Deepening A* (рус. Итеративное углубление A*)).
Если g(x) — стоимость пути поиска от первого узла до текущего, а h(x) — эвристика оценки стоимости от текущего узла до цели, тогда — фактическая стоимость пути к цели. Рассмотрим IDA*, который выполняет рекурсивный слева направо поиск в глубину от корневого узла, останавливая рекурсию, как только цель будет найдена или узлы достигнут максимального значения ƒ. Если цель не найдена на первой итерации ƒ, итерация затем увеличивается, и алгоритм выполняет поиск снова. То есть, он повторяется на итерациях.
У IDA* есть три основных недостатка. Во-первых, IDA* будет повторять состояния при наличии нескольких (иногда неоптимальных) путей к целевому узлу - это часто решается путём сохранения кеша посещённых состояний. Изменённый таким образом IDA* обозначается как IDA* с расширенной памятью (ME-IDA*ME-IDA* — сокращение английского словосочетания Memory-Enhanced-IDA* (рус. IDA* с расширенной памятью)), поскольку она использует некоторую память. Кроме того, IDA* повторяет все предыдущие операции поиска снова и снова, что необходимо для работы без хранилища. Сохраняя листовые узлы предыдущей итерации и используя их в качестве начальной позиции следующей, эффективность IDA* значительно повышается (в противном случае на последней итерации он всегда должен был бы посещать каждый узел в дереве).
Поиск по краям реализует эти улучшения в IDA*, используя структуру данных, состоящую более или менее из двух списков для итерации по границе или по краю дерева поиска. Один список «сейчас» хранит текущую итерацию, а другой список «позже» хранит ближайшую следующую итерацию. Таким образом, корневой узел дерева поиска «сейчас» является корнем, а «позже» — пустым. Затем алгоритм выполняет одно из двух действий: Если больше порогового значения, удаляет голову из «сейчас» и добавляет его в конец «позже», то есть сохраняет голову для следующей итерации. В противном случае, если меньше или равняется пороговому значению, разворачивает и отбрасывает голову, рассматривает его потомственные элементы, добавив их в начало «сейчас». В конце итерации пороговое значение увеличивается, список «позже» становится списком «сейчас» и опустошается.
Важное различие между поиск по краям и A* состоит в том, что содержимое списков в поиске по краям необязательно должно быть отсортировано — это значительный выигрыш по сравнению с A*, который требует зачастую дорогостоящего поддержания порядка в его открытом списке. Однако поиск по краям должен будет посещать, в отличие от A*, одни и те же узлы неоднократно, но стоимость каждого такого посещения постоянна по сравнению с логарифмическим временем сортировки списка в A* в худшем случае.
Псевдокод Реализация обоих списков в одном двусвязном списке, где узлы, предшествующие текущему узлу, являются частью «позже», а всё остальное — списком «сейчас». Используя массив предварительно выделенных узлов в списке для каждого узла в сетке, время доступа к узлам в списке сокращается до постоянного. Точно так же массив маркеров позволяет выполнять поиск узла в списке за постоянное время. g сохраняется как хеш-таблица, а последний массив маркеров сохраняется для постоянного поиска того, был ли ранее посещён узел и действительна ли запись в кэше.
init(start, goal) fringe F = s cache C[start] = (0, null) flimit = h(start) found = false
while (found == false) AND (F not empty) fmin = ∞ for node in F, from left to right (g, parent) = C[node] f = g + h(node) if f > flimit fmin = min(f, fmin) continue if node == goal found = true break for child in children(node), from right to left g_child = g + cost(node, child) if C[child] != null (g_cached, parent) = C[child] if g_child >= g_cached continue if child in F remove child from F insert child in F past node C[child] = (g_child, node) remove node from F flimit = fmin
if reachedgoal == true reverse_path(goal) Обратный псевдокод. reverse_path(node) (g, parent) = C[node] if parent != null reverse_path(parent) print node
Эксперименты При тестировании в сеточной среде, типичной для компьютерных игр, включая непроходимые препятствия, поиск по краям превзошёл A* примерно на , в зависимости от использования плиток или октилей. Возможные дальнейшие улучшения включают использование структуры данных, которая легче поддаётся кэшированию.
Примечания
Ссылки Джонатан Шеффер, Ингви Бьёрнссон, Маркус Энценбергер, Роберт К. Холте. Поиск по Краям: Победа над A* в поиске пути на игровых картах. Материалы симпозиума IEEE 2005 года по вычислительному интеллекту и играм (CIG05). Эссекский университет, Колчестер, Эссекс (Великобритания); 4–6 апреля 2005 года. IEEE 2005. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf
Внешние ссылки Реализация Поиска по Краям на языке C от Хесуса Мануэля Магера Хойса https://github.com/pywirrarika/fringesearch
Категория:Алгоритмы на графах Категория:Алгоритмы поиска