Структуры и стратегии поиска в пространстве состояний

ОБЩЕЕ ОПИСАНИЕ СТРАТЕГИЙ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ

Фундаментальной идеей, которая появилась в результате решения с помощью компьютера игровых задач и головоломок, является идея поиска решения задачи среди альтернативных вариантов.

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

Но поиска в пространстве состояний не достаточно для автоматизации интеллектуального поведения, обеспечивающего автоматическое решение проблем, хотя это важный инструмент для проектирования интеллектуальных программ. Если бы поиска в пространстве состояний было достаточно, то было бы довольно просто написать программу, играющую в шахматы. Для определения последовательности ходов, ведущих к победе, на каждом этапе игры нужно было бы осуществлять полный поиск по всему пространству состояний. Этот метод решения задач известен как исчерпывающий, или поиск методом полного перебора. Хотя полный перебор может применяться в любом пространстве состояний, огромный размер пространства для интересных задач делает этот подход практически неприемлемым. Игре в шахматы, например, соответствует приблизительно 10¹²⁰ различных состояний игровой доски. Это на порядок больше, чем число молекул во Вселенной или число наносекунд, которые минули с «большого взрыва» (момента создания Вселенной). Поиск в таком пространстве состояний выходит за рамки возможностей любого вычислительного устройства, размеры которого должны быть ограничены до известной области. Поиск обеспечивает структуру для автоматизации решения задач, но эта структура лишена интеллекта. Такой подход не дает возможности формально описать задачу. Кроме того, простой полный перебор большого пространства вообще практически неосуществим и непригоден для описания сущности разумной деятельности.

Однако в реальной жизни люди используют поиск: шахматист рассматривает ряд возможных ходов, доктор исследует несколько возможных диагнозов, ученый-программист принимает во внимание различные варианты проекта перед тем, как приступить к написанию кода. Однако люди не используют полный перебор: шахматист исследует только те ходы, которые, как свидетельствует опыт, должны быть эффективными, доктор не требует проведения всех возможных анализов, которые не связаны каким-либо образом с имеющимися симптомами болезни. Проектируя программные средства, математик руководствуется опытом и теоретическими знаниями. Итак, решение задачи человеком основано на субъективных правилах, направляющих поиск к тем частям пространства состояний, которые по каким-то причинам кажутся «обещающими». Эти правила известны под названием эвристик.

Эсристики составляют одну из центральных тем исследований в области искусственного интеллекта. Эвристика (термин возник от греческого слова «находить») — это стратегия для выборочного поиска в пространстве состояний. Она направляет поиск вдоль линий, имеющих высокую вероятность успеха, уводя при этом исследователя от потраченных впустую или очевидно глупых усилий.

Люди используют большое количество эвристик в решении задач.

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

Пространство состояний:

• — Пространство состояний используется в качестве формализованной структуры для представления проблем.
• — Пространство состояний — это ориентированный граф, узлы которого соответствуют проблемным ситуациям, а дуги — возможным действиям. Конкретная задача определяется с помощью начального узла и целевого состояния. В таком случае решение задачи соответствует одному из путей в графе. Поэтому решение задачи сводится к поиску пути в графе.
• — Задачи оптимизации можно моделировать, назначая стоимости дугам в пространстве состояний.
• — Тремя основными стратегиями поиска, которые позволяют систематически исследовать пространство состояний, являются поиск, а глубину, поиск, а ширину и итеративное углубление.
• — Разработка программы поиска в глубину может быть осуществлена проще всего, но такая программа восприимчива к образованию циклов. Для предотвращения циклов применяются два простых метода: ограничение глубины поиска и проверка на наличие повторяющихся узлов.
• — Реализация стратегии поиска в ширину сложнее, поскольку требует сопровождения множества возможных путей. Проще всего такое множество можно представить как список списков.
• — Поиск в ширину всегда позволяет в первую очередь найти кратчайший путь решения, но это утверждение не относится к стратегии поиска в глубину.
• — Для поиска в ширину требуется больше пространства, чем для поиска в глубину. На практике пространство часто является наиболее важным и ограниченным ресурсом. *
• — Метод поиска в глубину с итеративным углублением сочетает в себе наилучшие свойства поиска в глубину и в ширину.

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

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