пустимой; кроме того, можно легко доказать, что функция h преемственна. К тому же h доминирует над всеми эвристическими функции, которые входят в ее состав.

Допустимые эвристические функции могут быть также выведены на основе стоимости решения подзадачи данной конкретной задачи. Например, на рис. 4.6 показана подзадача для экземпляра игры в восемь, приведенного на рис. 4.5. Эта подзадача касается перемещения фишек 1, 2, 3, 4 в их правильные позиции. Очевидно, что стоимость оптимального решения этой подзадачи представляет собой нижнюю границу стоимости решения полной задачи. Как оказалось, такая оценка в некоторых случаях является намного более точной по сравнению с манхэттенским расстоянием.

Рис. 4.6. Подзадача для экземпляра игры в восемь, показанного на рис. 4.5. Задание заключается в том, чтобы передвинуть фишки 1, 2, 3 и 4 в их правильные позиции, не беспокоясь о том, что произойдет с другими фишками

В основе баз данных с шаблонами лежит такая идея, что указанные точные стоимости решений нужно хранить для каждого возможного экземпляра подзадачи—в нашем примере для каждой возможной конфигурации из четырех фишек и пустого квадрата. (Следует отметить, что при выполнении задания по решению этой подзадачи местонахождения остальных четырех фишек не нужно принимать во внимание, но ходы с этими фишками следует учитывать в стоимости решения.) После этого вычисляется допустимая эвристическая функция(здесь DB — Data Base) для каждого полного состояния, встретившегося в процессе поиска, путем выборки данных для соответствующей конфигурации подзадачи из базы данных. Сама база данных заполняется путем обратного поиска из целевого состояния и регистрации стоимости каждого нового встретившегося шаблона; затраты на этот поиск окупаются за счет успешного решения в дальнейшем многих новых экземпляров задачи.