Граничный поиск

В информатике , периферийный поиск — это алгоритм поиска по графу который находит путь с наименьшей стоимостью от заданного начального узла до одного целевого узла .

По сути, периферийный поиск — это золотая середина между A* и вариантом A* с итеративным углублением (IDA*).

Если g ( x ) — стоимость пути поиска от первого узла до текущего, а h ( x ) — эвристическая оценка стоимости от текущего узла до цели, то ƒ ( x ) = g ( x ) + h ( x ) и h * — фактическая стоимость пути к цели. Рассмотрим IDA*, который выполняет рекурсивный слева направо поиск в глубину от корневого узла, останавливая рекурсию, как только цель найдена или узлы достигли максимального значения ƒ . цель не найдена Если в первом пороге ƒ , порог затем увеличивается, и алгоритм выполняет поиск снова. IE. Он выполняет итерацию по порогу.

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

Поиск по границе реализует эти улучшения в IDA*, используя структуру данных, состоящую примерно из двух списков, для перебора границы или границы дерева поиска. Один список сейчас хранит текущую итерацию, а другой список позже сохраняет следующую итерацию. Таким образом, из корневого узла дерева поиска сейчас будет корень, а позже будет пусто. Затем алгоритм выполняет одно из двух действий: если ƒ (head) больше текущего порога, удалить head из now и добавить его в конец позже ; т.е. сохранить голову для следующей итерации. В противном случае, если ƒ (head) меньше или равен порогу, разверните head и отбросьте head , рассмотрите ее дочерние элементы, добавив их в начало now . В конце итерации порог увеличивается, более поздний список становится списком сейчас , а позже очищается.

Важным различием между fringe и A* является то, что содержимое списков в fringe не обязательно должно быть отсортировано – это значительное преимущество по сравнению с A*, которое требует часто дорогостоящего поддержания порядка в открытом списке. Однако, в отличие от A*, fringer придется неоднократно посещать одни и те же узлы, но стоимость каждого такого посещения постоянна по сравнению с логарифмическим временем сортировки списка в 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 процентов, в зависимости от использования плиток или октилей. Возможные дальнейшие улучшения включают использование структуры данных, которая легче поддается кэшированию.

Ссылки

• Бьернссон, Ингви; Энценбергер, Маркус; Холте, Роберт С.; Шеффер, Джонатан. Граничный поиск: пройдите A* в поиске пути на игровых картах. Материалы симпозиума IEEE 2005 г. по вычислительному интеллекту и играм (CIG05). Университет Эссекса, Колчестер, Эссекс, Великобритания, 4–6 апреля 2005 г. IEEE 2005. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/ публикации/cig2005.pdf

Внешние ссылки

• Реализация Fringe Search в C Хесусом Мануэлем Магером Хойсом https://github.com/pywirrarika/fringesearch