Решение задачи методом поиска

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

При разработке стратегии управления выводом важно определить два вопроса:

1. Какую точку в пространстве состояний принять в качестве исходной? От вы­
бора этой точки зависит и метод осуществления поиска в прямом или об­
ратном направлении.

2. Какими методами можно повысить эффективность поиска решения? Эти методы определяются выбранной стратегией перебора - глубину, в ширину, по
подзадачам или иначе.

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

В качестве простого примера рассмотрим игру "крестики-нолики". Для любой заданной ситуации всегда существует только конечное число допустимых ходов иг­рока. Первый игрок может разместить крестик в любой из девяти клеточек пустой игровой доски. Каждый из таких шагов порождает различные варианты заполнения игровой доски, которые позволяют противнику сделать восемь возможных ответных ходов и т.д. Эту совокупность (в зависимости от возможной конфигурации игровой доски) можно представить в виде вершин графа. Дуги графа представляют разре­шенные ходы, приводящие от одной конфигурации игровой доски к другой. Узлы этого графа соответствуют различным состояниям игрового поля. Результирующая структура называется графом пространства состояний.

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

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

Рисунок 1 - Фрагмент пространства состояний для игры "крестики-нолики"

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

Рисунок 2 - Описание пространства состояний на первом этапе реше­ния задачи диагностики неисправностей автомобиля

С каждым состоянием графа связаны дуги (соответствующие основным диагностиче­ским проверкам), которые ведут к состояниям, представляющим уточненные знания в процессе диагностики. Например, узел неисправности двигателя связан с узлами "двигатель запускается" и "двигатель не запускается". От узла "двигатель не запускает­ся" можно перемещаться к узлам "заводится" и "не заводится". Узел "не заводится" свя­зан с узлами "аккумулятор не работает" и "аккумулятор в порядке" (рис. 3). Можно построить граф, включающий все возможные вопросы и вершины, представ­ляющие заключительные диагностические выводы. Решающее устройство сможет диаг­ностировать автомобильные неполадки, находя путь в этом графе. Заметим, что конкретные вопросы, задаваемые в данном примере, определяют путь на графе. При этом каждый следующий ответ удаляет из рассмотрения ненужные вопросы. Хотя эта задача очень отличается от алгоритма нахождения оптимального пути в игре "крестики-нолики", она тоже решается путем поиска в пространстве состояний.

Рисунок 3 -Описание пространства состояний в задаче диагностики неполадок автомобиля

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

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

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

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

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