Граничный поиск
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В информатике , периферийный поиск — это алгоритм поиска по графу который находит путь с наименьшей стоимостью от заданного начального узла до одного целевого узла .
По сути, периферийный поиск — это золотая середина между 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 , target ) fringe F = s кэш C [ start ] = ( 0 , null ) flimit = h ( start ) Found = false while ( found == false ) AND ( F не пусто ) fmin = ∞ для узла в F , слева направо , если ( g , родительский ) = C [ узел ] f = g + h ( узел ) если f > flimit fmin = min ( f , fmin ) продолжить, узел == цель найдена = истинный разрыв для дочернего элемента в дочерних элементах ( node ), справа налево g_cached [ g_child = g + стоимость ( узел , дочерний элемент ) , если C [ дочерний элемент ] != null ( g_cached , родительский ) = C , дочерний элемент ] если g_child >= продолжить , если дочерний элемент в F удалить дочерний элемент из F вставить дочерний элемент в F мимо узла C [ child ] = ( g_child , node ) удалить узел из F flimit = fmin , если достигнута цель == true обратный_путь ( цель ) Обратный псевдокод.
обратный_путь ( узел ) ( g , родительский ) = C [ узел ] если родительский != нуль обратный_путь ( родительский ) печати узел Эксперименты
[ редактировать ]При тестировании в сеточных средах, типичных для компьютерных игр, включая непроходимые препятствия, бахрома превосходила 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