Главная arrow Поиск arrow Эвристические функции
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

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

Головоломка «игра в восемь» была одной из первых задач эвристического поиска. В ходе решения этой головоломки требуется передвигать фишки по горизонтали или по вертикали на пустой участок до тех пор, пока полученная конфигурация не будет соответствовать целевой конфигурации.

Типичный экземпляр головоломки «игра в восемь». Решение имеет длину 26 этапов

Средняя стоимость решения для сформированного случайным образом экземпляра головоломки «игра в восемь» составляет около 22 этапов. Коэффициент ветвления примерно равен 3. (Если пустой квадрат находится в середине коробки, то количество возможных ходов равно четырем, если находится в углу— двум, а если в середине одной из сторон — трем.) Это означает, что при исчерпывающем поиске на глубину 22 приходится рассматривать примерно 322=3.1 x 1010 состояний.

Отслеживая повторяющиеся состояния, это количество состояний можно сократить приблизительно в 170 000 раз, поскольку существует только 9!/2 = 181 440 различимых состояний, которые являются достижимыми. Это количество состояний уже лучше поддается контролю, но соответствующее количество для игры в пятнадцать примерно равно 1013, поэтому для такой головоломки с более высокой сложностью требуется найти хорошую эвристическую функцию. Если нужно находить кратчайшие решения с использованием поиска A*, то требуется эвристическая функция, которая никогда не переоценивает количество этапов достижения цели.

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

  • h1 = количество фишек, стоящих не на своем месте. На рисунке все восемь фишек стоят не на своем месте, поэтому показанное слева начальное состояние имеет эвристическую оценку h1 = 8. Эвристическая функция h1 является допустимой, поскольку очевидно, что каждую фишку, находящуюся не на своем месте, необходимо переместить по меньшей мере один раз.
  • h2 = сумма расстояний всех фишек от их целевых позиций. Поскольку фишки не могут передвигаться по диагонали, рассчитываемое расстояние представляет собой сумму горизонтальных и вертикальных расстояний. Такое расстояние иногда называют расстоянием, измеряемым в городских кварталах, или манхэттенским расстоянием. Эвристическая функция h2 также является допустимой, поскольку все, что может быть сделано в одном ходе, состоит лишь в перемещении одной фишки на один этап ближе к цели. Фишки от 1 до 8 в рассматриваемом начальном состоянии соответствуют такому значению манхэттенского расстояния: h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18.

Как и можно было предположить, ни одна из этих функций не переоценивает истинную стоимость решения, которая равна 26.

Зависимость производительности поиска от точности эвристической функции

Одним из критериев, позволяющих охарактеризовать качество эвристической функции, является эффективный коэффициент ветвления b*. Если общее количество узлов, вырабатываемых в процессе поиска A* решения конкретной задачи, равно N, а глубина решения равна d, то b* представляет собой коэффициент ветвления, который должно иметь однородное дерево с глубиной d для того, чтобы в нем содержалось N+1 узлов. Поэтому справедлива следующая формула:

N + 1 = 1 + b* + (b*)2 + … (b*)d

Например, если алгоритм A* находит решение на глубине 5 с использованием 52 узлов, то эффективный коэффициент ветвления равен 1,92. Эффективный коэффициент ветвления может изменяться от одного экземпляра одной и той же задачи к другому, но обычно в случае достаточно трудных задач остается относительно постоянным. Поэтому экспериментальные измерения коэффициента b* на небольшом множестве задач могут служить хорошим критерием общей полезности рассматриваемой эвристической функции. Хорошо спроектированная эвристическая функция должна иметь значение b*, близкое к 1, что позволяет быстро решать довольно большие задачи.

Для проверки эвристических функций h1 и h2 авторы сформировали случайным образом 1200 экземпляров задачи с длиной решения от 2 до 24 (по 100 экземпляров для каждого четного значения длины) и нашли их решения с помощью поиска с итеративным углублением и поиска в дереве по алгоритму A* с применением эвристических функций h1 и h2. Данные о среднем количестве узлов, развернутых при использовании каждой стратегии и эффективном коэффициенте ветвления, приведены в таблице. Эти результаты показывают, что эвристическая функция h2 лучше чем h1 и намного лучше по сравнению с использованием поиска с итеративным углублением. Применительно к найденным авторами решениям с длиной 14 применение поиска А* с эвристической функцией h2 становится в 30 000 раз более эффективным по сравнению с неинформированным поиском с итеративным углублением.

Сравнение значений стоимости поиска и эффективного коэффициента ветвления для алгоритмов Iterative-Deepening-Search и А* с h1, h2. Данные усреднялись по 100 экземплярам задачи игры в восемь применительно к различным значениям длины решения
Стоимость поиска Эффективный коэффициент ветвления
d
IDS
A*(h1)
A*(h2)
IDS
A*(h1)A*(h2)
2
10
6
6
2.45
1.79
1.79
4
112
13
12
2.87
1.48
1.45
6
680
20
18
2.73
1.34
1.30
8
6384
39
25
2.80
1.33
1.24
10
47127
93
39
2.79
1.38
1.22
12
3644035
227
73
2.78
1.42
1.24
14
-
539
113
-
1.44
1.23
16
-
1301
211
-
1.45
1.25
18
-
3056
363
-
1.46
1.26
20
-
7276
676
-
1.47
1.27
22
-
18094
1219
-
1.48
1.28
24
-
39135
1641
-
1.48
1.26

 

 

 

 

 

 

 

 

 

 

 

 

 

Интерес представляет вопрос о том, всегда ли эвристическая функция h2 лучше чем h1. Ответ на этот вопрос является положительным. На основании определений этих двух эвристических функций можно легко прийти к выводу, что для любого узла n справедливо выражение h2(n) >= h1(n). Таким образом, можно утверждать, что эвристика h2 доминирует над h1. Доминирование напрямую связано с эффективностью: при поиске A* с использованием функции h2 никогда не происходит развертывание большего количества узлов, чем при поиске A* с использованием h1 (возможно, за исключением нескольких узлов с f(n) = C*). Доказательство этого утверждения является несложным. Напомним, что каждый узел со значением h(n) < C* наверняка должен быть развернут. Это аналогично утверждению, что должен быть наверняка развернут каждый узел со значением h(n) < C* - g(n).

Но поскольку для всех узлов значение h2, по крайней мере, не меньше значения h1 то каждый узел, который должен быть наверняка развернут в поиске A* с h2, будет также наверняка развернут при поиске с h1 а применение эвристической функции h1 может к тому же вызвать и развертывание других узлов. Поэтому всегда лучше использовать эвристическую функцию с более высокими значениями, при тех условиях, что эта функция не переоценивает длину пути решения и что время вычисления этой эвристической функции не слишком велико.

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

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

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

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

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

  1. Фишка может быть передвинута из квадрата A в квадрат В, если квадрат A является смежным с квадратом B.
  2. Фишка может быть передвинута из квадрата A в квадрат B, если квадрат в пуст.
  3. Фишка может быть передвинута из квадрата A в квадрат B.

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

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

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

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

h(n) = max{h1(n), …, hm(n)}

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

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

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

Подзадача для экземпляра игры в восемь, показанного на рисунке. Задание заключается в том, чтобы передвинуть фишки 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 элементов кубика. В настоящее время нет полного понимания того, как можно определить базы данных с непересекающимися шаблонами для подобных задач.

Изучение эвристических функций на основе опыта

Предполагается, что эвристическая функция h(n) оценивает стоимость решения, начиная от состояния, связанного с узлом n. Как может некоторый агент составить подобную функцию? Одно из решений было приведено выше, а именно: агент должен сформулировать ослабленные задачи, для которых может быть легко найдено оптимальное решение. Еще один подход состоит в том, что агент должен обучаться на основании полученного опыта. Здесь под «получением опыта» подразумевается, например, решение большого количества экземпляров игры в восемь. Каждое оптимальное решение задачи игры в восемь предоставляет примеры, на основе которых можно изучать функцию h(n). Каждый пример складывается из состояния, взятого из пути решения, и фактической стоимости пути от этой точки до решения. На основе данных примеров с помощью алгоритма индуктивного обучения может быть сформирована некоторая функция h(n), способная (при счастливом стечении обстоятельств) предсказывать стоимости решений для других состояний, которые возникают во время поиска.

Методы индуктивного обучения действует лучше всего, когда в них учитываются характеристики состояния, релевантные для оценки этого состояния, а не просто общее описание состояния. Например, характеристика «количество стоящих не на своих местах фишек» может быть полезной при предсказании фактического удаления некоторого состояния от цели. Назовем эту характеристику x1(n). Например, можно взять 100 сформированных случайным образом конфигураций головоломки игры в восемь и собрать статистические данные об их фактических стоимостях решений. Допустим, это позволяет обнаружить, что при x1(n), равном 5, средняя стоимость решения составляет около 14, и т.д. Наличие таких данных позволяет использовать значение x1 для предсказания значений функции h(n). Безусловно, можно также применять сразу несколько характеристик. Второй характеристикой, x2(n), может быть «количество пар смежных фишек, которые являются также смежными в целевом состоянии». Каким образом можно скомбинировать значения x1(n) и x2(n) для предсказания значения h(n)? Общепринятый подход состоит в использовании линейной комбинации, как показано ниже.

h(n) = c1x1(n) + c2x2(n)

Константы c1 и c2 корректируются для достижения наилучшего соответствия фактическим данным о стоимостях решений. Предполагается, что константа c1 должна быть положительной, а c2 — отрицательной.