|
Информированный метод поискаИнформи́рованный по́иск (также эвристический поиск, англ. informed search, heuristic search) — стратегия поиска решений в пространстве состояний, в которой используются знания, относящиеся к конкретной задаче. Информированные методы обычно обеспечивают более эффективный поиск по сравнению с неинформированными методами. Информация о конкретной задаче формулируется в виде эвристической функции. Эвристическая функция на каждом шаге перебора оценивает альтернативы на основании дополнительной информации с целью принятия решения о том, в каком направлении следует продолжать перебор[1].
Эвристические функцииВ контексте поиска в пространстве состояний, эвристическая функция (англ. heuristic function) h(n) определена на узлах дерева перебора следующим образом:
Если n — целевой узел, то h(n) = 0. Узел для развёртывания выбирается на основе функции оценки (англ. evaluation function)
где функция g(n) определяет стоимость уже пройденного пути от начального узла до узла n.  f1(n) = g(n) + h1(n) — недопустимая эвристика f2(n) = g(n) + h2(n) — допустимая, но не преемственная f3(n) = g(n) + h3(n) — преемственная эвристика Если эвристическая функция h(n) никогда не переоценивает фактическую минимальную стоимость достижения цели (то есть является нижней оценкой фактической стоимости), то такая функция называется допустимой (англ. admissible). Если эвристическая функция h(n) удовлетворяет условию
где b — потомок a, то такая функция называется преемственной (англ. consistent). Если f(n) = g(n) + h(n) — функция оценки, h(n) — преемственная функция, то функция f(n) является монотонно неубывающей вдоль любого исследуемого пути. Поэтому преемственные функции также называются монотонными (англ. monotonic). Любая преемственная функция является допустимой, но не любая допустимая функция является преемственной. Если h1(n), h2(n) — допустимые эвристические функции, и для любого узла n верно неравенство h1(n) ≥ h2(n), то h1 является более информированной эвристикой, или доминирует над h2. Если для задачи существуют допустимые эвристики h1 и h2, то эвристика h(n) = max(h1, h2) является допустимой и доминирует над каждой из исходных эвристик[1][2]. Сравнение эвристических функцийПри сравнении допустимых эвристик имеют значение степень информированности и пространственная и временная сложность вычисления каждой из эвристик. Более информированные эвристики позволяют сократить количество развёртываемых узлов, хотя платой за это могут быть затраты времени на вычисление эвристики для каждого узла. Эффективный коэффициент ветвления (англ. effective branching factor) — среднее число преемников узла в дереве перебора после применения эвристических методов отсечения[1][2]. По эффективному коэффициенту ветвления можно судить о качестве используемой эвристической функции. Идеальная эвристическая функция (например, таблица поиска) всегда возвращает точные значения длины кратчайшего решения, поэтому дерево перебора содержит только оптимальные решения. Эффективный коэффициент ветвления идеальной эвристической функции близок к 1[1].
Примеры задач поиска 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) — это точное значение длины оптимального решения упрощённой версии головоломки, в которой плитки можно передвигать в занятые позиции. В исходной головоломке присутствует ограничение «в одной клетке не должны находиться две и более плитки», которого нет в упрощённой версии. Задача с меньшим количеством ограничений на возможные действия называется ослабленной задачей (англ. relaxed problem); стоимость решения ослабленной задачи является допустимой эвристикой для первоначальной задачи[1], так как любое решение первоначальной задачи является также решением ослабленной задачи. ПодзадачаДопустимая эвристика может быть основана на стоимости решения подзадачи (англ. subproblem) исходной задачи. Любое решение основной задачи одновременно является решением каждой из её подзадач[1]. Подзадачей задачи решения головоломки «Пятнашки» может быть задача перемещения на свои места плиток 1, 2, 3 и 4. Стоимость решения этой подзадачи является допустимой эвристикой для исходной задачи.
Базы данных с шаблонами Базы данных с шаблонами[1] (англ. Pattern databases) — вид допустимой эвристики, в основе которого лежит идея хранения точного значения стоимости решения для каждого возможного экземпляра подзадачи[1][6][12]. Пример шаблона для головоломки «Пятнашки» изображён на рисунке справа: в определение подзадачи входят позиции семи фишек, находящихся в первом столбце и в первой строке. Количество конфигураций этого шаблона равно . Для каждой из конфигураций база данных содержит минимальное количество ходов, необходимое для перевода этой конфигурации в целевую конфигурацию подзадачи, показанную на рисунке. Построение базы данных осуществляется методом обратного поиска в ширину[2][6].
Алгоритмы поискаПоиск по первому наилучшему совпадениюПоиск по первому наилучшему совпадению (англ. best-first search) представляет собой подход, в котором узел для развёртывания выбирается на основе оценочной функции f(n). Для развёртывания выбирается узел с наименьшей оценкой.
Поиск A*Поиск A* — наиболее известная разновидность поиска по первому наилучшему совпадению. В нём применяется оценка f(n) стоимости наименее дорогостоящего пути решения, проходящего через узел n:
Если h(n) никогда не переоценивает стоимость достижения цели (то есть является допустимой), то поиск A* является оптимальным.
IDA*Алгоритм A* с итеративным углублением (iterative deepening A*, IDA*) — применение идеи итеративного углубления в контексте эвристического поиска. Неинформированный алгоритм итеративного углубления останавливает развёртывание, когда глубина поиска d превышает текущий предел глубины l. Информированный алгоритм IDA* останавливает развёртывание, когда оценка f(n) стоимости пути через текущий узел n превышает текущий предел стоимости пути bound. Алгоритм IDA* отличается минимальными затратами памяти по сравнению с A* и сравнительно малым (в случае удачного выбора эвристики) количеством развёрнутых узлов по сравнению с IDDFS. Псевдокод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
См. такжеПримечания
Литература
Ссылки |
