Искусственный интеллект. Современный подход

Составление допустимых эвристических функций

Выше было показано, что эвристические функции пг (в которой используется количество стоящих не на своем месте фишек) и я2 (в которой используется манхэт-тенское расстояние) являются довольно неплохими эвристическими функциями для задачи игры в восемь и что функция п2 — из них наилучшая. Но на основании чего именно была предложена функция л2? Возможно ли, чтобы компьютер мог составить некоторую эвристическую функцию механически?
Эвристические функции пг и я2 представляют собой оценки оставшейся длины пути для задачи игры в восемь, но они, кроме того, возвращают идеально точные значения длины пути для упрощенных версий этой игры. Если бы правила игры в восемь изменились таким образом, чтобы любую фишку можно было передвигать куда угодно, а не только на соседний пустой квадрат, то эвристическая функция п± возвращала бы точное количество этапов в кратчайшем решении. Аналогичным образом, если бы любую фишку можно было перемещать на один квадрат в любом направлении, даже на занятый квадрат, то точное количество этапов в кратчайшем решении возвращала бы эвристическая функция я2. Задача с меньшим количеством ограничений на возможные действия называется ослабленной задачей. Стоимость оптимального решения ослабленной задачи представляет собой допустимую эвристику для первоначальной задачи. Такая эвристическая функция является допустимой, поскольку оптимальное решение первоначальной задачи, по определению, служит также решением ослабленной задачи и поэтому должно быть, по меньшей мере, таким же дорогостоящим, как и оптимальное решение ослабленной задачи. Поскольку значение производной эвристической функции представляет собой точную стоимость решения ослабленной задачи, эта функция должно подчиняться неравенству треугольника и поэтому должна быть преемственной (см. с. 160).
Если определение задачи записано на каком-то формальном языке, то существует возможность формировать ослабленные задачи автоматически6. Например, если действия в игре в восемь описаны следующим образом:
Фишка может быть передвинута из квадрата А в квадрат В, если квадрат А является смежным по горизонтали или по вертикали с квадратом В и квадрат В пуст
то могут быть сформированы три ослабленные задачи путем удаления одного или обоих из приведенных выше условий.
а) Фишка может быть передвинута из квадрата А в квадрат В, если квадрат А
является смежным с квадратом В.
б) Фишка может быть передвинута из квадрата А в квадрат в, если квадрат в пуст.
в) Фишка может быть передвинута из квадрата А в квадрат В.
На основании ослабленной задачи а) можно вывести функцию л2 (манхэттенское расстояние). В основе этих рассуждений лежит то, что л2 должна представлять собой правильную оценку, если каждая фишка передвигается к месту ее назначения по очереди. Эвристическая функция, полученная на основании ослабленной задачи б), обсуждается в упр. 4.9. На основании ослабленной задачи в) можно получить эвристическую функцию h± (фишки, стоящие не на своих местах), поскольку эта оценка была бы правильной, если бы фишки можно было передвигать в предназначенное для них место за один этап. Обратите внимание на то, что здесь существенной является возможность решать ослабленные задачи, создаваемые с помощью указанного метода, фактически без какого-либо поиска, поскольку ослабленные правила обеспечивают декомпозицию этой задачи на восемь независимых подзадач. Если бы было трудно решать и ослабленную задачу, то был бы дорогостоящим сам процесс получения значений соответствующей эвристической функции7.
Для автоматического формирования эвристических функций на основе определений задач с использованием метода "ослабленной задачи" и некоторых других методов может применяться программа под названием Absolver [1237]. Программа Absolver составила для задачи игры в восемь новую эвристическую функцию, лучшую по сравнению со всеми существовавшими ранее эвристическими функциями, а также нашла первую полезную эвристическую функцию для знаменитой головоломки "кубик Рубика".
Одна из проблем, возникающих при составлении новых эвристических функций, состоит в том, что часто не удается получить эвристическую функцию, которая была бы "лучшей во всех отношениях" по сравнению с другими. Если для решения какой-либо задачи может применяться целая коллекция допустимых эвристических функций h±.. . Лщ и ни одна из них не доминирует над какой-либо из других функций, то какая из этих функций должна быть выбрана? Оказалось, что такой выбор делать не требуется, поскольку можно взять от них всех самое лучшее, определив такой критерий выбора:
h(n) =max{hi(n), hm{n)}
В этой составной эвристике используется та функция, которая является наиболее точной для рассматриваемого узла. Поскольку эвристические функции, входящие в состав эвристики л, являются допустимыми, сама эта функция также является допустимой; кроме того, можно легко доказать, что функция h преемственна. К тому же h доминирует над всеми эвристическими функции, которые входят в ее состав.
Допустимые эвристические функции могут быть также выведены на основе стоимости решения подзадачи данной конкретной задачи. Например, на рис. 4.6 показана подзадача для экземпляра игры в восемь, приведенного на рис. 4.5. Эта подзадача касается перемещения фишек 1, 2, 3, 4 в их правильные позиции. Очевидно, что стоимость оптимального решения этой подзадачи представляет собой нижнюю границу стоимости решения полной задачи. Как оказалось, такая оценка в некоторых случаях является намного более точной по сравнению с манхэттенским расстоянием.
В основе баз данных с шаблонами лежит такая идея, что указанные точные стоимости решений нужно хранить для каждого возможного экземпляра подзадачи—в нашем примере для каждой возможной конфигурации из четырех фишек и пустого квадрата. (Следует отметить, что при выполнении задания по решению этой подзадачи местонахождения остальных четырех фишек не нужно принимать во внимание, но ходы с этими фишками следует учитывать в стоимости решения.) После этого вычисляется допустимая эвристическая функция hDB (здесь DB — Data Base) для каждого полного состояния, встретившегося в процессе поиска, путем выборки данных для соответствующей конфигурации подзадачи из базы данных. Сама база данных заполняется путем обратного поиска из целевого состояния и регистрации стоимости каждого нового встретившегося шаблона; затраты на этот поиск окупаются за счет успешного решения в дальнейшем многих новых экземпляров задачи.
Выбор фишек 1-2-3-4 является довольно произвольным; можно было бы также создать базы данных для фишек 5-6-7-8, 2-4-6-8 и т.д. По данным каждой базы данных формируется допустимая эвристическая функция, а эти эвристические функции можно составлять в общую эвристическую функцию, как было описано выше, применяя их максимальное значение. Составная эвристическая функция такого вида является намного более точной по сравнению с манхэттенским расстоянием; количество узлов, вырабатываемых при решении сформированных случайным образом экземпляров задачи игры в пятнадцать, может быть уменьшено примерно в 1000 раз.
Представляет интерес вопрос о том, можно ли складывать значения эвристических функций, полученных из баз данных 1-2-3-4 и 5-6-7-8, поскольку очевидно, что соответствующие две подзадачи не перекрываются. Будет ли при этом все еще получена допустимая эвристическая функция? Ответ на этот вопрос является отрицательным, поскольку в решениях подзадачи 1-2-3-4 и подзадачи 5-6-7-8 для данного конкретного состояния должны наверняка присутствовать некоторые общие ходы. Дело в том, что маловероятна ситуация, при которой фишки 1-2-3-4 можно было бы передвинуть на свои места, не трогая фишек 5-6-7-8, и наоборот. Но что будет, если не учитывать эти ходы? Иными словами, допустим, что регистрируется не общая стоимость решения подзадачи 1-2-3-4, а только количество ходов, в которых затрагиваются фишки 1-2-3-4. В таком случае можно легко определить, что сумма этих двух стоимостей все еще представляет собой нижнюю границу стоимости решения всей задачи. Именно эта идея лежит в основе баз данных с непересекающимися шаблонами. Применение таких баз данных позволяет решать случайно выбранные экземпляры задачи игры в пятнадцать за несколько миллисекунд — количество формируемых узлов сокращается примерно в 10 000 раз по сравнению с использованием манхэттенского расстояния. Для задачи игры в 24 может быть достигнуто ускорение приблизительно в миллион раз.
Базы данных с непересекающимися шаблонами успешно применяются для решения головоломок со скользящими фишками, поскольку сама задача может быть разделена таким образом, что каждый ход влияет лишь на одну подзадачу, так как одновременно происходит перемещение только одной фишки. При решении таких задач, как кубик Рубика, подобное разделение не может быть выполнено, поскольку каждый ход влияет на положение 8 или 9 из 26 элементов кубика. В настоящее время нет полного понимания того, как можно определить базы данных с непересекающимися шаблонами для подобных задач.