Оценочная функция. 
Символический искусственный интеллект: математические основы представления знаний

Эвристическая информация может иметь любую форму. В ИИ принято представлять эвристическую информацию в виде оценочной функции F (d).

Оценочная функция F определена на множестве допустимых состояний среды (базы фактов) и принимает вещественные числовые значения F:D—>M" Причем обычно выбирают оценочную функцию таким образом, чтобы на терминальных узлах ее значение было минимально — F (d_t) = = min{d е D | F (d)}. Если задана такая оценочная функция, то можно записать функцию Select, используя идею наискорейшего спуска (алгоритм 3.2).

Алгоритм 3.2. Функция выбора узла для раскрытия

Proc Select (О) m: = оо d' := nil for d е О do if F (d) < m then d' := d m := F (d).

end if end for return (d') end proc.

Или короче:

Select (0) := min F (d), d e 0.

Для оценочной функции F предложено много различных идей реализации. Слово «оценочная» означает, что F (предположительно) близка к каким-то важным характеристикам поиска. Ниже приведен список некоторых характерных свойств, которые часто пытаются использовать при выборе оценочной функции:

• • величина, обратная вероятности того, что d принадлежит оптимальному пути;
• • расстояние от узла d до целевого множества узлов Т
• • вес пути от исходной вершины d₀ до целевой вершины d_t через текущую вершину d.

Здесь мы рассматриваем именно последний случай.

Будем рассматривать оценочную функцию в следующей форме:

гдeg (d) — фактическая стоимость пути от исходной вершины d₀ до d (уже определена нами в процедуре Open); h (d) — эвристическая оценка стоимости пути от d до целевой вершины d_t.

Рассмотрим процесс выбора оценочной функции на примере игры в «восемь»^[1] (см. п. 2.1.5). Введем оценочную функцию F (d) как сумму глубины в дереве (соответствует функции g (d)) и числа шашек не на своем месте (соответствует функции h (d)). Мы видим (рис. 3.1), что с такой оценочной функцией поиск на графе оказывается весьма эффективным и быстро приводит к решению.

Рис. 3.1. Граф поиска для игры в «восемь» со значением оценочной функции F.

Сделаем несколько наблюдений по этому примеру: • h (dr) = 0, так как в целевой позиции все шашки находятся на своем месте по определению; • h (d) не превосходит минимального числа ходов, которые необходимо совершить, чтобы перейти из d в dr • значение функции F (d) для раскрываемых узлов не убывает; • если взять функцию Столько как глубину в дереве, т. е. положить h = = 0, то получится просто поиск в ширину. В следующем параграфе мы обобщим и истолкуем эти эмпирические наблюдения.

• [1] Дал У., Дейкстра Э., Хоар К. Структурное программирование.