Главная arrow книги arrow Копия Глава 4. arrow Составление допустимых эвристических функций
Составление допустимых эвристических функций

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

Для автоматического формирования эвристических функций на основе определений задач с использованием метода "ослабленной задачи" и некоторых других методов может применяться программа под названием Absolver [1237]. Программа Absolver составила для задачи игры в восемь новую эвристическую функцию, лучшую по сравнению со всеми существовавшими ранее эвристическими функциями, а также нашла первую полезную эвристическую функцию для знаменитой головоломки "кубик Рубика".

Одна из проблем, возникающих при составлении новых эвристических функций, состоит в том, что часто не удается получить эвристическую функцию, которая была бы "лучшей во всех отношениях" по сравнению с другими. Если для решения какой-либо задачи может применяться целая коллекция допустимых эвристических функций h1.. .hm и ни одна из них не доминирует над какой-либо из других функций, то какая из этих функций должна быть выбрана? Оказалось, что такой выбор делать не требуется, поскольку можно взять от них всех самое лучшее, определив такой критерий выбора:

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