Выше было показано, что эвристические функции h1 (в которой используется количество стоящих не на своем месте фишек) и h2 (в которой используется манхэттенское расстояние) являются довольно неплохими эвристическими функциями для задачи игры в восемь и что функция h2 — из них наилучшая. Но на основании чего именно была предложена функция h2? Возможно ли, чтобы компьютер мог составить некоторую эвристическую функцию механически?

Эвристические функции h1 и h2 представляют собой оценки оставшейся длины пути для задачи игры в восемь, но они, кроме того, возвращают идеально точные значения длины пути для упрощенных версий этой игры. Если бы правила игры в восемь изменились таким образом, чтобы любую фишку можно было передвигать куда угодно, а не только на соседний пустой квадрат, то эвристическая функция h1 возвращала бы точное количество этапов в кратчайшем решении. Аналогичным образом, если бы любую фишку можно было перемещать на один квадрат в любом направлении, даже на занятый квадрат, то точное количество этапов в кратчайшем решении возвращала бы эвристическая функция h2. Задача с меньшим количеством ограничений на возможные действия называется ослабленной задачей. 1 Стоимость оптимального решения ослабленной задачи представляет собой допустимую эвристику для первоначальной задачи. Такая эвристическая функция является допустимой, поскольку оптимальное решение первоначальной задачи, по определению, служит также решением ослабленной задачи и поэтому должно быть, по меньшей мере, таким же дорогостоящим, как и оптимальное решение ослабленной задачи. Поскольку значение производной эвристической функции представляет собой точную стоимость решения ослабленной задачи, эта функция должно подчиняться неравенству треугольника и поэтому должна быть преемственной.

Если определение задачи записано на каком-то формальном языке, то существует возможность формировать ослабленные задачи автоматически6. Например, если действия в игре в восемь описаны следующим образом:

Фишка может быть передвинута из квадрата А в квадрат В, если квадрат А является смежным по горизонтали или по вертикали с квадратом В и квадрат В пустто могут быть сформированы три ослабленные задачи путем удаления одного или обоих из приведенных выше условий.

а)    Фишка может быть передвинута из квадрата А в квадрат В, если квадрат А является смежным с квадратом В.

б)    Фишка может быть передвинута из квадрата А в квадрат в, если квадрат в пуст.

в)    Фишка может быть передвинута из квадрата А в квадрат В.