Поиск по краям

В информатике поиск по краям (англ. fringe search) — это алгоритм поиска по графу^[uk], который находит путь с наименьшей стоимостью от заданного начального узла до одного целевого узла.

По сути, поиск по краям — это золотая середина между алгоритмом поиска A* и вариантом итеративного углубления A*^[en] (IDA*^[1]).

Если g(x) — стоимость пути поиска от первого узла до текущего, а h(x) — эвристика оценки стоимости от текущего узла до цели, тогда $\text{[math]}$ ƒ(x) = g(x) + h(x) — фактическая стоимость пути к цели. Рассмотрим IDA*, который выполняет рекурсивный слева направо поиск в глубину от корневого узла, останавливая рекурсию, как только цель будет найдена или узлы достигнут максимального значения ƒ. Если цель не найдена на первой итерации ƒ, итерация затем увеличивается, и алгоритм выполняет поиск снова. То есть, он повторяется на итерациях.

У IDA* есть три основных недостатка. Во-первых, IDA* будет повторять состояния при наличии нескольких (иногда неоптимальных) путей к целевому узлу - это часто решается путём сохранения кеша посещённых состояний. Изменённый таким образом IDA* обозначается как IDA* с расширенной памятью (ME-IDA*^[2]), поскольку она использует некоторую память. Кроме того, IDA* повторяет все предыдущие операции поиска снова и снова, что необходимо для работы без хранилища. Сохраняя листовые узлы предыдущей итерации и используя их в качестве начальной позиции следующей, эффективность IDA* значительно повышается (в противном случае на последней итерации он всегда должен был бы посещать каждый узел в дереве).

Поиск по краям реализует эти улучшения в IDA*, используя структуру данных, состоящую более или менее из двух списков для итерации по границе или по краю дерева поиска. Один список «сейчас» хранит текущую итерацию, а другой список «позже» хранит ближайшую следующую итерацию. Таким образом, корневой узел дерева поиска «сейчас» является корнем, а «позже» — пустым. Затем алгоритм выполняет одно из двух действий: Если $\text{[math]}$ ƒ(голова) больше порогового значения, удаляет голову из «сейчас» и добавляет его в конец «позже», то есть сохраняет голову для следующей итерации. В противном случае, если $\text{[math]}$ ƒ(голова) меньше или равняется пороговому значению, разворачивает и отбрасывает голову, рассматривает его потомственные элементы, добавив их в начало «сейчас». В конце итерации пороговое значение увеличивается, список «позже» становится списком «сейчас» и опустошается.

Важное различие между поиск по краям и 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* примерно на 10—40 %, в зависимости от использования плиток или октилей. Возможные дальнейшие улучшения включают использование структуры данных, которая легче поддаётся кэшированию.

ПримечанияПравить

↑ IDA* — сокращение английского словосочетания Iterative Deepening A* (рус. Итеративное углубление A*)
↑ ME-IDA* — сокращение английского словосочетания Memory-Enhanced-IDA* (рус. IDA* с расширенной памятью)

СсылкиПравить

Джонатан Шеффер, Ингви Бьёрнссон, Маркус Энценбергер, Роберт К. Холте. Поиск по Краям: Победа над 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

[1] IDA* — сокращение английского словосочетания Iterative Deepening A* (рус. Итеративное углубление A*)

[2] ME-IDA* — сокращение английского словосочетания Memory-Enhanced-IDA* (рус. IDA* с расширенной памятью)

[1]

[2]