| dbo:abstract
|
- In computer science, fringe search is a graph search algorithm that finds the least-cost path from a given initial node to one goal node. In essence, fringe search is a middle ground between A* and the iterative deepening A* variant (IDA*). If g(x) is the cost of the search path from the first node to the current, and h(x) is the heuristic estimate of the cost from the current node to the goal, then ƒ(x) = g(x) + h(x), and h* is the actual path cost to the goal. Consider IDA*, which does a recursive left-to-right depth-first search from the root node, stopping the recursion once the goal has been found or the nodes have reached a maximum value ƒ. If no goal is found in the first threshold ƒ, the threshold is then increased and the algorithm searches again. I.E. It iterates on the threshold. There are three major inefficiencies with IDA*. First, IDA* will repeat states when there are multiple (sometimes non-optimal) paths to a goal node - this is often solved by keeping a cache of visited states. IDA* thus altered is denoted as memory-enhanced IDA* (ME-IDA*), since it uses some storage. Furthermore, IDA* repeats all previous operations in a search when it iterates in a new threshold, which is necessary to operate with no storage. By storing the leaf nodes of a previous iteration and using them as the starting position of the next, IDA*'s efficiency is significantly improved (otherwise, in the last iteration it would always have to visit every node in the tree). Fringe search implements these improvements on IDA* by making use of a data structure that is more or less two lists to iterate over the frontier or fringe of the search tree. One list now, stores the current iteration, and the other list later stores the immediate next iteration. So from the root node of the search tree, now will be the root and later will be empty. Then the algorithm takes one of two actions: If ƒ(head) is greater than the current threshold, remove head from now and append it to the end of later; i.e. save head for the next iteration. Otherwise, if ƒ(head) is less than or equal to the threshold, expand head and discard head, consider its children, adding them to the beginning of now. At the end of an iteration, the threshold is increased, the later list becomes the now list, and later is emptied. An important difference here between fringe and A* is that the contents of the lists in fringe do not necessarily have to be sorted - a significant gain over A*, which requires the often expensive maintenance of order in its open list. Unlike A*, however, fringe will have to visit the same nodes repeatedly, but the cost for each such visit is constant compared to the worst-case logarithmic time of sorting the list in A*. (en)
- En ciencias de la computación, la Búsqueda por Franjas (Fringe Search en inglés) es un algoritmo heurístico de búsqueda sobre grafos, creado por Böjrnsson, Enzenberger, Holte y Schaeffer, que encuentra una ruta desde un nodo inicial dado a un nodo objetivo. La Búsqueda por Franjas es un punto medio entre A* y la variante de profundización iterativa A* (IDA*). (es)
- В информатике поиск по краям (англ. fringe search) — это , который находит путь с наименьшей стоимостью от заданного начального узла до одного целевого узла. По сути, поиск по краям — это золотая середина между алгоритмом поиска A* и вариантом (IDA*). Если g(x) — стоимость пути поиска от первого узла до текущего, а h(x) — эвристика оценки стоимости от текущего узла до цели, тогда ƒ(x) = g(x) + h(x) — фактическая стоимость пути к цели. Рассмотрим IDA*, который выполняет рекурсивный слева направо поиск в глубину от корневого узла, останавливая рекурсию, как только цель будет найдена или узлы достигнут максимального значения ƒ. Если цель не найдена на первой итерации ƒ, итерация затем увеличивается, и алгоритм выполняет поиск снова. То есть, он повторяется на итерациях. У IDA* есть три основных недостатка. Во-первых, IDA* будет повторять состояния при наличии нескольких (иногда неоптимальных) путей к целевому узлу - это часто решается путём сохранения кеша посещённых состояний. Изменённый таким образом IDA* обозначается как IDA* с расширенной памятью (ME-IDA*), поскольку она использует некоторую память. Кроме того, IDA* повторяет все предыдущие операции поиска снова и снова, что необходимо для работы без хранилища. Сохраняя листовые узлы предыдущей итерации и используя их в качестве начальной позиции следующей, эффективность IDA* значительно повышается (в противном случае на последней итерации он всегда должен был бы посещать каждый узел в дереве). Поиск по краям реализует эти улучшения в IDA*, используя структуру данных, состоящую более или менее из двух списков для итерации по границе или по краю дерева поиска. Один список «сейчас» хранит текущую итерацию, а другой список «позже» хранит ближайшую следующую итерацию. Таким образом, корневой узел дерева поиска «сейчас» является корнем, а «позже» — пустым. Затем алгоритм выполняет одно из двух действий: Если ƒ(голова) больше порогового значения, удаляет голову из «сейчас» и добавляет его в конец «позже», то есть сохраняет голову для следующей итерации. В противном случае, если ƒ(голова) меньше или равняется пороговому значению, разворачивает и отбрасывает голову, рассматривает его потомственные элементы, добавив их в начало «сейчас». В конце итерации пороговое значение увеличивается, список «позже» становится списком «сейчас» и опустошается. Важное различие между поиск по краям и A* состоит в том, что содержимое списков в поиске по краям необязательно должно быть отсортировано — это значительный выигрыш по сравнению с A*, который требует зачастую дорогостоящего поддержания порядка в его открытом списке. Однако поиск по краям должен будет посещать, в отличие от A*, одни и те же узлы неоднократно, но стоимость каждого такого посещения постоянна по сравнению с логарифмическим временем сортировки списка в A* в худшем случае. (ru)
|
