Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 43

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 43)

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

Например, если действия в игре в восемь описаны следующим образом: ь В главах 8 н 11 будут описаны формальные языки, подходящие для этого назначения; возможность автоматизировать формирование ослабленных задач появляется прн наличии формальных описаний, с которыми могут проводиться манипуляции, а пока длх этого назначения будет использоваться естественный язык. Глава 4. Информированный поиск и исследование пространства состояний 171 Фишка может быть передвинута из квадрата А в квадрат В, если квадрат А явдяетоя смежным по горизонтали иди по вертикали с квадратом В и квадрат В пуст то могут быть сформированы три ослабленные задачи путем удаления одного или обоих из приведенных выше условий. а) Фишка может быть передвинута из квадрата А в квадрат в, если квадрат А является смежным с квадратом В.

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

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

Если бы было трудно решать и ослабленную задачу, то был бы дорогостоящим сам процесс получения значений соответствующей эвристической функции'. Для автоматического формирования эвристических функций на основе определений задач с использованием метода "ослабленной задачи" и некоторых других методов может применяться программа под названием АЬзо!чег 11237). Программа АЬгю!чег составила для задачи игры в восемь новую эвристическую функцию, лучшую по сравнению со всеми существовавшими ранее эвристическими функциями, атакже нашла первую полезную эвристическую функцию для знаменитой головоломки "кубик Рубика".

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

Поскольку эвристические функции, входя)цие в состав эвристики И, являются допустимыми, сама эта функция также является до- 7 Следует отмстить, что идеальную эвристическую функцию можно также получить, просто разрешив функции Ь "тайком" выполнять полный поиск в ширину. Таким образом, при создании эвристических функций всегда приходится искать компромисс между точностью и временем вычисления. Глава 4. Информированный поиск и исследование пространства состояний 173 но, что соответствующие две ползадачи не перекрываются. Будет ли при этом все еще получена допустимая эвристическая функция? Ответ на этот вопрос является отрицательным, поскольку в решениях подзадачи 1-2-3-4 и подзадачи 5-6-7-8 для данного конкретного состояния должны наверняка присутствовать некоторые общие ходы.

Дело в том, что маловероятна ситуация, при которой фишки 1-2-3-4 можно было бы передвинуть на свои места, не трогая фишек 5-6-7-8, и наоборот. Но что будет, если не учитывать эти ходы? Иными словами, допустим, что регистрируется не общая стоимость решения подзадачи 1-2-3-4, а только количество ходов, в которых затрагиваются фишки 1-2-3-4.

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

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

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

Еше один подход состоит в том, что агент должен обучаться на основании полученного опыта. Здесь под "получением опыта" подразумевается, например, решение большого количества экземпляров игры в восемь. Каждое оптимальное решение задачи игры в восемь предоставляет примеры, на основе которых можно изучать функцию )з(п).

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

(Применимы также методы обучения с подкреплением, которые рассматриваются в главе 21.) Методы индуктивного обучения действует лучше всего, когла в них учитываются Ъ. характеристики состояния, релевантные для оценки этого состояния, а не просто общее описание состояния. Например, характеристика "количество стоящих не на Часть 11. Решение проблем 174 своих местах фишек" может быть полезной при предсказании фактического удаления некоторого состояния от цели. Назовем эту характеристику х, (и) . Например, можно взять 100 сформированных случайным образом конфигураций головоломки игры в восемь и собрать статистические данные об их фактических стоимостях решений.

Допустим, это позволяет обнаружить, что при х,(п), равном 5, средняя стоимость решения составляет около 14, и т.д. Наличие таких данных позволяет использовать значение х„для предсказания значений функции )з(п). Безусловно, можно также применять сразу несколько характеристик. Второй характеристикой, х,(п), может быть "количество пар смежных фишек, которые являются также смежными в целевом состоянии". Каким образом можно скомбинировать значения х, (п) и х, (п) для предсказания значения )з (п)? Общепринятый подход состоит в использовании линейной комбинации, как показано ниже.

й(п) = сг хг (и) + с2 х2 (и) Константы с, и с, корректируются для достижения наилучшего соответствия фактическим данным о стоимостях решений. Предполагается, что константа с„должна быль положительной, а с, — отрицательной. 4.3. АЛГОРИТМЫ ЛОКАЛЪНОГО ПОИСКА И ЗАДАЧИ ОПТИМИЗАЦИИ Рассматривавшиеся до сих пор алгоритмы поиска предназначались для систематического исследования пространств поиска. Такая систематичность достигается благодаря тому, что один или несколько путей хранится в памяти и проводится регистрация того, какие альтернативы были исследованы в каждой точке вдоль этого пути, а какие нет. После того как цель найдена, путь к этой цели составляет также искомое решение данной задачи.

Характеристики

Список файлов книги