«ВВЕДЕНИЕ В ИНТЕЛЛЕКТУАЛЬНЫЕ ИНФОРМАЦИОННЫЕ СИСТЕМЫ УДК 004.8 (075.8) ББК 32.813я73 C34 Сидоров С. П., Дудов С. И. С34 Введение в интеллектуальные информационные системы: Учеб. пособие для студентов мех.-мат. фак. ...»

С. П. Сидоров, С. И. Дудов

ВВЕДЕНИЕ

В ИНТЕЛЛЕКТУАЛЬНЫЕ

ИНФОРМАЦИОННЫЕ

СИСТЕМЫ

УДК 004.8 (075.8)

ББК 32.813я73

C34

Сидоров С. П., Дудов С. И.

С34 Введение в интеллектуальные информационные системы: Учеб.

пособие для студентов мех.-мат. фак. Саратов: Изд-во Сарат. унта, 2004. – 100 с.: ил.

ISBN 5-292-03310-3 Пособие посвящено некоторым вопросам проектирования интеллектуальных информационных систем. Особое внимание уделяется представлению знаний, системам продукций искусственного интеллекта и экспертным системам.

Для студентов механико-математического факультета, обучающихся по специальности Прикладная информатика (по областям).

Рекомендуют к печати:

Кафедра математической экономики Саратовского государственного университета Кандидат физико-математических наук О. В. Мещерякова Кандидат физико-математических наук Л. Б. Тяпаев УДК 004.8 (075.8) ББК 32.813я Работа издана в авторской редакции c Сидоров С. П., Дудов С. И., ISBN 5-292-03310- Введение В настоящее время актуальным направлением совершенствования программного обеспечения является его интеллектуализация. Под этим понимается, в частности, применение декларативных языков для описания постановок задач, способов их решения, а также смещение центра управления процессом решения задачи от пользователя к программной системе. Это должно позволить в будущем не только обеспечить ускорение процесса решения специфических практических задач, но и понизить требования к квалификации пользователя без потери качества решения поставленной задачи.

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

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

Данное учебное пособие написано в соответствии с программой дисциплины Интеллектуальные информационные системы из государственного стандарта специальности Прикладная информатика (по областям).

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

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

Настоящее пособие предназначено для студентов механико-математического факультета СГУ, обучающихся по специальностям Прикладная информатика в экономике и Прикладная информатика в юриспруденции, изучающих курс Интеллектуальные информационные системы.

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

В моделировании искусственного интеллекта исторически сложились три основных направления.

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

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

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

1.2. Фактуальное и операционное знание Любая информационная система (ИС) выполняет следующие функции: воспринимает вводимые пользователем информационные запросы и необходимые исходные данные, обрабатывает введенные и хранимые в системе данФактуальное и операционное знание ные в соответствии с известным алгоритмом и формирует требуемую выходную информацию. С точки зрения реализации перечисленных функций ИС можно рассматривать как фабрику, производящую информацию, в которой заказом является информационный запрос, а инструментом (оборудованием) знание, с помощью которого данные преобразуются в информацию.

Знание имеет двоякую природу: фактуальную и операционную.

Фактуальное знание это осмысленные и понятые данные. Данные сами по себе это специально организованные знаки на каком-либо носителе.

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

Часто фактуальное знание называют экстенсиональным (детализированным), а операционное знание интенсиональным (обобщенным).

Процесс извлечения информации из данных сводится к адекватному соединению операционного и фактуального знаний и в различных типах ИС выполняется по разному. Самый простой путь их соединения заключается в рамках одной прикладной программы (рис. 1).

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

Следствием перечисленных недостатков является плохая жизнеспособность ИС или неадаптивность к изменениям информационных потребностей.

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

В системах, основанных на обработке баз данных (СБД Data Base Systems), происходит отделение фактуального и операционного знаний друг от друга. Первое организуется в виде базы данных, второе в виде программ.

Причем программа может автоматически генерироваться по запросу пользователя (например, реализация SQL- или QBE- запросов). В качестве посредника между программой и базой данных выступает программный инструмент доступа к данным система управления базой данных (СУБД) (рис. 2).

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

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

Анализ структуры программы показывает возможность выделения из программы операционного знания (правил преобразования данных) в так называемую базу знаний, которая в декларативной форме хранит общие для различных задач единицы знаний. При этом управляющая структура ма вывода), который связывает единицы знаний в исполняемые цепочки (генерируемые алгоритмы) в зависимости от конкретной постановки задачи (сформулированной в запросе цели и исходных условий). Такие системы становятся системами, основанными на обработке знаний (Knowledge Base (Based) Systems):

Рис. 3. Структура системы, основанной на обработке знаний Следующим шагом в развитии интеллектуальных информационных систем является выделение в самостоятельную подсистему репозитория метазнания, описывающего структуру операционного и фактуального знания и отражающего модель проблемной области. В таких системах и программы, и структуры данных генерируются или компонуются из единиц знаний, описанных в репозитории, каждый раз при изменении модели проблемной области. Будем называть ИИС, обрабатывающие метазнание, системами, основанными на моделях (Model Based Systems).

1.3. Признаки интеллектуальных информационных систем Для интеллектуальных информационных систем, ориентированных на генерацию алгоритмов решения задач, характерны следующие признаки:

развитые коммуникативные способности;

умение решать сложные плохо формализуемые задачи;

способность к самообучению;

адаптивность.

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

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

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

Адаптивность способность к развитию системы в соответствии с объективными изменениями модели проблемной области.

В различных ИИС перечисленные признаки интеллектуальности развиты в неодинаковой степени, и редко когда все четыре признака реализуются одновременно. Условно каждому из признаков интеллектуальности соответствует свой класс ИИС:

системы с интеллектуальным интерфейсом;

экспертные системы;

самообучающиеся системы;

адаптивные системы.

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

Вывести список товаров, цена которых выше среднеотраслевой, Вывести список товаров-заменителей некоторой продукции, Вывести список потенциальных покупателей некоторого товара и т.д.

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

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

Естественно-языковой интерфейс предполагает трансляцию естественноязыковых конструкций на внутримашинный уровень представления знаний.

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

Синтез высказываний решает обратную задачу преобразования внутреннего представления информации в естественно-языковое.

Естественно-языковой интерфейс используется для:

доступа к интеллектуальным базам данных;

контекстного поиска документальной текстовой информации;

голосового ввода команд в системах управления;

машинного перевода с иностранных языков.

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

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

Системы когнитивной графики позволяют осуществлять интерфейс пользователя с ИИС с помощью графических образов, которые генерируются в соответствии с происходящими событиями. Такие системы используются в мониторинге и управлении оперативными процессами. Графические образы в наглядном и интегрированном виде описывают множество параметров изучаемой ситуации. Например, состояние сложного управляемого объекта отображается в виде человеческого лица, на котором каждая черта отвечает за какой-либо параметр, а общее выражение лица дает интегрированную характеристику ситуации.

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

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

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

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

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

Это понимание, возникшее в начале 70-х годов, по существу, означало качественный скачок в работах по искусственному интеллекту.

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

Экспертные системы [3] это интеллектуальные программы, способные делать логические выводы на основании знаний в конкретной предметной области и обеспечивающие решение специфических задач на профессиональном уровне.

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

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

1.6. Самообучающиеся системы В основе самообучающихся систем лежат методы автоматической классификации примеров ситуаций реальной практики (обучения на примерах). Примеры реальных ситуаций накапливаются за некоторый исторический период и составляют обучающую выборку. Эти примеры описываются множеством признаков классификации. Причем обучающая выборка может быть:

с учителем, когда для каждого примера задается в явном виде значение признака его принадлежности некоторому классу ситуаций (классообразующего признака);

без учителя, когда по степени близости значений признаков классификации система сама выделяет классы ситуаций.

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

Общие недостатки, свойственные всем самообучающимся системам, заключаются в следующем:

возможна неполнота и/или зашумленность (избыточность) обучающей выборки и, как следствие, относительная адекватность базы знаний возникающим проблемам;

возникают проблемы, связанные с плохой смысловой ясностью зависимостей признаков и, как следствие, неспособность объяснения пользователям получаемых результатов;

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

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

Процесс классификации примеров осуществляется следующим образом.

1. Выбирается признак классификации из множества заданных (либо последовательно, либо по какому-либо правилу).

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

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

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

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

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

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

Обучение нейронной сети сводится к определению связей (синапсов) между нейронами и установлению силы этих связей (весовых коэффициентов).

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

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

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

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

Системы, основанные на прецедентах, применяются как системы распространения знаний с расширенными возможностями или как в системах контекстной помощи.

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

Типичными задачами оперативного ситуационного анализа являются:

определение профиля потребителей конкретного товара;

предсказание изменений ситуаций на рынке;

анализ зависимостей признаков ситуаций (корреляционный анализ) и др.

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

1.7. Адаптивные информационные системы В условиях динамического развития экономических объектов возрастают требования к адаптивности информационных систем к изменениям. Эти требования сводятся к следующему:

ИС в каждый момент времени должна адекватно поддерживать организацию бизнес-процессов;

реконструкция ИС должна проводиться всякий раз, как возникает потребность в реорганизации бизнес-процессов;

реконструкция ИС должна проводиться быстро и с минимальными затратами.

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

При проектировании информационной системы обычно используются два подхода: оригинальное или типовое проектирование. Первый подход предполагает разработку информационной системы с чистого листа в соответствии с требованиями экономического объекта, второй подход адаптацию типовых разработок к особенностям экономического объекта. Первый подход, как правило, реализуется на основе применения систем автоматизированного проектирования ИС или CASE-технологий, второй подход на основе применения систем компонентного (сборочного) проектирования ИС.

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

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

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

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

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

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

1.8. Языки программирования для ИИ и языки представления знаний Для разработки прикладных систем, ориентированных на знания, необходимо использование средств автоматизации программирования таких систем.

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

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

расширение базисных языков ИИ до систем представления знаний за счет специализированных библиотек и пакетов;

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

На начальном этапе развития искусственного интеллекта были разработаны языки и системы обработки символьной информации, которые на несколько десятилетий стали основным инструментом программирования интеллектуальных систем. До недавнего времени наиболее популярным базовым языком реализации систем искусственного интеллекта вообще и экспертных систем в частности был LISP. Язык LISP был разработан в Стэнфорде под руководством Дж. Маккарти в начале 1960-х годов на основе следующих принципов: использование единого спискового представления для программ и данных; применение выражений для определения функций; скобочный синтаксис языка.

В 1971 г. в Марсельском университете был разработан язык PROLOG.

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

В 70-х годах в программировании вообще и программировании задач искусственного интеллекта в частности центр тяжести стал смещаться от процедурных к декларативным описаниям. К этому же времени сформировались и концепции представления знаний на основе семантических сетей и фреймов. Естественно, что появились и специальные языки программирования, ориентированные на поддержку этих концепций. Характерными чертами этих языков представления знаний были: двухуровневое представление данных (абстрактная модель предметной области в виде иерархии множеств понятий и конкретная модель ситуации как совокупность взаимосвязанных экземпляров этих понятий); представление связей между понятиями и закономерностей предметной области в виде присоединенных процедур; семантический подход к сопоставлению образцов и поиску по образцу.

Глава Представление знаний в интеллектуальных системах 2.1. Данные и знания При изучении интеллектуальных систем традиционно возникает вопрос что же такое знания и чем они отличаются от обычных данных, десятилетиями обрабатываемых ЭВМ. Можно предложить несколько рабочих определений, в рамках которых это становится очевидным.

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

При обработке на ЭВМ данные трансформируются, условно проходя следующие этапы:

D1 данные как результат измерений и наблюдений;

D2 данные на материальных носителях информации (таблицы, протоколы, справочники);

D3 модели (структуры) данных в виде диаграмм, графиков, функций;

D4 данные в компьютере на языке описания данных;

D5 базы данных на машинных носителях информации.

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

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

При обработке на ЭВМ знания трансформируются аналогично данным:

Z1 знания в памяти человека как результат мышления;

Z2 материальные носители знаний (учебники, методические пособия);

Z3 поле знаний, т.е. условное описание основных объектов предметной области, их атрибутов и закономерностей, их связывающих;

Z4 знания, описанные на языках представления знаний (продукционные языки, семантические сети, фреймы см. далее);

Z5 база знаний на машинных носителях информации.

Часто используется такое определение знаний.

Знания это хорошо структурированные данные, или данные о данных, или метаданные.

Существует множество способов определять понятия. Один из широко применяемых способов основан на идее интенсионала.

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

Интенсионалы формулируют знания об объектах.

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

Пример. Понятие персональный компьютер. Его интенсионал: Персональный компьютер это дружественная ЭВМ, которую можно поставить на стол и купить менее чем за $2000–3000. Экстенсионал этого понятия:

Персональный компьютер это Mac, IBM PC, Sinkler,....

Для хранения данных используются базы данных (для них характерны большой объем и относительно небольшая удельная стоимость информации), для хранения знаний базы знаний (небольшого объема, но исключительно дорогие информационные массивы). База знаний основа любой интеллектуальной системы.

Знания могут быть классифицированы по следующим категориям.

1. Поверхностные знания это знания о видимых взаимосвязях между отдельными событиями и фактами в предметной области.

2. Глубинные знания это абстракции, аналогии, схемы, отображающие структуру и природу процессов, протекающих в предметной области.

Эти знания объясняют явления и могут использоваться для прогнозирования поведения объектов.

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

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

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

2.2. Модели представления знаний Существуют десятки моделей (или языков) представления знаний для различных предметных областей. Большинство из них может быть сведено к следующим классам:

продукционные модели;

семантические сети;

формальные логические модели.

Коротко охарактеризуем каждую из этих моделей.

2.2.1. Продукционная модель Продукционная модель или модель, основанная на правилах, позволяет представить знания в виде предложений типа Если (условие), то (действие).

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

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

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

В следующей главе мы рассмотрим эту модель более подробно.

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

Семантическая сеть это ориентированный граф, вершины которого понятия, а дуги отношения между ними.

В качестве понятий обычно выступают абстрактные или конкретные объекты, а отношения это связи типа это ( АКО A-Kind-Of, is ), имеет частью ( has part ), принадлежит, любит.

Характерной особенностью семантических сетей является обязательное наличие трех типов отношений:

класс элемент класса (класс работников менеджер);

свойство значение (образование высшее);

пример элемента класса (менеджер Иванов И.И.).

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

1. По количеству типов отношений:

а) однородные (с единственным типом отношений);

б) неоднородные (с различными типами отношений).

2. По типам отношений:

а) бинарные (в которых отношения связывают два объекта);

б) n-арные (в которых есть специальные отношения, связывающие более двух понятий).

Наиболее часто в семантических сетях используются следующие отношения:

связи типа часть целое ( класс подкласс, элемент множество,... );

функциональные связи (определяемые обычно глаголами производит, количественные (больше, меньше, равно,... );

пространственные (далеко от, близко от, за, под, над,... );

временные (раньше, позже, в течение,... );

атрибутивные связи (иметь свойство, иметь значение);

логические связи (и, или, не);

лингвистические связи.

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

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

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

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

2.2.3. Фреймы Термин фрейм (от английского frame, что означает каркас или рамка ) был предложен Марвином Минским, одним из пионеров ИИ, в 70-е годы двадцатого века для обозначения структуры знаний для восприятия пространственных сцен. Эта модель, как и семантическая сеть, имеет глубокое психологическое обоснование.

Фрейм это абстрактный образ для представления некоего стереотипа восприятия.

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

В теории фреймов такой образ комнаты называется фреймом комнаты.

Фреймом также называется и формализованная модель для отображения образа.

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

фреймы-роли (менеджер, кассир, клиент);

фреймы-сценарии (банкротство, собрание акционеров, именины);

фреймы-ситуации (тревога, авария, рабочий режим устройства).

Традиционно структура фрейма может быть представлена как список свойств:

(ИМЯ ФРЕЙМА:

(имя 1-го слота: значение 1-го слота), (имя 2-го слота: значение 2-го слота),

(имя N-го слота: значение N-го слота) В табл. 1 представлена та же запись, дополненная двумя столбцами. Дополнительные столбцы предназначены для описания способа получения слотом его значения и возможного присоединения к тому или иному слоту специальных процедур, что допускается в теории фреймов. В качестве значения слота может выступать имя другого фрейма, так образуются сети фреймов.

Имя слота Значение слота Способ получения Присоединенная Существует несколько способов получения слотом значений во фреймеэкземпляре:

по умолчанию от фрейма-образца (Default-значение);

через наследование свойств от фрейма, указанного в слоте АКО;

по формуле, указанной в слоте;

через присоединенную процедуру;

явно из диалога с пользователем;

Важнейшим свойством теории фреймов является заимствование из теории семантических сетей так называемое наследование свойств. И во фреймах, и в семантических сетях наследование происходит по АКО-связям (A-Kind-Of = это). Слот АКО указывает на фрейм более высокого уровня иерархии, откуда неявно наследуются, то есть переносятся, значения аналогичных слотов.

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

2.2.4. Формальные логические модели Традиционно в представлении знаний выделяют формальные логические модели, основанные на классическом исчислении предикатов I-го порядка, когда предметная область или задача описывается в виде набора аксиом.

В основе логических моделей лежит понятие формальной теории, задаваемой четверкой S = B, F, A, R, где B счетное множество базовых символов (алфавит) теории S;

F подмножество S, называемых формулами теории (под выражениями понимаются конечные последовательности базовых символов теории S). Обычно существует эффективная процедура (множество синтаксических правил), позволяющая строить из B синтаксически правильные выражения формулы;

A выделенное множество формул, называемых аксиомами теории S, т.е. множество априорно истинных формул;

R конечное множество отношений r1,..., rn между формулами, называемыми правилами вывода.

Для каждого ri существует целое положительное число j, такое, что для каждого множества, состоящего из j формул, и для каждой формулы f эффективно решается вопрос о том, находятся ли данные j формул в отношении ri с формулой f. Если отношение ri выполняется, то f называется непосредственным следствием данных j формул по правилу ri. Следствием (выводом) формулы fn в теории S называется всякая последовательность f1,..., fn формул, такая, что для любого i формула ri есть либо аксиома теории S, либо непосредственное следствие каких-либо предыдущих формул по одному из правил вывода. Правила вывода позволяют расширять множество формул, которые считаются истинными в рамках данной теории.

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

Формальная система S называется непротиворечивой, если не существует формулы A, такой, что A и ¬A выводимы в S.

Наиболее распространенной формальной системой, которая используется для представления знаний, является исчисление предикатов первого порядка. Алфавит исчисления предикатов состоит из следующего набора символов:

пропозициональных связок ¬,,, ;

знаков кванторов, ;

символов переменных xk, k = 1, 2,...;

n-местных функциональных букв: fk, k 1, n 0 (fk называют константными буквами);

Из символов алфавита можно строить различные выражения. Выделяют термы, элементарные формулы (атомы) и правильно построенные формулы (или просто формулы). Всякий символ переменной или константной буквы есть терм. Если t1,..., tn (n 1) термы, то и fk (t1,..., tn ) является термом.

ментарная формула (атом). Атом является правильно построенной формулой. Если A и B правильно построенные формулы, то ¬A, A B, A B, A B есть правильно построенные формулы. Если A правильно построенная формула и x переменная в A, то конструкции (x A) и (x A) правильно построенные формулы. Выражение является правильно построенной формулой, только если оно получено с соблюдением приведенных выше правил.

Для того чтобы придать формуле содержание, ее интерпретируют как утверждение, касающееся рассматриваемой предметной области. Под интерпретацией понимают всякую систему, состоящую из непустого множества D, называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве pn некоторое n-местное отношение в D;

каждой функциональной букве fk некоторую n-местную функцию, отображающую Dn D, и каждой константной букве fk некоторый элемент из D. При заданной интерпретации переменные мыслятся пробегающими все значения из области D этой интерпретации, а всякой элементарной формуле приписывается значение истинно (И) или ложно (Л). Приписывание значения элементарной формуле pn (t1,..., tn ) осуществляется по следующеk му правилу: если термы предикатной буквы соответствуют элементам из D, удовлетворяющим отношению, определяемому данной интерпретацией, то значением элементарной формулы будет истина, в противном случае ложь. Значение неэлементарной формулы вычисляется рекуррентно, исходя из значений составляющих ее формул. Очевидно, что значения формул могут быть истинными или ложными в зависимости от выбранной интерпретации.

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

Теорема 1. Пусть даны формулы B1,..., Bn и формула A. Формула A является логическим следствием B1,..., Bn тогда и только тогда, когда формула B1... Bn A общезначима, т.е. является истиной.

Напомним, что формула A логически следует из формул B1,..., Bn тогда и только тогда, когда всякая интерпретация I, удовлетворяющая B1...Bn, удовлетворяет также и A. Формулы B1,..., Bn называют посылками, а A заключением логического следования и обозначают B1,..., Bn A.

Задачей доказательства теоремы называют выяснение вопроса логического следования из заданного множества формул B1,..., Bn некоторой формулы A, что равносильно доказательству общезначимости формулы B1...

Bn A или невыполнимости формулы B1... Bn (¬A).

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

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

ДАТЬ (МИХАИЛ, ВЛАДИМИРУ, КНИГУ);

( x)( ЭЛЕМЕНТ (x, СОБЫТИЕ–ДАТЬ) ИСТОЧНИК (x, МИХАИЛ) АДРЕСАТ (x, ВЛАДИМИР) ОБЪЕКТ (x, КНИГА)).

Здесь описаны два способа записи одного факта: Михаил дал книгу Владимиру.

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

К другим недостаткам формальных систем следует отнести их монотонность, отсутствие средств для структурирования используемых элементов и недопустимость противоречий.

Стремление устранить недостатки формальных систем при их использовании в качестве моделей представления привело к появлению семиотических систем. Семиотическая система формально задается восьмеркой S = B, F, A, R, Q(B), Q(F ), Q(A), Q(R). Здесь первые четыре компонента те же, что и в определении формальной системы (см. выше), а остальные компоненты правила изменения первых четырех компонентов под влиянием накапливаемого в базе знаний интеллектуальной системы опыта о строении и функционировании сущностей в данной проблемной среде.

Мы опустим подробное описание логических моделей, т.к. исчисление предикатов 1-го порядка в промышленных экспертных системах практически не используется в силу того, что они предъявляют очень высокие требования и ограничения к предметной области.

Глава Системы продукций и стратегии поиска в пространстве состояний 3.1. Системы продукций 3.1.1. Компоненты системы продукций Система продукций (или продукционная система) состоит из трех основных элементов:

рабочей памяти;

множества продукционных правил;

системы управления.

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

Продукционное правило представляет собой пару условие действие.

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

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

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

3.1.2. Основной алгоритм системы продукций Обозначим текущее состояние рабочей памяти системы продукций через CurrentState.

Следующий алгоритм описывает взаимодействие трех компонентов продукционной системы.

function MainAlgorithm;

begin CurrentState := Start ’исходное состояние рабочей памяти until CurrentState = goal do а) выбрать некоторое правило P в множестве правил, которые применимы в состоянии CurrentState;

б) CurrentState := P(CurrentState) ’результат применения правила P к CurrentState;

end.

Пример 1. Рассмотрим простой пример работы системы продукций, которая преобразовывает строку, состоящую из символов a, b, c в соответствии со следующими правилами:

Работа такой системы продукций для начального состояния рабочей памяти acabc приведена в табл. 2.

Алгоритм MainAlgorithm является недетерминированным, т.к. в нем не указывается каким образом следует выбирать применимое правило.

Так, в примере 1 множество применимых правил на некоторых шагах состоит более чем из одного правила. Множество всех применимых в данном состоянии правил называется конфликтным множеством.

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

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

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

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

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

Чтобы поставить эту задачу, определим следующее.

Рабочая память будет содержать список городов, посещенных к данному моменту. Таким образом, исходное состояние рабочей памяти является списком [A]. Не допускается появление списков, содержащих название любого города более одного раза, кроме случая, когда после внесения в список названий всех городов A упоминается в нем вторично.

Правила продукций соответствуют решениям:

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

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

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

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

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

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

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

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

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

Граф состоит из множества (не обязательно конечного) вершин. Определенные пары вершины соединены дугами, и эти дуги направлены от одного элемента пары к другому. Такой граф называется направленным. Для наших целей вершины помечены базами данных, а дуги правилами. Если дуга направлена от вершины ni к вершине nj, то говорят, что вершина nj является преемником вершины ni, а ni родителем вершины nj. В графах, представляющих для нас интерес, у любой вершины может быть лишь конечное число преемников. (У наших систем продукций имеется лишь конечное число применимых правил.) Обе вершины в паре одновременно могут быть преемниками друг друга; в этом случае пара направленных дуг иногда заменяется ребром.

Дерево частный случай графа, в котором каждая вершина имеет не более одного родителя. Вершина дерева, не имеющая родителя, называется корневой, а не имеющая преемников концевой. Мы говорим, что корневой вершине соответствует глубина, равная нулю. Глубина любой другой вершины дерева определяется как глубина предшествующей вершины плюс 1.

Последовательность вершин ni1, ni2, ni3,..., nik, где каждая nij является преемником nij1 для j = 2,..., k, называется путем длиной k от ni1 к nik. Если существует путь от вершины ni к вершине nj, то говорят, что вершина nj достижима из вершины ni. В этом случае nj является потомком вершины ni и ni предком вершины nj.

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

Часто оказывается удобным приписать положительные стоимости дугам, чтобы отразить таким образом стоимость применения соответствующего правила. Мы используем обозначение c(ni, nj ) для стоимости дуги, направленной от вершины ni к вершине nj. (Для некоторых дальнейших рассмотрений важно, чтобы все они были больше некоторого произвольно малого положительного числа e.) Стоимость пути между двумя вершинами равна сумме стоимостей всех дуг, соединяющих вершины, лежащие на этом пути. В некоторых задачах мы хотим найти путь между двумя вершинами, имеющий минимальную стоимость.

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

Чаще, однако, встречается ситуация, где требуется найти путь между вершиной s и любой вершиной из множества {ti }, представляющего состояния рабочей памяти, удовлетворяющие терминальному условию. Это множество {ti } называют целевым и каждую вершину t в {ti } целевой.

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

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

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

Пространство состояний это четверка {N, A, S, GD}, где N есть множество вершин графа или состояний в процессе решения задачи, A есть множество дуг между вершинами, соответствующих шагам в процессе решения задачи, S есть непустое множество начальных состояний задачи, GD есть непустое подмножество N, состоящее из целевых состояний. Эти состояния могут быть описаны одним из следующих способов:

измеряемыми свойствами состояний, встречающихся в процессе поиска;

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

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

Пример 2. Рассмотрим в качестве примера систему продукций, множества правил которой приведено в табл. 3.

Пусть начальное состояние рабочей памяти Start содержит утверждение a. Граф пространства состояний для такой системы продукций приведен на рис. 5.

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

Алгоритм работает до тех пор, пока не достигнет цели либо не исследует все пространство состояний. Ниже приведен алгоритм поиска с возвратами.

В нем используются три списка, позволяющих запоминать путь от узла к узлу в пространстве состояний.

1. SL (State List) список исследованных состояний рассматриваемого пути. Если цель уже найдена, то SL содержит список состояний пути решения.

2. NSL (New State List) список новых состояний, он содержит вершины, подлежащие рассмотрению, т.е. список вершин, потомки которых еще не были порождены и рассмотрены.

3. DE (Dead Ends) список тупиков, т.е. список вершин, потомки которых уже были исследованы, но не привели к цели. Если состояние из этого списка снова встречается в процессе поиска, то оно обнаруживается в списке DE и исключается из рассмотрения.

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

Обозначим CurrentState текущее состояние при поиске с возвратами.

Состояние CurrentState всегда равно последнему из состояний, занесенных в список SL, и представляет фронтальную вершину на построенном в данный момент пути. Правила вывода, ходы в игре или иные соответствующие операторы решения задачи упорядочиваются и применяются к CurrentState. В результате возникает упорядоченное множество новых состояний, потомков CurrentState. Первый из этих потомков объявляется новым текущим состоянием, а остальные заносятся в список новых состояний NSL для дальнейшего изучения. Новое текущее состояние заносится в список состояний SL, и поиск продолжается. Если текущее состояние CurrentState не имеет потомков, то оно удаляется из списка состояний SL (именно в этот момент алгоритм возвращается назад ), и исследуется какой-либо из оставшихся потомков его предка в списке состояний SL.

function Backtrack; begin SL := [Start]; NSL := [Start]; DE := [];

while NSL [ ] do ’пока существуют неисследованные состояния if CurrentState = goal (или удовлетворяет описанию цели) ’при нахождении цели вернуть список состояний пути if CurrentState не имеет потомков (исключая узлы, входящие в DE, SL и NSL) then SL не пуст и CurrentState = первый элемент списка SL do добавить CurrentState в SL;

поместить потомок CurrentState (кроме узлов, CurrentState := первый элемент NSL;

return FAIL;

end.

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

формируется список неисследованных состояний (NSL), для того чтобы иметь возможность возвратиться к любому из них;

поддерживается список неудачных состояний (DE), чтобы оградить алгоритм от проверки бесполезных путей;

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

Пример 3. Продемонстрируем работу алгоритма поиска с возвратами на графе пространства состояний некоторой системы продукций, изображенного на рис. 6. Целевыми вершинами будем считать вершины G и H.

Тогда работа такой системы продукций в соответствии с алгоритмом Backtrack приведена в табл. 4.

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

3.2.4. Поиск в ширину Поиск в ширину осуществляется с использованием списков open и closed, позволяющих отслеживать продвижение в пространстве состояний. Список open, подобно NSL в алгоритме поиска с возвратами, содержит сгенерированные состояния, потомки которых еще не были исследованы. Порядок удаления состояний из списка open определяет порядок поиска. В список closed заносятся уже исследованные состояния. Список closed объединяет списки DE и SL, используемые в алгоритме поиска с возвратами.

function BreadthFirstSearch;

begin closed := [ ];

begin удалить крайнее слева состояние из open, скажем X;

else begin сгенерировать потомок X;

поместить X в список closed;

исключить потомок X, если он уже в списке поместить остальные потомки в правый конец списка open end.

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

Это структура данных FIFO (rst-in rst-out). Состояния добавляются в список справа, а удаляются слева. Таким образом, в поиске участвуют состояния, которые находятся в списке open дольше всего, обеспечивая поиск в ширину. Дочерние состояния, которые были уже записаны в списки open или closed, отбрасываются. Если алгоритм завершается из-за невыполнения условия цикла while (open = [ ]), то можно заключить, что весь граф исследован, а желаемая цель не достигнута. Следовательно, поиск потерпел неудачу.

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

Целевыми вершинами будем считать те, которые содержат утверждение x, т.е. вершины 6, 8 и 9. Работа алгоритма BreadthFirstSearch приведена в табл. 5.

Поскольку при поиске в ширину узлы графа рассматриваются по уровням, сначала исследуются те состояния, пути к которым короче. Поиск в ширину, таким образом, гарантирует нахождение кратчайшего пути от начального состояния к цели. Более того, поскольку вначале исследуются состояния, найденные по кратчайшему пути, при повторном проходе это состояние отбрасывается. Иногда помимо имен состояний в open и closed необходимо хранить дополнительную информацию. Например, заметим, что алгоритм поиска в ширину не поддерживает список состояний на текущем пути к цели, как это делалось при поиске с возвратами (Backtrack) в списке SL. Все посещенные состояния хранятся в closed. Если путь является решением, Рис. 7. Граф пространства состояний из примера то он возвращается алгоритмом. Это может быть сделано путем накопления информации о предках для каждого состояния. Состояние хранится вместе с записью родительского состояния, т.е. в виде пары (состояние, родитель). Когда цель найдена, алгоритм может восстановить путь решения, прослеживая его в обратном направлении от цели к начальному состоянию по родительским состояниям. Заметим, что состояние A имеет родителя nil (нуль), т.е.

является начальным состоянием. Это служит сигналом прекращения восстановления пути.

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

3.2.5. Поиск в глубину Опишем алгоритм поиска в глубину упрощенный алгоритм поиска с возвратами, уже представленный ранее. В этом алгоритме состояния-потомки добавляются и удаляются с левого конца списка open, т.е. список open реализован как стек магазинного типа или структура LIFO (last-in-rst-out, последним пришел первым обслужен ). При организации списка open в виде стека предпочтение отдается самым молодым (недавно сгенерированным состояниям), т.е. осуществляется принцип поиска в глубину.

function DepthFirstSearch;

begin closed := [ ];

удалить крайнее слева состояние из open, скажем X;

сгенерировать потомок X;

исключить потомок X, если он уже в open или closed;

поместить остальные потомки в левый конец списка open end.

Пример 5. Проследим путь алгоритма DepthFirstSearch поиска в глубину на графе, изображенном на рис. 7. Целевыми вершинами будем считать те, которые содержат утверждение x, т.е. вершины 6, 8, 9. Работа алгоритма DepthFirstSearch приведена в табл. 6.

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

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

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

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

Жадный алгоритм поиска Наиболее простой путь эвристического поиска это применение процедуры поиска экстремума (hill climbing). Стратегии, основанные на поиске экстремума, оценивают не только текущее состояние поиска, но и его потомков.

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

Методы поиска без механизмов возврата или других приемов восстановления не могут отличить локальный максимум от глобального. Существуют методы приближенного решения этой проблемы, например, случайное возмущение оценки. Однако гарантированно решать задачи с использованием техники поиска экстремума нельзя. Несмотря на эти ограничения, алгоритм поиска экстремума может быть достаточно эффективным, если оцениваюГлава 3. Системы продукций и стратегии поиска щая функция позволяет избежать локального максимума и зацикливания алгоритма. В общем, однако, эвристический поиск требует более гибкого метода, предусмотренного в жадном алгоритме поиска, где при использовании приоритетной очереди возможно восстановление алгоритма из точки локального максимума. Подобно алгоритмам поиска в глубину и алгоритмам поиска в ширину, жадный алгоритм поиска использует списки сохраненных состояний: список open отслеживает текущее состояние поиска, а в closed записываются уже проверенные состояния. На каждом шаге алгоритм записывает в список open состояние с учетом некоторой эвристической оценки его близости к цели. Таким образом, на каждой итерации рассматриваются наиболее перспективные состояния из списка open. Псевдокод для функции, реализующей жадный алгоритм поиска приведен ниже.

function BestFirstSearch;

begin closed := [ ];

удалить первое состояние X из списка open;

if X = goal, return путь от Start к X сгенерировать потомок X;

потомок не содержится в списке open или closed:

присвоить потомку эвристическое значение;

потомок уже содержится в списке open:

if потомок был достигнут по кратчайшему пути then записать это состояние в список open потомок уже содержится в списке closed:

if потомок был достигнут по кратчайшему пути then поместить X в список closed;

переупорядочить состояния в списке open в соответствии с эвристикой (лучшие слева) end.

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

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

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

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

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

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

Алгоритм А Определим оценочную функцию f так, чтобы ее значение f (n) для любой вершины n оценивало сумму стоимости пути минимальной стоимости от исходной вершины s к вершине n и стоимости аналогичного пути от вершины n к целевой. Это значит, что f (n) является оценкой стоимости пути минимальной стоимости при условии, что он проходит через вершину n. Та вершина в списке open, для которой значение f наименьшее, считается вершиной, дающей наименее жесткое ограничение, следовательно, ее целесообразно взять для очередного раскрытия.

Перед тем как продемонстрировать некоторые свойства этой оценочной функции, введем ряд полезных обозначений. Пусть функция k(ni, nj ) выражает реальную стоимость пути минимальной стоимости между двумя произвольными вершинами ni и nj. (Функция k не определена для вершин, между которыми нет пути.) Стоимость такого пути от вершины n к некоторой конкретной целевой вершине ni в этом случае равна k(n, ti ). Пусть h (n) минимум всех значений k(n, ti ) на полном множестве целевых узлов {ti }. Таким образом, h (n) стоимость пути минимальной стоимости от вершины n к целевой вершине и любой путь от вершины n к целевой, для которой достигается h (n), является оптимальным путем от n к цели. (Функция h не определена для любой вершины n, не имеющей доступа ни к одной целевой вершине.) Часто нас интересует стоимость k(s, n) оптимального пути от заданной исходной вершины s к некоторой произвольной вершине n. Чтобы несколько упростить наши обозначения, введем новую функцию g (n) = k(s, n) для всех n, доступных из s.

Далее, определим функцию f так, чтобы ее значение f (n) для любой вершины n было бы реальной стоимостью оптимального пути от вершины s к вершине n плюс стоимость оптимального пути от вершины n к целевой:

Функция f (n), следовательно, равна стоимости оптимального пути при условии, что он проходит через вершину n. (Заметим, что f (s) = h (s) это реальная стоимость оптимального пути от s к цели в отсутствие ограничений.) Мы хотим, чтобы наша оценочная функция f была оценкой f. Эта оценка дается соотношением где g оценка g и h оценка h. Очевидно, в качестве g(n) можно выбрать стоимость пути на дереве поиска от s к n, которая получается в результате суммирования стоимостей дуг, вычисленных при отслеживании указателей от n к s. (Этот путь является путем самой меньшей стоимости от s к n, найденным до сих пор алгоритмом поиска. Значение g(n) для некоторых вершин можно уменьшить, если дерево поиска видоизменяется на шаге 7.) Заметим, что такое определение подразумевает g(n) > g (n). При установлении h(n) оценки h (n) исходим из эвристической информации об области задачи. Назовем h эвристической функцией. Итак, пусть в качестве оценочной функции имеем Назовем алгоритм поиска, использующий эту оценочную функцию для упорядочения вершин, алгоритмом А. Отметим, что, когда h = 0 и g = d (глубина вершины на дереве поиска), алгоритм А идентичен поиску в ширину.

Ранее мы утверждали, что алгоритм поиска в ширину с гарантией находит путь к цели, имеющий минимальную длину. Если h является нижней границей h (т.е. (h(n)) < h (n) для всех вершин n), то алгоритм А находит оптимальный путь к цели.

3.3. Рекурсивный поиск 3.3.1. О реализации поиска в пространстве состояний Ранее были рассмотрены различные методы поиска в пространстве состояний. Этот подход пространства состояний к решению задачи позволяет использовать теорию графов для создания и анализа компьютерных программ. Был определен общий алгоритм поиска с возвратами, алгоритмы поиска в глубину и в ширину, а также эвристический поиск. Следующие понятия характеризуют данные и управляющие структуры, используемые для реализации поиска в пространстве состояний.

1. Представление решения задачи в виде пути от начального состояния к целевому.

2. Алгоритм поиска, систематически проверяющий наличие альтернативных путей к цели.

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

4. Списки, содержащие точную информацию о рассматриваемых в данный момент состояниях, в том числе:

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

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

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

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

1. Рекурсивный шаг: вызов процедуры из этой же процедуры для повторения последовательности действий.

2. Условие, которое обеспечивает выход из процедуры и таким образом предотвращает зацикливание (рекурсивная версия бесконечного цикла).

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

Простой пример алгоритм определения принадлежности данного элемента списку. Списком (list) называют упорядоченную последовательность элементов и фундаментальных строительных блоков структур данных. Списки использовались, например, для представления списков open и closed в алгоритмах поиска. Процедура проверки принадлежности элемента списку определяется так.

function member(item, list);

begin else if item = первому элементу списка then return SUCCESS tail := список после удаления первого элемента;

end.

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

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

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

3.3.3. Рекурсивный поиск Прямое преобразование описанного ранее алгоритма поиска в глубину в рекурсивную форму иллюстрирует эквивалентность рекурсии и итерационного подхода. Этот алгоритм для поддержки списка состояний использует глобальные переменные open и closed.

function DepthSearch; ’переменные open и closed глобальные begin if список open пуст then return FAIL;

CurrentState := первый элемент списка open;

if CurrentState равно целевому состоянию then return SUCCESS else open := хвост списка open;

closed := closed с добавлением CurrentState;

для каждого потомка CurrentState then добавить потомок в начало списка open end.

Поиск в ширину можно описать фактически тем же самым алгоритмом.

При этом необходимо сохранять список closed как глобальную структуру данных и рассматривать список open как очередь, а не как стек.

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

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