В информатике , поиск бахрома является графиком алгоритм поиска , который находит путь с наименьшей стоимостью от заданного начального узла к одной цели узла .
По сути, поиск по краям - это золотая середина между A * и вариантом A * с итеративным углублением (IDA *).
Если g ( x ) - стоимость пути поиска от первого узла до текущего, а h ( x ) - эвристическая оценка стоимости от текущего узла до цели, то ƒ ( x ) = g ( x ) + h ( x ) , а h * - фактическая стоимость пути к цели. Рассмотрим IDA *, который делает рекурсивный слева направо поиска в глубину от корневого узла, останавливая рекурсию , как только цель была найдена или узлы достигли максимального значения ƒ. Если цель не найдена в первом пороге ƒ , порог затем увеличивается, и алгоритм выполняет поиск снова. IE Он повторяется на пороге.
У IDA есть три основных недостатка. Во-первых, IDA * будет повторять состояния при наличии нескольких (иногда неоптимальных) путей к целевому узлу - это часто решается путем сохранения кеша посещенных состояний. Измененная таким образом IDA * обозначается как IDA * с расширенной памятью (ME-IDA *), поскольку она использует некоторую память. Кроме того, IDA * повторяет все предыдущие операции поиска при итерациях с новым порогом, который необходим для работы без хранилища. Сохраняя листовые узлы предыдущей итерации и используя их в качестве начальной позиции следующей, эффективность IDA * значительно повышается (в противном случае на последней итерации он всегда должен был бы посещать каждый узел в дереве).
Fringe search реализует эти улучшения в IDA *, используя структуру данных, которая представляет собой более или менее двух списков для итерации по границе или краю дерева поиска. В одном списке теперь хранится текущая итерация, а в другом списке позже сохраняется ближайшая следующая итерация. Таким образом, из корневого узла дерева поиска теперь будет корень, а затем будет пусто. Тогда алгоритм принимает один из двух действий: Если ƒ (голова) больше порогового значения тока, удалить голову из ныне и добавить его к концу позже ; т.е. сохранить голову для следующей итерации. В противном случае, если ƒ (голова) меньше или равно пороговому значению, расширить голову и отбрасывания голову , считают своих детей, добавляя их к началу Сейчас . В конце итерации порог увеличивается, более поздний список становится списком « Сейчас» , а позже очищается.
Важное различие между fringe и A * состоит в том, что содержимое списков в fringe необязательно должно быть отсортировано - это значительный выигрыш по сравнению с A *, который требует зачастую дорогостоящего поддержания порядка в его открытом списке. Однако в отличие от A *, fringe должен будет посещать одни и те же узлы неоднократно, но стоимость каждого такого посещения постоянна по сравнению с логарифмическим временем сортировки списка в A * в худшем случае.
Псевдокод
Реализация обоих списков в одном двусвязном списке, где узлы, предшествующие текущему узлу, являются более поздней частью, а все остальное - списком сейчас . Используя массив предварительно выделенных узлов в списке для каждого узла в сетке, время доступа к узлам в списке сокращается до постоянного. Точно так же массив маркеров позволяет выполнять поиск узла в списке за постоянное время. g хранится как хэш-таблица, а последний массив маркеров сохраняется для постоянного поиска того, был ли ранее посещен узел и действительна ли запись в кэше.
init ( start , goal ) fringe F = s cache C [ start ] = ( 0 , null ) flimit = h ( start ) found = false в то время как ( найдено == ложь ) и ( F не пусто ) Fmin = ∞ для узла в F , от влево , чтобы справа ( г , родительский ) = C [ узел ] е = г + ч ( узел ) , если е > flimit Fmin = мин ( е , Fmin ) продолжить , если узел == цель нашла = истинный перерыв для ребенка в детях ( узел ), от права на левый g_child = г + стоимость ( узел , ребенок ) , если C [ ребенок ] ! = NULL ( g_cached , родительская ) = C [ child ] if g_child > = g_cached продолжить, если дочерний элемент в F удалить дочерний элемент из F вставить дочерний элемент в F после узла C [ child ] = ( g_child , node ) удалить узел из F flimit = fmin если достигнута цель == истина обратный_путь ( цель )
Обратный псевдокод.
reverse_path ( узел ) ( g , parent ) = C [ узел ] if parent ! = null узел печати reverse_path ( родительский )
Эксперименты
При тестировании в сеточной среде, типичной для компьютерных игр, включая непроходимые препятствия, fringe превзошел A * примерно на 10-40 процентов, в зависимости от использования тайлов или октилей. Возможные дальнейшие улучшения включают использование структуры данных, которая легче поддается кэшированию.
Рекомендации
- Бьёрнссон, Ингви; Энценбергер, Маркус; Holte, Роберт C .; Шеффер, Джонатан. Fringe Search: победа над 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