Поиск по краям (по бахроме) кратко

Привет, Вы узнаете о том , что такое fringe search, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое fringe search, поиск по границам, поиск по краям , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

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

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

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

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

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

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

При тестировании на сеточных средах, типичных для компьютерных игр, включая непроходимые препятствия, fringe превзошел A* примерно на 10–40 процентов в зависимости от использования плиток или октилей. Об этом говорит сайт https://intellect.icu . Возможные дальнейшие улучшения включают использование структуры данных, которая легче поддается кэшированию.

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