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

Информи́рованный по́иск (также эвристический поиск, англ. informed search, heuristic search) — стратегия поиска решений в пространстве состояний, в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами.

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

Эвристические функции

В контексте поиска в пространстве состояний, эвристическая функция (англ. heuristic function) h(n) определена на узлах дерева перебора следующим образом:

h(n) = оценка стоимости наименее дорогостоящего пути от узла n до целевого узла.

Если n — целевой узел, то h(n) = 0.

Узел для развёртывания выбирается на основе функции оценки (англ. evaluation function)

f(n) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n,

f(n) = g(n) + h(n),

где функция g(n) определяет стоимость уже пройденного пути от начального узла до узла n.

Если эвристическая функция h(n) никогда не переоценивает фактическую минимальную стоимость достижения цели (то есть является нижней оценкой фактической стоимости), то такая функция называется допустимой (англ. admissible).

Если эвристическая функция h(n) удовлетворяет условию

h(a) ≤ cost(a, b) + h(b),

где b — потомок a, то такая функция называется преемственной (англ. consistent).

Если f(n) = g(n) + h(n) — функция оценки, h(n) — преемственная функция, то функция f(n) является монотонно неубывающей вдоль любого исследуемого пути. Поэтому преемственные функции также называются монотонными (англ. monotonic).

Любая преемственная функция является допустимой, но не любая допустимая функция является преемственной.

Если h₁(n), h₂(n) — допустимые эвристические функции, и для любого узла n верно неравенство h₁(n) ≥ h₂(n), то h₁ является более информированной эвристикой, или доминирует над h₂.

Если для задачи существуют допустимые эвристики h₁ и h₂, то эвристика h(n) = max(h₁, h₂) является допустимой и доминирует над каждой из исходных эвристик^[1][2].

Сравнение эвристических функций

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

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

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

Примеры задач поиска

В качестве моделей для испытания алгоритмов поиска и эвристических функций часто используются перестановочные головоломки — Пятнашки 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. Стоимость решения этой подзадачи является допустимой эвристикой для исходной задачи.

Базы данных с шаблонами

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

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

Алгоритмы поиска

Поиск по первому наилучшему совпадению

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

Поиск A*

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

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

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

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

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

IDA*

Алгоритм 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

MA*

SMA*

SMA* (англ.)

RBFS

См. также

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

Примечания

Литература

• Stefan Edelkamp, Stefan Schrödl. Heuristic search: theory and applications. — Morgan Kaufmann Publishers, 2012. — 712 с. — ISBN 978-0-12-372512-7.

• Стюарт Рассел, Питер Норвиг. Составление допустимых эвристических функций // Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach. — 2-е изд.. — М.: Вильямс, 2006. — С. 170 — 173. — 1408 с. — ISBN 5-8459-0887-6.

Ссылки

	Имеется викиучебник по теме «Алгоритм поиска A*»

Эта страница в последний раз была отредактирована 24 июня 2023 в 13:18.