Сравнение вариантов алгоритма Л*

Рассмотрим два варианта алгоритма А* для одного и того же пространства состояний некоторой задачи:

• — алгоритм А,* с оценочной функцией f (n) =g_t(n) + Л,(л), /г,(я) < h*(n),
• — алгоритм А₂* с оценочной функцией /₂(и) =g₂(n) + h₂(n), h₂(n) < h*(n).

Выше отмечалось, что алгоритм А* с идеальной оценочной функцией /*(п) = g*(n) + h*{n) обеспечивает на каждом шаге поиска раскрытие наименьшего числа вершин, кандидатов для продолжения поиска, и наиболее быстро строит оптимальный решающий путь. Заметим, что эвристической функцией в этом случае является идеальная эвристическая функция h*(n). Можно предположить, что чем точнее произвольная эвристическая функция h (n) приближает снизу функцию И*(п), тем эффективнее (с меньшим числом вершин-кандидатов и быстрее) будет поиск оптимального решающего пути алгоритма Л*. Это предположение подтверждается на практике и в теории. В связи с этим введем определение Определение. Алгоритм А₂* называется более информированным, чем алгоритм А если для всех нецелевых вершин выполняется неравенство /7,(и) <�И₂(п).

Следующая теорема констатирует большую эффективность более информированного варианта алгоритма А*.

Теорема. Если А* и А₂* — два варианта алгоритма, А * для одного и того же пространства состояний некоторой задачи и алгоритм А₂* более информирован, чем алгоритм А,*, то при наличии решающего пути к окончанию поиска каждая вершина, раскрытая алгоритмом А₂*, будет раскрыта также и алгоритмом, А *.

Именно в смысле этой теоремы алгоритм А₂* является более эффективным алгоритмом, чем алгоритм И,*, так как вершин, раскрытых алгоритмом А₂*, согласно теореме будет, вообще говоря, меньше, чем вершин, раскрытых алгоритмом А,*.

Примером, подтверждающим эту теорему, может служить игра «Восемь», если для алгоритма А,* принять h,(S) = 0, а для алгоритма А₂* принять h₂(S), равным числу фишек в состоянии S, стоящих не на своих местах в сравнении с целевым состоянием S,. Тогда алгоритм А, * представляет собой обычный поиск в ширину. Это означает, что каждая вершина, раскрытая алгоритмом Л₂*, оказывается обязательно раскрытой также алгоритмом А,*, так как поиск в ширину раскрывает абсолютно все вершины пространства состояний, если отыскиваются все решающие пути.