Поиск решений в пространстве состояний интеллектуальных задач

Поиск как основа функционирования СОЗ

 

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

 

Рис.1. Поиск в СОЗ

 

Причем поиск конечного состояния выполняется автоматически на основе реализованной в СОЗ стратегии поиска, которая:

- реализует возможность выбора;

- позволяет выполнять шаги от начального состояния к новым состояниям, более или менее близким к цели.

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

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

Большинство СОЗ работают по этой модели.

 

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

Особенности ПО - это степень сложности объекта, его количественная сложность (размер, количество элементов) и его качественная сложность (сложность его организации и поведения - статический, динамический, развивающийся).

Особенности знаний о ПО - это полнота, определенность, точность знаний о ПО (полнота, определенность, точность данных об объекте, а также полнота и адекватность модели объекта).

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

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

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

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

1.Методы поиска в одном пространстве - применяются в случаях, когда ПО статична и невелика, возможно построение единой полной модели и получение полных и точных данных;

2.Методы поиска в иерархии пространств - применяются в случаях, когда ПО велика, но возможно ее представление в виде иерархии моделей первого типа и получение полных и точных данных;

3.Методы поиска в условиях неопределенности - применяются в случаях, когда ПО недостаточно изучена, имеющиеся данные неполны, ненадежны и недостаточно точны;

4.Методы поиска в динамических пространствах - применяются в случаях, когда ПО представляет собой эволюционирующий, изменяющийся во времени и пространстве, развивающийся объект;

5.Методы поиска на основе нескольких моделей - применяются в случаях, когда ПО неоднородна, агрегирована из объектов различной природы, представление которых требует использования специфических моделей.

2.4.1. Методы поиска в одном пространстве

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

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

Подход на основе "поиска в пространстве состояний" сложился при автоматизации решения игровых задач, отличающихся тем, что каждая такая игра может быть представлена как множество характеризуемых конечным набором признаков ситуаций, смена которых в процессе игры происходит по строго определенным правилам, число которых тоже конечно. Типичными примерами являются игры в шахматы, в шашки, в 8, в крестики-нолики и многие другие. Рассмотрим подробнее этот подход.
Игру в шахматы можно теоретически представить тройкой (S0,F,ST), где S0 - начальное состояние (расположение шахматных фигур на доске); ST - множество заключительных состояний (расположений фигур, означающих мат или ничью); F - множество допустимых по шахматным правилам ходов, реализация каждого из которых преобразует текущее состояние (расположение фигур) в новое. Заключительные состояния множества ST в шахматах явно перечислить невозможно, поэтому множество ST можно лишь описать через свойства заключительных состояний (расположений фигур, означающих мат или ничью). Задача состоит в том, чтобы найти последовательность ходов (операторов), преобразующих S0 в одно из состояний (каждый из игроков желает свое) множества ST. Описать процесс поиска можно с помощью графа, вершины которого соответствуют состояниям (шахматным позициям), а дуги - переходам из состояния в состояние под действием операторов (выполняемых ходов).

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

Не только в шахматах, но и в такой простой игре, как крестики-нолики, возникает вопрос о выборе наилучшего в данной позиции хода. Простейшая стратегия - перебрать все варианты продолжения игры и выбрать ход, соответствующий выигрышному варианту. Однако подсчитано, что в шахматах просмотр позиции лишь на 5 ходов вперед уже дает 1015 вариантов, а в такой простой игре, как крестики-нолики существует 362880 (9!) позиций, число которых за счет учета симметрии можно сократить до 60000, но это тоже не мало. Поэтому вместо полного перебора вариантов используют стратегии с применением "эвристических правил", позволяющих существенно сократить объем перебора за счет снижения гарантии успешности поиска.

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

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

Наиболее предпочтительным является случай, когда удается представить процесс решения сложной задачи в виде уже рассматривавшегося нами в первой главе дизъюнктивно-конъюнктивного дерева (ДК-дерева), изображаемого обычно в виде графа с вершинами двух типов: & и V. Конъюнктивная вершина (&) требует решения всех своих дочерних подзадач, дизъюнктивная же вершина (V) удовлетворяется решением хотя бы одной из дочерних подзадач. Цель поиска в этом случае состоит в нахождении при заданных условиях задачи "решающего подграфа" (части ДК-дерева, удовлетворяющей все его вершины типов & и V). Смешивание дизъюнктивных и конъюнктивных вершин на одно уровне создает неудобства в организации поиска решения, поэтому часто в таких случаях в ДК-дерева вводят фиктивные ребра и вершины. Фиктивность таких вершин состоит в том, что для их выполнения не требуется решения каких-либо задач. По сути, они являют собой лишь логические операторы.

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

Поиск способом "генерация-проверка". Если дерево поиска явно не может быть задано, что обычно бывает при бесконечном или просто слишком большом пространстве поиска, поиск организуется путем создания генератора возможных решений и распознавателя степени их пригодности.

В идеальном случае генератор должен быть полным (т.е. порождать все варианты структур, могущие быть решением) и неизбыточным (т.е. не должен порождать вариантов структур, не могущих быть решением).

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

 

Поиск решений в пространстве состояний интеллектуальных задач

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

Прежде чем применять поиск, важно выбрать определенный способ компьютерно приемлемого представления задачи.

Существует несколько способов, пригодных для решения задач поисковыми методами на компьютере. Среди них рассмотрим способ представления в пространстве состояний задачи, предложенный Г. Саймоном и А. Ньюэллом в GPS [6,9].

Если задача или проблема представляется в пространстве состояний, то с ней связываются три важнейших составляющих:

· Исходное или начальное состояние задачи, например, головоломки.

· Тест окончания или завершения решения задачи, а именно проверка достигнуто ли требуемое конечное (целевое) состояние (найдено решение проблемы), например, собрана ли Вавилонская башня.

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

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

Стратегии поиска разделяются на две большие группы: слепой поиск и направленный (эвристический) поиск.

Основная идея слепого поиска — последовательно генерировать все возможные состояния задачи с проверкой на каждом такте не достигнуто ли целевое состояние.

Направленный поиск использует разного рода эвристики. В частности, иногда удается ввести так называемую оценочную функцию. Она дает оценку расстояния до цели. Далее можно использовать градиентный метод и т.п.

Один из способов наглядного представления процесса эволюции состояний в процессе поиска дает граф, в котором состояния — это узлы или вершины, а операции — дуги. В этом случае процесс поиска можно отождествить с процедурой отыскания пути на графе [9].