Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Эвристический алгоритм поиска пути
Heuristic pathfinding algorithm
Итеративное углубление A* (IDA*) – это алгоритм обхода графа и поиска пути, который может найти кратчайший путь между заданным начальным узлом и любым элементом набора целевых узлов во взвешенном графе. Это вариант поиска в глубину с итеративным углублением, который использует идею применения эвристической функции для консервативной оценки оставшейся стоимости достижения цели, позаимствованную из алгоритма A*. Поскольку это алгоритм поиска в глубину, его использование памяти меньше, чем у A*, но, в отличие от обычного поиска в глубину с итеративным углублением, он сосредотачивается на исследовании наиболее перспективных узлов и, таким образом, не достигает одной и той же глубины во всем дереве поиска. В отличие от A*, IDA* не использует динамическое программирование и поэтому часто исследует одни и те же узлы многократно. В то время как стандартный поиск в глубину с итеративным углублением использует глубину поиска в качестве критерия отсечения для каждой итерации, IDA* использует более информативный критерий: f(n) = g(n) + h(n), где g(n) – стоимость пути от начального узла к узлу n, а h(n) – эвристическая оценка стоимости пути от n к цели, специфичная для решаемой задачи. Алгоритм был впервые описан Ричардом Корфом в 1985 году.
Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth first search that borrows the idea to use a heuristic function to conservatively estimate the remaining cost to get to the goal from the A* search algorithm. Since it is a depth first search algorithm, its memory usage is lower than in A*, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus does not go to the same depth everywhere in the search tree. Unlike A*, IDA* does not utilize dynamic programming and therefore often ends up exploring the same nodes many times. While the standard iterative deepening depth first search uses search depth as the cutoff for each iteration, the IDA* uses the more informative , where is the cost to travel from the root to node and is a problem specific heuristic estimate of the cost to travel from to the goal. The algorithm was first described by Richard Korf in 1985.
Описание
Итеративное углубление A* работает следующим образом: на каждой итерации выполняется поиск в глубину, при этом ветвь отсекается, когда её общая стоимость превышает заданный порог. Этот порог начинается с оценки стоимости в начальном состоянии и увеличивается с каждой итерацией алгоритма. На каждой итерации порог, используемый для следующей итерации, равен минимальной стоимости всех значений, превысивших текущий порог. IDA* полезен в задачах с ограниченной памятью. Поиск A* хранит большую очередь неисследованных узлов, которая может быстро заполнить память. В отличие от него, поскольку IDA* не запоминает никакие узлы, кроме тех, что находятся на текущем пути, ему требуется объем памяти, линейный по длине находящегося в построении решения. Его временная сложность анализируется Корфом и др. при условии, что эвристическая оценка стоимости h является согласованной, то есть
Iterative deepening A* works as follows: at each iteration, perform a depth first search, cutting off a branch when its total cost exceeds a given threshold. This threshold starts at the estimate of the cost at the initial state, and increases for each iteration of the algorithm. At each iteration, the threshold used for the next iteration is the minimum cost of all values that exceeded the current threshold. IDA* is beneficial when the problem is memory constrained. A* search keeps a large queue of unexplored nodes that can quickly fill up memory. By contrast, because IDA* does not remember any node except the ones on the current path, it requires an amount of memory that is only linear in the length of the solution that it constructs. Its time complexity is analyzed by Korf et al. under the assumption that the heuristic cost estimate h is consistent, meaning that
для всех узлов n и всех соседей n' узла n; они заключают, что по сравнению с полным перебором дерева поиска для задачи экспоненциального размера, IDA* достигает меньшей глубины поиска (на постоянный множитель), но не меньшего коэффициента ветвления. Рекурсивный поиск в ширину с лучшим первым выбором – это еще одна версия поиска A* с ограничением памяти, которая может быть быстрее IDA* на практике, поскольку требует меньшего восстановления узлов. Решение кубика Рубика – пример задачи планирования, которую можно эффективно решать с помощью IDA*.
for all nodes n and all neighbors n' of n; they conclude that compared to a brute force tree search over an exponential sized problem, IDA* achieves a smaller search depth (by a constant factor), but not a smaller branching factor. Recursive best first search is another memory constrained version of A* search that can be faster in practice than IDA*, since it requires less regenerating of nodes. Solving the Rubik's Cube is an example of a planning problem that is amenable to solving with IDA*.