Применение оценочных функций при эвристическом поиске

Для многих задач имеется возможность использовать информацию, относящуюся к предметной области задачи, для управления поиском.

Рассмотрим, например, такую задачу. Имеется шахматная доска
n*n, где n — очень большое число. Требуется перевести коня из левого верхнего угла в правый нижний за минимальное число ходов. Очевидно, что разумной эвристикой будет движение вдоль главной диагонали. Но эвристическая информация должна иметь числовой вид.

Построим оценочную функцию f(u), принимающую на вершинах графа состояний действительные значения. Таким образом, f(u) — оценка перспективности вершины u. Договоримся строить f таким образом, чтобы вершина с меньшим значением f с большей вероятностью находилась на минимальном пути к целевой вершине.

Определим f так, чтобы ее значение f(u) для любой вершины u оценивало сумму стоимостей минимального пути от исходной вершины s к вершине u + стоимость минимального пути от s до t при условии, что он проходит через вершину u.

Определим функцию f*(u) как стоимость минимального пути от s до u + стоимость минимального пути от u до t:

f*(u)=g*(u)+h*(u).

Мы хотим, чтобы наша оценочная функция f(u) была оценкой f*(u) (стоимости настоящего минимального пути от s до t через u). Тогда

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

g(u) — стоимость уже пройденного пути от s до u (не обязательно минимального!),

h(u) — значение эвристики вершины u.

Таким образом, g(u) есть оценка g*(u) и g(u)≥g*(u); h(u) есть оценка пути, который придется пройти от u до t, и возможны два варианта этой оценки:

h(u)≤h*(u) и h(u)>h*(u).

Эвристики первого типа называются «малыми», эвристики второго типа — «большими».

Как мы увидим далее, эвристики «малого» типа гарантируют минимальность решения, если удается завершить поиск за реальное время. Эвристики «большого» типа не гарантируют того, что решение будет найдено, но если оно будет найдено, то за наименьшее время, так как «большие» эвристики очень сильно фокусируют поиск в направлении целевой вершины.