Patarakin: 1 версия импортирована

2022-10-19T17:55:04Z

1 версия импортирована

← Предыдущая версия		Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>MagnusFit: Перевод из Английской Википедии

2021-09-19T19:11:06Z

Перевод из Английской Википедии

Новая страница

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

По сути, поиск по краям — это золотая середина между [[A*|алгоритмом поиска A*]] и вариантом {{нп5|Итеративное углубление A*|итеративного углубления A*||
Iterative deepening A*}} ('''IDA*'''<ref>'''IDA*''' — сокращение [[Английский язык|английского]] словосочетания '''''I'''terative '''D'''eepening '''A*''''' ([[Русский язык|рус.]] ''Итеративное углубление A*'')</ref>).

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

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

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

Важное различие между '''поиск по краям''' и '''A*''' состоит в том, что содержимое списков в '''поиске по краям''' необязательно должно быть отсортировано — это значительный выигрыш по сравнению с '''A*''', который требует зачастую дорогостоящего поддержания порядка в его открытом списке. Однако '''поиск по краям''' должен будет посещать, в отличие от '''A*''', одни и те же узлы неоднократно, но стоимость каждого такого посещения постоянна по сравнению с [[Временная сложность алгоритма#Логарифмическое время|логарифмическим временем]] сортировки списка в '''A*''' в худшем случае.

== Псевдокод ==
Реализация обоих списков в одном двусвязном списке, где узлы, предшествующие текущему узлу, являются частью ''«позже»'', а всё остальное — списком ''«сейчас»''. Используя массив предварительно выделенных узлов в списке для каждого узла в сетке, время доступа к узлам в списке сокращается до постоянного. Точно так же массив маркеров позволяет выполнять поиск узла в списке за постоянное время. ''g'' сохраняется как [[хеш-таблица]], а последний массив маркеров сохраняется для постоянного поиска того, был ли ранее посещён узел и действительна ли запись в [[кэш]]е.

<syntaxhighlight lang=cpp>
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)
</syntaxhighlight>
Обратный псевдокод.
<syntaxhighlight lang=cpp>
reverse_path(node)
(g, parent) = C[node]
if parent != null
reverse_path(parent)
print node
</syntaxhighlight>

== Эксперименты ==
При тестировании в сеточной среде, типичной для компьютерных игр, включая непроходимые препятствия, '''поиск по краям''' превзошёл '''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/publications/cig2005.pdf

== Внешние ссылки ==
* Реализация '''Поиска по Краям''' на [[Си (язык программирования)|языке C]] от Хесуса Мануэля Магера Хойса https://github.com/pywirrarika/fringesearch

{{Алгоритмы поиска на графах}}

[[Категория:Алгоритмы на графах]]
[[Категория:Алгоритмы поиска]]

Поиск по краям - История изменений

Patarakin: 1 версия импортирована

ru_wikipedia>MagnusFit: Перевод из Английской Википедии