Информированный метод поиска

При сравнении допустимых эвристик имеют значение степень информированности и пространственная и временная сложность вычисления каждой из эвристик. Более информированные эвристики позволяют сократить количество развёртываемых узлов, хотя платой за это могут быть затраты времени на вычисление эвристики для каждого узла.

Эффективный коэффициент ветвления (англ. effective branching factor) — среднее число преемников узла в дереве перебора после применения эвристических методов отсечения[1][2]. По эффективному коэффициенту ветвления можно судить о качестве используемой эвристической функции.

Идеальная эвристическая функция (например, таблица поиска) всегда возвращает точные значения длины кратчайшего решения, поэтому дерево перебора содержит только оптимальные решения. Эффективный коэффициент ветвления идеальной эвристической функции близок к 1[1].

Сумма манхэттенских расстояний всех плиток от их целевых позиций:
h_m(n)=3+0+0+3+2+4+2+4+1+3+2+2+
+3+3+2=34.
Оптимальное решение состоит из 50 ходов.

В качестве моделей для испытания алгоритмов поиска и эвристических функций часто используются перестановочные головоломки — Пятнашки 3×3[3][4], 4×4[5][6][7], 5×5[8][9][10], 6×6[11], кубик Рубика[9][12], Ханойская башня с четырьмя стержнями[11][13].

В головоломке «Пятнашки» может быть применена эвристика h_m, основанная на манхэттенском расстоянии. Более конкретно, для каждой плитки подсчитывается манхэттенское расстояние между её текущим положением и её положением в начальном состоянии; полученные величины суммируются.

Можно показать, что эта эвристика является допустимой и преемственной: за один ход её значение не может измениться более чем на ±1.

Эвристическая функция h_m, использующаяся для решения головоломки «Пятнашки», представляет собой нижнюю оценку длины оптимального решения. Помимо этого, h_m(n) — это точное значение длины оптимального решения упрощённой версии головоломки, в которой плитки можно передвигать в занятые позиции. В исходной головоломке присутствует ограничение «в одной клетке не должны находиться две и более плитки», которого нет в упрощённой версии. Задача с меньшим количеством ограничений на возможные действия называется ослабленной задачей (англ. relaxed problem); стоимость решения ослабленной задачи является допустимой эвристикой для первоначальной задачи[1], так как любое решение первоначальной задачи является также решением ослабленной задачи.

Допустимая эвристика может быть основана на стоимости решения подзадачи (англ. subproblem) исходной задачи. Любое решение основной задачи одновременно является решением каждой из её подзадач[1].

Подзадачей задачи решения головоломки «Пятнашки» может быть задача перемещения на свои места плиток 1, 2, 3 и 4. Стоимость решения этой подзадачи является допустимой эвристикой для исходной задачи.

Шаблон «fringe» (целевая конфигурация подзадачи)[6]

Базы данных с шаблонами[1] (англ. Pattern databases) — вид допустимой эвристики, в основе которого лежит идея хранения точного значения стоимости решения для каждого возможного экземпляра подзадачи[1][6][12].

Пример шаблона для головоломки «Пятнашки» изображён на рисунке справа: в определение подзадачи входят позиции семи фишек, находящихся в первом столбце и в первой строке. Количество конфигураций этого шаблона равно ${\displaystyle {\dfrac {16!}{8!}}=518918400}$. Для каждой из конфигураций база данных содержит минимальное количество ходов, необходимое для перевода этой конфигурации в целевую конфигурацию подзадачи, показанную на рисунке. Построение базы данных осуществляется методом обратного поиска в ширину[2][6].

Поиск по первому наилучшему совпадению (англ. best-first search) представляет собой подход, в котором узел для развёртывания выбирается на основе оценочной функции f(n). Для развёртывания выбирается узел с наименьшей оценкой.

Поиск A* — наиболее известная разновидность поиска по первому наилучшему совпадению. В нём применяется оценка f(n) стоимости наименее дорогостоящего пути решения, проходящего через узел n:

f(n) = g(n) + h(n), где

g(n) — стоимость пути от начального узла до узла n,

h(n) — оценка стоимости пути от узла n до цели.

Если h(n) никогда не переоценивает стоимость достижения цели (то есть является допустимой), то поиск A* является оптимальным.

Алгоритм A* с итеративным углублением (iterative deepening A*, IDA*) — применение идеи итеративного углубления в контексте эвристического поиска.

Неинформированный алгоритм итеративного углубления останавливает развёртывание, когда глубина поиска d превышает текущий предел глубины l. Информированный алгоритм IDA* останавливает развёртывание, когда оценка f(n) стоимости пути через текущий узел n превышает текущий предел стоимости пути bound.

Алгоритм IDA* отличается минимальными затратами памяти по сравнению с A* и сравнительно малым (в случае удачного выбора эвристики) количеством развёрнутых узлов по сравнению с IDDFS.

[14]

 node              текущий узел
 g                 стоимость начала решения root..node
 f                 оценка стоимости минимального пути через node
 h(node)           эвристическая оценка стоимости остатка пути node..goal
 cost(node, succ)  функция стоимости пути
 is_goal(node)     функция проверки цели
 successors(node)  функция развёртывания узла node
 
 procedure ida_star(root, cost(), is_goal(), h())
   bound := h(root)
   loop
     t := search(root, 0, bound)
     if t = FOUND then return FOUND
     if t = ∞ then return NOT_FOUND
     bound := t
   end loop
 end procedure
 
 function search(node, g, bound)
   f := g + h(node)
   if f > bound then return f
   if is_goal(node) then return FOUND
   min := ∞
   for succ in successors(node) do
     t := search(succ, g + cost(node, succ), bound)
     if t = FOUND then return FOUND
     if t < min then min := t
   end for
   return min
 end function

SMA* (англ.)