Русская Википедия:Информированный метод поиска

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

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

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

Узел для развёртывания выбирается на основе функции оценки (Шаблон:Lang-en)

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

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

Файл:Heuristics.png
Значения функций вдоль оптимального решения
f1(n) = g(n) + h1(n) — недопустимая эвристика
f2(n) = g(n) + h2(n) — допустимая, но не преемственная
f3(n) = g(n) + h3(n) — преемственная эвристика

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

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

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

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

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

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

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

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

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

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

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

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

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

Файл:15-puzzle-solvable.svg
Сумма манхэттенских расстояний всех плиток от их целевых позиций:
hm(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].

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

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

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

Ослабленная задача

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

Подзадача

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

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

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

Файл:15-puzzle-fringe.svg
Шаблон «fringe» (целевая конфигурация подзадачи)[6]

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

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

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

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

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

Поиск A*

Шаблон:Main

Поиск 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*Шаблон:Ref-en Шаблон:В планах

RBFS

Шаблон:В планах

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Wikibooks Шаблон:Алгоритмы поиска на графах

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 Ошибка цитирования Неверный тег <ref>; для сносок aima2 не указан текст
  2. ↑ 2,0 2,1 2,2 Ошибка цитирования Неверный тег <ref>; для сносок hsta не указан текст
  3. ↑ Ошибка цитирования Неверный тег <ref>; для сносок reinefeld_1993 не указан текст
  4. ↑ Ошибка цитирования Неверный тег <ref>; для сносок kunkle_2001 не указан текст
  5. ↑ Ошибка цитирования Неверный тег <ref>; для сносок korf_1985 не указан текст
  6. ↑ 6,0 6,1 6,2 6,3 Ошибка цитирования Неверный тег <ref>; для сносок culberson_schaeffer_1998 не указан текст
  7. ↑ Ошибка цитирования Неверный тег <ref>; для сносок korf_schultze_2005 не указан текст
  8. ↑ Ошибка цитирования Неверный тег <ref>; для сносок taylor_korf_1996 не указан текст
  9. ↑ 9,0 9,1 Ошибка цитирования Неверный тег <ref>; для сносок korf_2000 не указан текст
  10. ↑ Ошибка цитирования Неверный тег <ref>; для сносок korf_felner_2002 не указан текст
  11. ↑ 11,0 11,1 Ошибка цитирования Неверный тег <ref>; для сносок felner_korf_hanan_2004 не указан текст
  12. ↑ 12,0 12,1 Ошибка цитирования Неверный тег <ref>; для сносок korf_1997 не указан текст
  13. ↑ Ошибка цитирования Неверный тег <ref>; для сносок korf_felner_2007 не указан текст
  14. ↑ Основан на Lecture Notes: IDA* Шаблон:Wayback
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Информированный_метод_поиска&oldid=10005835