Системы искусственного интеллекта. Учебно-практическое пособие [В. Ю. Яньков] (doc) читать онлайн


МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ
(образован в 1953 году)

Кафедра информационных технологий

Дистанционное
обучение

Информ-05.03.2102.зчн. плн. Информ-05.03.2202.зчн. плн.
Информ-05.03.2102.зчн. скр. Информ-05.03.2202.зчн. скр.
Информ-05.03.2102.очн. плн. Информ-05.03.2202.очн. плн.
Информ-05.03.2102.очн. скр. Информ-05.03.2202.очн. скр.
Информ-05.03.2102.очн/зчн.плн. Информ-5.03.2202.очн/зчн.плн.
Информ-05.03.2102.очн/зчн.скр. Информ-5.03.2202.очн/зчн.скр.


В. Ю. ЯНЬКОВ, А.М. ИГЛИЦКИЙ
СИСТЕМЫ ИСКУССТВЕННОГО
ИНТЕЛЛЕКТА

Учебно-практическое пособие
для студентов специальностей 2102 и 2202
всех форм обучения







www.msta.ru




Москва 2004 4104



УДК 007001.33(075.8)


© Яньков В.Ю. Иглицкий А.М. Системы искусственного интеллекта. Учебно-практическое пособие. М.,МГУТУ, 2004



В учебно-практическом пособии профессора В. Ю. Янькова и доцента А.М. Иглицкого в кратком и систематическом виде изложено содержание курса «Системы искусственного интеллекта». После каждой главы даны вопросы и тесты, позволяющие контролировать степень усвоения материала. Имеется словарь основных понятий.



Пособие предназначено для студентов спец. 2102,2202 всех форм обучения.


Авторы: Яньков Владимир Юрьевич, Иглицкий Александр Михайлович.

Рецензенты:
проф. МГУПБТ, д.т.н. Сапфиров С. Г.,
проф. МГУПБТ, д.т.н. Бородин А.В.












Редактор: Свешникова Н.И.




© Московский государственный университет технологий и управления, 2004
109004, Москва, Земляной Вал,73.

СОДЕРЖАНИЕ Стр.
Введение 4
Глава 1.Основные понятия систем искусственного интеллекта 5
1.1. Основные понятия 5
1.2. Прямая и обратная цепочки рассуждений. 8
1.3. Агенты и среды 8
Вопросы для самопроверки к главе 1 11
Тесты к главе 1 11
Глава 2.Математический аппарат, используемый в задачах
искусственного интеллекта 12
2.1. Логика высказываний 12
2.1.1. Синтаксис логики высказываний 14
2.1.2. Семантика логики высказываний 14
2.1.3. Общезначимые формулы и их роль 15
2.2. Нечеткие множества 17
2.2.1.Операции с нечеткими множествами 18
Вопросы для самопроверки к главе 2 20
Тесты к главе 2 20
Глава 3. Логические рассуждения 20
3.1.Рассуждения в пространстве состояний среды 21
3.1.1. Постановка задачи 22
3.1.2. Формализация вывода средствами логики высказываний 22
3.1.3. Поиск решения 24
3.2.Нечеткий логический вывод 25
Вопросы для самопроверки к главе 3 29
Тесты к главе 3 29
Глава 4. Стратегии поиска 30
4.1. Оценки успеха при поиске цели 30
4. 2. Слепой поиск 32
4.2.1. Поиск в ширину 32
4.2.2. Монотонный поиск в ширину 33
4.2.3. Поиск в глубину 34
4.2.4. Ограниченный поиск в глубину 36
4.2.5. Итеративный поиск в глубину 36
4.2.6. Двунаправленный поиск 37
4.2.7. Сравнение стратегий поиска 38
4. 3. Направленный поиск 38
4.3.1. Поиск по критерию близости к цели 38
4.3.2. Поиск по критерию цены пути (А*-поиск) 40
4.3.3. Оптимизирующий итеративный поиск 42
Вопросы для самопроверки к главе 4 43
Тесты к главе 4 43
Ответы на тестовые задания 43
Тесты по дисциплине 44
Список рекомендуемой литературы 44
Словарь основных понятий 45




Введение
Что такое искусственный интеллект? Область знаний искусственного интеллекта пытается объяснить сущность интеллектуальных, умственных способностей человека. Искусственный интеллект занимается созданием интеллектуальных искусственных объектов с помощью компьютеров.
Сегодня системы искусственного интеллекта (СИИ) являются важнейшей составной частью в технологии современных производств.
Главная проблема, стоящая перед предприятием (в смысле управления), – это проблема преодоления сложности. Как известно, сложности управления возникают тогда, когда приходится делать выбор из множества возможных решений. Это может быть инженерный выбор решения (как проектировать данное изделие), выбор расписания (как это изделие производить) и т. д.
Управление производством требует обработки большого объема информации. Проблема получения информации с объектов, функционирующих в реальном масштабе времени, в настоящее время решена. Но это породило другую проблему: как уменьшить долю информации до того уровня, который действительно необходим для принятия решения индивидуумом? В то же время следует отметить, что потеря информации, поступающей от объектов, работающих в реальном масштабе времени, может существенно сказаться на конечном результате.
Нехватка времени на принятие решения – еще одна проблема, которая проявляется, по мере усложнения производства.
Очень важный фактор - необходимость сохранения и распределения знаний отдельных опытных экспертов, полученных ими в процессе многолетней работы и большого практического опыта. Проблема извлечения знаний и их распределения- сегодня одна из главных проблем производственных организаций.
Таким образом, видим, что все перечисленные выше условия реализации идеи автоматизации интеллектуальной деятельности человека в производственных системах управления безусловно выполняются.
Что же такое все – таки такое искусственный интеллект?
Искусственный интеллект (ИИ) — это программная система, имитирующая на компьютере мышление человека.
Система искусственного интеллекта (СИИ) – это реальная производственная система, использующая в своей работе методы искусственного интеллекта.
Структурная схема одной из возможных интеллектуальных систем приведена на рис.1
Есть производственный процесс, на который влияет шум «d». Выход этого процесса «x» измеряется измерительной системой, которой, в свою очередь, присущи измерительные шумы «η». Измеренный сигнал «y» поступает на устройство оценивания состояния объекта, с которого получают оценку «».
Эта оценка поступает как непосредственно на управляющие механизмы, так и на блок искусственного интеллекта, состоящего из базы знаний и блока вывода. Блок вырабатывает желательные значения-уставки состояния процесса и управляющего сигнала , которые и подаются на управляющие механизмы. Вне контура управления находятся эксперты, заполняющие с помощью средств заполнения базу знаний и верификатор, проверяющий истинность вывода.
Показатели оценки состояния процесса и уставок через монитор сообщаются человеку – «лицу, принимающему решение» (ЛПР), который, приняв решение, расходящееся с И.И, может вмешаться в работу управляющих механизмов и верификатора.
Переход к интеллектуальным системам целесообразен лишь там, где объектами управления являются плохо определенные объекты, не позволяющие применять к ним классические методы современной теории управления.
Как видно из рисунка, при переходе к СИИ в традиционной схеме управления вместо блоков, связанных с идентификацией и оптимизацией, появляются два новых блока – база знаний (БЗ) и механизм вывода.
Не останавливаясь на том, что такое знания и каковы формализмы их представления (это будет разъяснено в дальнейшем), заметим, что именно база знаний является главной компонентой интеллектуальных систем, отражающей опыт по управлению технологической установкой квалифицированного эксперта (или группы экспертов), накопленный им в процессе многолетней деятельности.

Глава 1.Основные понятия систем искусственного интеллекта
1.1. Основные понятия
А. Цель. Интеллектуальная деятельность всегда связана с какой-то целью. Целью называется конечный результат, на который направлены мыслительные процессы человека. При проектировании систем ИИ всегда следует помнить о цели, для достижения которой они предназначены.
Целью может быть, например, следующее:
1. Определить кратчайший путь между Москвой и Новгородом.
2. Выбрать вино, больше всего подходящее к определенной рыбе.
3. Научиться завязывать шнурки у ботинок.
4. Найти способ оценки успехов ребенка в арифметике.
Б. Факты и правила.
Человеческий мозг – это огромное хранилище знаний. Человеку свойственно приобретать новые знания и применять их к возникающим ситуациям. В общем, интеллект можно представить как совокупность фактов и способов их применения для достижения цели. Отчасти цели достигаются с помощью правил использования всех известных фактов. Приведем несколько примеров фактов и правил их использования.
Пример 1.
Факт 1. Зажженная плита – горячая.
Правило 1. ЕСЛИ положить руку на зажженную плиту, ТО можно обжечься.
Пример 2.
Факт 2. В час пик на улице много машин.
Правило 2. ЕСЛИ попытаться в час пик перейти шоссе, ТО можно попасть под машину.
Пример 3.
Факт За. Тихие, темные улицы опасны.
Факт 36. Пожилые люди обычно не совершают дерзких преступлений.
Факт Зв. Полиция защищает людей от преступников.

Рис. 1. Структурная схема СИИ АСУ ТП.
Правило За. ЕСЛИ на тихой, темной улице встретится пожилой человек, ТО можно не очень беспокоиться.
Правило 36. ЕСЛИ на тихой, темной улице вы видите полицейского, ТО можно чувствовать себя в безопасности.
В. Упрощение.
В мозгу существует сложная система, руководящая выбором правильной реакции на конкретную ситуацию. Такой выбор называется упрощением. Механизм упрощения блокирует мысли, не имеющие отношения к решаемой в данный момент задаче.
Когда человек сталкивается с какой-то ситуацией, механизм упрощения заставляет его мозг сосредоточиться только на фактах и правилах, нужных для достижения поставленной цели.
Г. Механизм вывода.
Достигая цель, человек не только приходит к решению поставленной перед ним задачи, но одновременно приобретает новые знания. Рассмотрим пример:
1.Иван и Мария — родители Юры.
2.Иван и Мария — родители Анны.
Цель заключается в том, чтобы определить, кем приходятся друг другу Юра и Анна. Механизм упрощения заставляет человека обратиться к хранящемуся в его мозгу правилу: ЕСЛИ у девочки и мальчика одни и те же родители, ТО мальчик и девочка — брат и сестра. Цель мгновенно достигнута.
Ответ на вопрос о степени родства Юры и Анны получен из известного ранее правила. Кроме того, в процессе достижения цели получен новый факт: Юра и Анна — брат и сестра.
Часть интеллекта, которая помогает извлекать новые факты, называется механизмом вывода.
Именно механизм вывода позволяет человеку учиться на опыте, так как он дает возможность генерировать новые факты из уже существующих, применяя имеющиеся знания к новой ситуации.
Д. База знаний.
Факты формулируются в виде вопросов, ответы на которые помогают человеку принять окончательное решение. Факты и правила хранятся в компьютере в так называемой базе знаний.
Е. Экспертная система.
Конкретные сферы человеческой деятельности, в которых могут применяться системы ИИ, называются предметными областями.
Примерами предметных областей могут служить оценка эффективности обучения и выбор маршрута автобуса.
Невозможно создание единой системы ИИ, охватывающей все предметные области. Для такой системы необходимо бесконечное число фактов и правил. Даже если бы такая система была создана, понадобилось бы длительное время на наполнение ее знаниям
Система ИИ, созданная для решения задач в конкретной проблемной области, называется экспертной системой. Источником знаний для наполнения экспертных систем служат люди-эксперты в соответствующей предметной области.
Когда человек сталкивается с проблемой, не все соображения для него равноценны, например, если надо попасть на работу вовремя, он не будет слишком заботиться о том, чтобы сидеть в автобусе. Можно сказать, что человек «взвешивает» различные соображения. Числа, хотя бы приближенно оценивающие тех или иных фактов, поэтому называются весами или весовыми факторами фактов.
Получив сумму весовых факторов для положительных или отрицательных ответов, можно узнать, как велики шансы на положительное или отрицательное решение задачи.
Итоговое число, оценивающее как положительные, так и отрицательные шансы, называется общим весовым фактором. Общий весовой фактор – это некоторая количественная оценка.
Весовые факторы выбираются не случайно, они представляют собой знания, полученные в результате исследования проблемной области. Работа всех экспертных систем основана строго на экспертной информации, полученной в конкретной проблемной области.
Ж. Получение данных.
После того как определены общие факты, необходимые для достижения цели, надо получить конкретные данные и присвоить значения переменным.
Прежде всего, факты следует представить в форме вопросов, ответив на которые можно получить необходимую информацию.
Программа в режиме диалога выводит на дисплей вопросы, ответы на которые будут использоваться для оценки цели.
Проинициализированные переменные становятся частью базы данных.
1.2. Прямая и обратная цепочки рассуждений.
Из сказанного выше следует, что разработка программы для И.И. состоит из:
1. Определения целей.
2. Определения фактов, имеющих отношение к этим целям.
3. Получения данных, соответствующих фактам, характерным для заданной ситуации или объекта.
4. Оценки данных, используя правила и механизм вывода.
Процесс достижения целей описанным способом называется прямой цепочкой рассуждений, т. е. цепочкой от данных к логическому заключению. Он позволяет логически переходить от одного шага к другому.
Процесс, в котором заключение используется для поиска подтверждающих его данных, называется обратной цепочкой рассуждений.
Рассмотрим пример, иллюстрирующий обратную цепочку рассуждений.
Совершено преступление: в квартире был обнаружен труп с пулевыми ранами.
Полиция начала расследование. Первое, чем поинтересовались полицейские, – кто кроме потерпевшего, имел ключ от квартиры? Они узнали, что у убитого был приятель, который часто пользовался его квартирой. Расследование показало, что друзья недавно поссорились.
Опросив свидетелей, полиция сделала вывод, что приятель потерпевшего и является вероятным убийцей (прямая цепочка рассуждений);
Но для завершения дела были необходимы неопровержимые улики. Осмотрев квартиру подозреваемого, они ничего не обнаружили. Но в соседнем переулке в мусорном баке один из полицейских нашел ружье с отпечатками пальцев подозреваемого, а баллистические эксперименты подтвердили, что человека убили из этого ружья. Преступление было раскрыто. В данном случае, получая новые данные и проверяя, согласуются ли они с изначальным заключением, полиция идентифицировало убийцу.
Здесь заключение использовалось для поиска подтверждающих его данных, т.е. была проведена обратная цепочка рассуждений.
Заключение – это подозреваемый, а данные – это оружие.
1.3. Агенты и среды.
Искусственный интеллект занимается созданием интеллектуальных сущностей, объектов, которые принято называть агентами или носителями.
Агент воспринимает внешнюю среду с помощью датчиков x 1,x2 ,….,xm и воздействует на нее посредством исполнительных органов z1,z2,….,zn , подобно тому, как человек воспринимает внешнюю среду или просто среду с помощью органов чувств и воздействует на нее с помощью таких частей тела, как руки, ноги и т.п. В понятия датчиков и исполнительных органов закладывают самый широкий смысл. Например, датчиком может быть некий аналог уха, воспринимающий речевые сообщения, а исполнительным органом — органы речи, позволяющие передавать сообщения на каком-либо языке. Обычно воздействие агента на среду называют реакцией, а восприятие агентом среды – восприятием.
Если каждый исполнительный орган zj сопоставить с одноименной выходной переменной zj, принимающей множество значений γj, и каждое такое значение назвать микрореакцией, то реакция будет представлять собой набор значений γ1, γ2, ….γn
Аналогично, если каждый датчик хi сопоставить с одноименной входной переменной хi, принимающей множество значений αi, называемых микровосприятиями, то восприятие будет представлять собой набор значений α1, α2,…αm.
Поведение агента состоит в переработке восприятий в реакции. Эта переработка осуществляется агентом с помощью специального решателя, функционирующего на основе заложенных в него знаний.
Не существует какой-либо общепринятой классификации агентов. В зависимости от сложности решаемых задач выделим следующие четыре типа агентов: комбинационные; последовательностные; целенаправленные; целевыбирающие.
А) Поведение комбинационного агента внешне выглядит достаточно простым. В определенный момент времени t агент получает с датчиков x 1..., х m восприятие α1 ,α2,…., αm, характеризующее состояние среды.
На основании только этого восприятия и неизменяемых в процессе всего существования агента знаний, хранящихся в его памяти, он в этот же момент времени с помощью исполнительных органов z1, z2,…,zn формирует реакцию γ1, γ2, ….γn. Конечно, при практической реализации агента на формирование реакции по данному восприятию требуется время, но теоретически считается, что все происходит мгновенно в момент времени t, и этот момент времени нас может даже не интересовать. Существенно лишь то, что комбинационный агент не порождает новые знания. Каждый раз, когда надо вырабатывать очередную реакцию по вновь поступившему восприятию, он использует одни и те же знания, хранящиеся в его памяти.
Б) Агентов, которые используют запомненную в предыдущие моменты времени информацию, называют последовательностными.
В) Поведение целенаправленного агента принципиально отличается от комбинационного и последовательностного, поскольку их поведение основано на восприятиях в настоящий или предыдущий момент времени и использовании правил, учитывающих только эти восприятия или производные от них состояния.
Целенаправленный же агент прежде, чем принять решение, на основании известной ему цели (в нашем примере места назначения и времени, к которому он туда должен прибыть) заранее планирует свои реакции. Иными словами, на основании имеющихся у него правил агент заранее до того, как он начнет действовать, пытается построить план, гарантирующий ему достижение цели, или обнаруживает, что такого плана не существует. В случае обнаружения недостижимости цели он может запросить дополнительные правила и продолжить или повторить процесс поиска. План является последовательностью пар восприятие-реакция (или только реакций), называемых также действиями и ведущих к цели. Если план найден, то целенаправленный агент его выполняет и достигает цели.
Таким образом, решатель целенаправленного агента использует не раз и навсегда данное ему множество правил, предписывающих, какие реакции выдавать в ответ на восприятия, а всякий раз для каждой вновь возникающей цели порождает план достижения именно этой цели. Исходными для работы такого решателя могут быть также правила, описывающие не реакции агента на конкретные восприятия, а некие общие законы его поведения в среде, законы поведения самой среды и законы порождения планов достижения целей.
Г) Целевыбирающий агент, помимо возможности построения планов достижения целей, так же, как это делает целенаправленный агент, способен на большее.
Во-первых, при наличии одной цели он может выбирать из множества всех конкурирующих планов достижения цели наилучший, иногда и без полного построения всех планов.
Во-вторых, при наличии нескольких конкурирующих целей, достижение каждой из которых заранее нельзя оценить с полной уверенностью, он способен определить степень успеха достижения каждой цели в зависимости от ее важности.
В-третьих, на основании предшествующего опыта, он может обучаться и корректировать или пополнять свои знания.
Агент всегда функционирует в некоторой среде. От свойств конкретной среды зависит выбор типа агентов и всего, что ему необходимо для успешного функционирования в этой среде.
Рассмотрим в общих чертах свойства сред в виде взаимоисключающих пар.
А) Существуют дискретные и непрерывные среды.
Дискретные среды таковы, что число различных восприятий и реакций, которые требуются агенту при функционировании в среде, конечно.
Непрерывные среды могут порождать бесконечное число восприятий, реакций или того и другого. Примером дискретной среды является, например, среда шахмат, а непрерывной – среда агента-водителя, если для его функционирования требуется восприятие значения, например, скорости со сколь угодно высокой точностью. Если же все параметры среды воспринимаются агентом (как это обычно бывает на практике) с определенной точностью и в заданных пределах, например, скорость с точностью до 1 км/ч в пределах от 1 до 200 км/ч, то такая среда с точки зрения агента также может считаться дискретной.
Б) Различают детерминированные и недетерминированные среды.
В детерминированных средах по любому восприятию агент формирует строго одну реакцию. Недетерминированные же среды таковы, что вследствие каких-либо причин, например недоступности всех необходимых восприятий, агент не в состоянии сформировать единственную реакцию.
Кроме того различают статические и динамические среды.
В) Среда является статической, если за время, протекающее между получением агентом любого восприятия и выработкой им реакции, в среде ничего не изменяется. В противном случае среда называется динамической. При функционировании агента в статической среде необязательно, чтобы он наблюдал за ней, пока занимается выработкой реакции. Но даже если среда является динамической, на практике чаще всего считается, что для агента неважно, какие изменения в ней происходят, пока он вырабатывает реакцию. Агент игнорирует эти изменения, считая динамическую среду статической.
Предмет искусственного интеллекта – наука о создании агентов, а под СИИ понимается сообщество агентов, способных решать интеллектуальные задачи в средах.
Предполагается, что создание агента любого типа осуществляется человеком, и он всегда способен решать задачи суперагента любого уровня. Процесс создания агента сам по себе неформален и качество описания, выражающееся в степени адекватности поведения получаемого агента задуманному, зависит от учета создателем всех необходимых аспектов его будущего поведения. Иначе говоря, создатель агента должен включить в его описание все правила, необходимые для задуманного поведения. Совокупность всех таких правил называют базой знаний агента.
Эту базу знаний можно представить в некотором формальном языке, в частности, языке логики.
В ответ на свое восприятие агент с помощью логических рассуждений на основе знаний, хранящихся в базе знаний, способен вырабатывать реакции. Механизм рассуждений зависит от типа агента и от языка представления базы знаний.
Логические рассуждения.
Рассуждением или умозаключением обычно называют ряд мыслей, изложенных в логически последовательной форме.
Агент должен уметь находить интересующие его состояния среды (целевые состояния), если он что-либо знает о других ее состояниях. Определение целевых состояний осуществляется с помощью поиска или рассуждений в пространстве состояний.
Вопросы для самопроверки к главе 1:
1.Каковы причины появления производственных систем искусственного интеллекта?
2.Каким образом системы искусственного интеллекта используют знания, накопленные человечеством в той или иной предметной области?
3.Получает ли человек в результате логических рассуждений новые знания?
4.Какими могут быть цели систем искусственного интеллекта?
5.Какие типы агентов Вы знаете?
Тесты к главе 1:
1.Искусственный интеллект – это:
А) набор формул, Б) производственная система, В) компьютерная программа.
2.Вывод – это
А) приобретение новых знаний, Б) упорядочение имеющихся знаний,
В) не имеет отношения к знаниям.
3.Экспертная система – это
А) набор формул, Б) набор правил, В) набор экспертов.
4.Прямая цепочка рассуждений – это
А) рассуждения от данных к логическому заключению,
Б) от заключения к подтверждающим его данным,
В) достижение целей любым способом.
5.Агент – это
А) человек, Б) среда, В) объект.

Глава 2. Математический аппарат, используемый
в задачах искусственного интеллекта.
При создании СИИ используются главным образом три раздела математики: ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ, ПРЕДИКАТЫ и НЕЧЕТКИЕ МНОЖЕСТВА. С помощью исчисления выск5азываний и теории предикатов обычные предложения на русском языке можно записать в компактной математической форме. Теория нечетких множеств позволяет решать задачи, когда мы не можем провести точное решение.
2.1. Логика высказываний.
В предыдущей главе показано, что рассуждения агента (поиск решений задачи) сводится к определению правил перехода в соответствии с выбранной стратегией. Каждый шаг состоит в проверке агентом истинности левой части правила (факта нахождения среды в состоянии bi и допустимости действия сj) и, в случае ее истинности, признании факта перехода из состояния bi в состояние bk в результате действия сj. Естественно, нам хотелось бы иметь математический аппарат, на основе которого можно осуществлять постановку и поиск решения задачи формально, используя наилучшую стратегию поиска. Логика высказываний – это первый шаг к созданию такого аппарата.
Осуществить постановку задачи формально – значит, имея некий формальный язык, выразить на нем все знания о среде, необходимые для решения задачи. Формальный язык в соответствии с современными представлениями требует рассмотрения двух его неотъемлемых частей: синтаксиса и семантики. Синтаксис языка описывает допустимые в языке предложения, состоящие из цепочек (последовательностей) символов, принадлежащих определенному множеству, называемому алфавитом. Синтаксис языка позволяет отличать предложения, принадлежащие языку, от предложений, ему не принадлежащих. Семантика языка определяет смысл этих предложений, сопоставляя символы языка с объектами реального мира, а предложения-отношения между объектами. Без семантики предложения языка являются ничего не значащими для агента цепочками символов. Семантика логики высказываний позволяет подразделять все множество допустимых предложений на истинные и ложные. Истинные – это те предложения, которые соответствуют имеющим место фактам или отношениям, а ложные – не имеющим. Решать задачу формально – значит иметь множество правил и стратегию их использования, которые позволяют осуществить вывод одних синтаксически правильных истинных предложений из других синтаксически правильных истинных или предполагаемых истинными.
Исчисление высказываний (другие названия – алгебра логики, двоичная алгебра, алгебра Буля) рассматривает операции над переменными, которые могут принимать только два значения: 0 и 1. Алгебра логики позволяет формализовать (записывать в виде формул) логические рассуждения. В этих рассуждениях оперируют понятиями истина и ложь. Понятие истина при этом обозначается 1, ложь – 0.
Функции алгебры логики – двоичные функции удобно формировать и исследовать с помощью специальных таблиц – таблиц истинности, в которых перечисляются все возможные значения одного или нескольких переменных. В таблице 2.1 представлены все возможные двоичные функции одной переменной.






Первая и последняя функции являются константами, вторая – повторяет x, а вот третья, значения которой противоположны значениям х, широко используется в алгебре логики и называется отрицанием х , или инверсией, или просто функцией НЕ х. Других, кроме перечисленных функций одной переменной в алгебре логики не существует.
Функций двух переменных имеется 16, некоторые, наиболее часто используемые, приведены в таблице истинности 2.2.
Первая из этих функций называется логическим сложением или ДИЗЪЮНКЦИЕЙ или просто функцией ИЛИ. Часто её обозначают знаком +.
Вторая функция – логическое умножение или конъюнкция или функция И. Её часто обозначают знаком умножения – точкой.
Третья, четвертая и пятая функции называются, соответственно импликацией, сложением по модулю 2 и эквивалентностью.

Таблица 2.2
Значения
аргументов
Значения функций
x1
x2
y=x1x2 OR
y=x1x2
AND
y=x1x2
y=x1x2=x1x2
XOR
y=x1~x2
0
0
0
0
1
0
0
0
1
1
0
1
1
1
1
0
1
0
0
1
1
1
1
1
1
1
0
0
Импликация обращается в нуль, только если значение второго элемента меньше значения первого.
Функция эквивалентности равна 1 при совпадении значений обоих аргументов, а функция сложения по модулю 2 при их несовпадении.
Существуют логические функции трех, четырех и т.д. аргументов. Например,
y=x1x2 x3, y=(x1x2) x3, y=(x1x2)(((x2x1)3)~3).
Первое выражение можно прочесть так: если x1 или x2 или x3 истинно (равно 1), то и y истинно (равно1).
Интерпретация второго выражения: если истинны x1 и x2 , или истинно x3, то y истинно.
Третье выражение можно прочесть так: Y истинно, если x1x2 при одновременном несовпадении x3 (отрицание x3) c логическим произведением: x1 не совпадает с x2 на не x3.
2.1.1. Синтаксис логики высказываний
Синтаксис логики высказываний прост и имеет прямые синтаксические и семантические аналоги в естественных языках, что чрезвычайно облегчает нам понимание логики высказываний. Символами языка логики высказываний, составляющими ее алфавит, являются логические константы ИСТИНА и ЛОЖЬ, сокращенно обозначаемые буквами И и Л, логические переменные х, у, z, обозначаемые строчными буквами латинского алфавита, логические связки (И), (ИЛИ), (НЕ), ЭКВИВАЛЕНТНО, => (ВЛЕЧЕТ) и круглые скобки. Значениями логических переменных являются логические константы. Предложения языка логики высказываний, называемые также формулами или высказываниями, составляют в соответствии со следующими правилами:
Логические константы являются простыми предложениями;
Логические переменные также простые предложения;
Сложные предложения формируются из простых с помощью связок (И), (ИЛИ), (НЕ), (ЭКВИВАЛЕНТНО), => (ВЛЕЧЕТ);
Простые и сложные предложения, заключенные или не заключенные в скобки, являются предложениями языка логики высказываний;
Из предложений с помощью связок и скобок можно образовать новые предложения языка логики высказываний;
Связки имеют следующий порядок старшинства ,,,, т.е. связка  самая старшая, а связка  самая младшая.
Формулы логики высказываний, составленные по этим правилам, называют правильно построенными формулами или сокращенно формулами.
2.1.2. Семантика логики высказываний.
Семантику логики высказываний можно пояснить смысловой интерпретацией ее предложений или формул, под которой обычно понимают процесс установления соответствия между логическими переменными и изменяющимися свойствами объектов среды и между значениями переменных (константами) и конкретными значениями свойств объектов. С помощью алгебры логики можно записывать любое правило и предложение для СИИ..
Пример 1. Студент, который не ходит на занятия и не занимается дома, не сдаст экзамен. Обозначим через x1 событие: ходить на занятия; через x2 событие – заниматься дома и через y – сдать экзамен. Тогда формальная запись на языке алгебры логике будет иметь вид:
y=x1 x2
Пример 2. Если истинно утверждение, что Иван и Мария являются родителями и Юры и Анны, то Юра и Анна являются братом и сестрой. Обозначим: x1 – Иван, x2 – Мария, x3 – Юра, x4 – Анна, y1 – родители Юры, y2 – родители Анны, y – Юра и Анна – брат и сестра.
y1=x1x2, y2=x1x2, y=y1y2.
То же самое можно описать словами:
“Родители_Юры”=”Иван””Мария”
“Родители_Анны”=”Иван””Мария”
“Юра_и_Мария – брат_и_сестра”=”Родители_Юры””Родители_Анны”
Иначе говоря, интерпретация определяет семантику формул (предложений, высказываний) путем сопоставления переменных в формулах со свойствами объектов среды, а отношений между этими свойствами — с формулами. Это позволяет по значению формул после подстановки вместо переменных конкретных значений свойств судить о наличии или отсутствии у среды тех или иных совокупных свойств или отношений. Если дана какая-либо формула, то подстановка в формулу констант вместо ее переменных называется конкретизацией. Таким образом конкретизация является результатом интерпретации.
Будем полагать, что, употребляя формулу xy, мы вкладываем в нее смысл, вытекающий из следующего предложения: «Мы заявляем, что истинность высказывания «х влечет у» означает, что истинность х влечет истинность у, а больше мы ничего не заявляем».
Истинностные значения любой формулы, т.е. ее семантику, всегда можно задать таблицей, состоящей из двух частей: в левой части таблицы перечислены все наборы значений аргументов, а в правой соответствующие наборам значения формулы. Задание таких таблиц для связок облегчается тем, что значениями аргументов и формул являются только две величины – И или Л. Такие таблицы в логике высказываний называют таблицами истинности.
Если формула интерпретирована, то ее таблица истинности определяет семантику интерпретированной формулы, поскольку по ней можем всегда определить, какие же отношения между свойствами объектов, обозначаемых переменными, имеют место (формула истинна) и не имеют места (формула ложна).
С помощью алгебры логики можно записывать любое правило и предложение для СИИ.
2.1.3. Общезначимые формулы и их роль.
Формулы, истинные на всех наборах значений своих аргументов, называют общезначимыми формулами. Если какая-либо формула  является общезначимой, то этот факт обычно записывается с использованием знака общезначимости =который ставится перед формулой: |=. Проверку формулы на общезначимость можно осуществить с помощью таблицы истинности: если формула истинна во всех строках таблицы истинности, то эта формула общезначима. Рассмотрим, например, формулу x(yy)xx. Из таблицы ясно, что формула является общезначимой, т.к. значения переменных в последнем столбце всегда истинно.






Ранее было заявлено, что истинность высказывания 12 всегда означает, что истинность 1 влечет истинность 2 (здесь 1 и 2 являются формулами логики высказываний). Потому, установив факт общезначимости формулы 12 и истинности 1, всегда можно сделать заключение об истинности 2. Таким образом, общезначимость формул вида 12, называемых импликативными формулами, является важным свойством для получения заключения об истинности 2 , называемого заключением, при истинности 1, называемого посылкой. Для простоты импликативные формулы 12 будем называть так же, как и связку , импликацией. В логике высказываний известно много общезначимых формул, называемых обычно законами логики высказываний. Наиболее известными являются следующие законы.
Коммутативные: x1x2=x2x1, x1x2=x2x1;
Дистрибутивные: x1 (x2x3)=(x1x2)(x1x3), x1(x2x3)=(x1x2)(x1x3);
Ассоциативные: x1(x2 x3)=(x1x2)x3, и x1(x2x3)=(x1x2)x3;
законы Де Моргана:
=,=,
закон двойного отрицания:.
Кроме того, справедливы следующие соотношения:
, . , ,
Сложные формулы, как правило, можно упростить. Для этого можно использовать следующие эквивалентности:
– правила поглощения,
– правило склеивания,
– правило вычеркивания.
Их доказательства осуществляются путем построения соответствующих таблиц истинности.
Рассмотрим пример упрощения логической функции. Пусть

Последовательное применение приведенных выше правил дает:
= =
=()=()=1.
Кроме общезначимых, существуют формулы выполнимые и невыполнимые. Формула называется выполнимой, если существуют наборы значений ее аргументов, на которых она принимает истинное значение, и наборы значений, на которых она принимает ложное значение.
Если формула на всех наборах значений ее аргументов принимает ложное значение, то она называется невыполнимой.
Установление истинности следствия по общезначимой импликативной формуле достаточно универсальный способ для вывода заключений, но требует проверки общезначимости последней. Если формула 1  2 не является общезначимой, то подобного заключения делать нельзя.
Проверку общезначимости можно осуществить с помощью таблицы истинности. Однако построение таблиц истинности слишком трудоемко для того, чтобы можно было решать реальные задачи. Вместо этого используют специальные правила вывода, применение которых базируется не на понятии общезначимости формулы, в частности общезначимости импликативной формулы, а на понятии модели формулы.
2.2. Нечеткие множества
Записывая и решая задачу на языке исчисления высказываний или предикатов, мы получаем ответ в виде «да» или «нет»,(истина или ложь, 0 или 1). Однако во многих задачах мы не уверены в исходных данных, мы знаем их приближенно и поэтому удовлетворимся приближенным ответом.
Для математического решения таких задач используется нечеткая логика, предложенная американским математиком Л. Заде в начале 60-х годов.
Обычная логика, в которой есть два логических значения ИСТИНА и ЛОЖЬ, связана с таким же четким разделением объектов на два множества. Например, логическое условие
ПРИЗЫВНИК = ((ПОЛ = МУЖСКОЙ)  (ВОЗРАСТ>ПРИЗЫВНОЙ))
подразумевает разделение людей по признаку пола МУЖСКОЙ/ЖЕНСКИЙ и по возрасту ВОЗРАСТ>ПРИЗЫВНОЙ/ ВОЗРАСТ<ПРИЗЫВНОЙ. Логическая операция конъюнкции описывает ПРИЗЫВНИКА как пересечение множеств:




Рис.2.1.Операция пересечения множеств
Вместе с тем во многих случаях приходится иметь дело с не столь определенными понятиями. Например, выражение МОЛОДОЙ ЧЕЛОВЕК не указывает точно ни на какой возраст. Правда, можно отметить, что возраст 10 лет под понятие МОЛОДОГО ЧЕЛОВЕКА. по-видимому, не подпадает, точно так же, как и возраст 50 лет. Однако точно указать диапазон возраста МОЛОДОГО ЧЕЛОВЕКА в виде условия
МОЛОДОЙ ЧЕЛОВЕК=((ВОЗРАСТ>МИНИМАЛЬНЫЙ) И (ВОЗРАСТ< МАКСИМАЛЬНЫЙ)) невозможно – множество возрастов, подпадающих под понятие МОЛОДОГО ЧЕЛОВЕКА, является нечетким.
Если считать, что принадлежность объекта множеству описывается функцией принадлежности, принимающей значения от 0 до 1, то разница между обычными (четкими) и нечеткими множествами состоит в следующем. Для четкого множества функция принадлежности принимает значения только 0 и 1.
Например, функция принадлежности к призывному возрасту P(y) имеет вид (рис.2.2). В случае же нечеткого множества функция принадлежности принимает и промежуточные значения. Например, функция принадлежности к множеству МОЛОДОЙ ЧЕЛОВЕК может иметь вид (рис.2.3).









Рис.2.2. Функция принадлежности четкого множества.






Рис.2.3. Функция принадлежности нечеткого множества
и в таком случае описывается формулами:
при y<15 P(y)=0;
при 15 при 20 при 25 при y>30 P(y) = 0.
Иными словами, при возрасте менее 15 и старше 30 лет человек молодым заведомо не является, а в промежутке от 20 до 25 лет - заведомо является. В промежутке от 15 до 20 лет статус МОЛОДОГО ЧЕЛОВЕКА плавно возрастает, принимая значения от 0 до 1, а в промежутке от 25 до 30 лет - убывает от 1 до 0.
Для того, чтобы описать нечеткое множество МОЛОДОЙ ЧЕЛОВЕК, следует указать все его элементы с указанием степени принадлежности элемента множеству. Это делается с помощью записи
МЧ=0.2/16+0.4/17+0.6/18+0.8/19+1/20+1/21+1/22+1/23+1/24+1/25+0.8/26+0.6/27+0.4/28+0.2/29
В тех случаях, когда это не может привести к путанице, можно использовать обычное обозначение коэффициентов, принятое в алгебре. Например, если множество Z состоит из элементов a, b, c, d, e с функцией принадлежности
Z = 0.1/a+0.5/b+0.9/c+0.7/d+0.5/e
это может быть также записано во форме
Z = 0.1a+0.5b+0.9c+0.7d+0.5e
2.2.1. Операции с нечеткими множествами.
К нечетким множествам, как и к четким, применимы операции объединения, пересечения и дополнения. Если считать, что в универсальном множестве U выделены два нечетких множества A и B с функциями принадлежности f и g, то их объединение имеет функцию принадлежности h
h(u) = max (f(u), g(u))
Например, если
U = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
A = 0.8/0+0.7/1+0.6/2+0.4/3+0.2/4+0.1/5+0.1/6+0.1/7
B = 0.1/3+0.3/5+0.5/7+0.7/8+0.9/9
то A  B имеет вид
A  B = 0.8/0+0.7/1+0.6/2+0.4/3+0.2/4+0.3/5+0.1/6+0.5/7+0.7/8+0.9/9





Аналогично, функция принадлежности для пересечения нечетких множеств A и B имеет вид min (f(u), g(u)). В том же примере
A  B = 0.1/3+0.1/5+0.1/7
Дополнение множества имеет функцию принадлежности, вычисляемую как дополнение до 1 функции принадлежности исходного множества. Так, дополнение множества A имеет функцию принадлежности
A = 0.2/0+0.3/1+0.4/2+0.6/3+0.8/4+0.9/5+0.9/6+0.9/7+1/8+1/9





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





НЕЧЕТКАЯ ЛОГИКА
В отличие от обычной логики, где существуют только два значения истинности утверждения ИСТИНА и ЛОЖЬ, в нечеткой логике "значение истинности" утверждения может принимать и промежуточные значения. Считается, что ИСТИНА имеет значение 1, ЛОЖЬ - 0, и истинность любого утверждения u, обозначаемая (u), находится в промежутке между этими значениями.
В нечеткой логике существуют те же логические операции конъюнкции, дизъюнкции и отрицания, однако они определяются иначе, чем в обычной логике. Если истинность логических операций конъюнкции, дизъюнкции и отрицания в обычной логике задается таблицами истинности, то в нечеткой логике она задается формулами. Если истинность утверждения u равна (u), а v - (v), то истинность конъюнкции, дизъюнкции и отрицания выражается формулами
(uv) =min((u), (v)), (u  v) = max ((u), (v))
(u) = 1-(u)
При этом свойства нечетких операций в значительной степени сходны со свойствами операций в обычной логике, в частности:
(uv)=(vu), (uv)=(vu)
((uv)w)=(u(vw)), ((uv)w)=(u(vw))
((u))=(u), ((uv))=(uv)
((uv))=(uv), ((uv)w)=((uw)(vw))
((uv)w)=((uw) (v  w)), (0u)=(u)
(1u)=1, (0u)=0, (1u)=(u)
(Однако аналогия не является полной - например, аналоги формул uu=0 и uu=1 в нечеткой логике неверны.)
Используемые в логическом выводе формулы импликации вида A  B также могут быть нечеткими, т.е. их уровень истинности может быть меньше 1. В этом случае уровень истинности заключения вычисляется как произведение уровня истинности посылки на уровень истинности импликации. Например, если (A)=0.9, а (AB) = 0.8, то (B)=0.72.
Вопросы для самопроверки к главе 2:
1.Могут ли системы искусственного интеллекта создаваться на одном из алгоритмических языков, например Бейсике?
2.Каким образом на языке исчисления высказываний можно записать выражение «студент должен сдать экзамены по математике и физике или по литературе и истории»?
3.Может ли функция принадлежности быть равна 3?
4.Сколько функций трех переменных существует в исчислении высказываний?
5. Запишите функцию эквивалентности через функции конъюнкции, дизъюнкции и отрицания.
Тесты к главе 2
1.Исчисление высказыванийоперирует
А) с троичными переменными, Б) с двоичными переменными,
В) с однозначными переменными.
2. Свойства исчисления высказываний доказываются с помощью
А) логического вывода ,Б) таблиц истинности, В) формул.
3.Число логических функций
А) бесконечно, Б) конечно, но не зависит от числа аргументов
В) зависит от числа аргументов.
4.Логическое сложение двух единиц равно
А) нулю, Б) двум, В) единице.
5.Функция принадлежности объединения двух нечетких множеств равна
А) максимуму функции принадлежности каждого множества
Б) функции принадлежности одного из множеств
В) минимуму функции принадлежности каждого множества.

Глава 3. Логические рассуждения.
Рассуждением или умозаключением обычно называют ряд мыслей, изложенных в логически последовательной форме.
Агент должен уметь находить интересующие его состояния среды (целевые состояния), если он что-либо знает о других ее состояниях. Определение целевых состояний осуществляется с помощью поиска или рассуждений в пространстве состояний.
3.1.Рассуждения в пространстве состояний среды.
В коммунальной квартире две старушки занимают по комнате. Комнаты находятся в общем коридоре, который имеет выход на лестничную клетку. Одна из комнат расположена слева (левая комната) от выхода, а другая – справа (правая комната). В коридоре живет кот, которого обе старушки одинаково любят и балуют, оставляя ему кусочки сыра. Каждая старушка кладет кусочек сыра у двери своей комнаты. Кот отдыхает либо у левой комнаты (слева), либо у правой (справа).
Множество всех состояний этой среды (среды кота) можно представить табл. 3.1, в столбцах которой для каждого состояния среды указаны - местонахождение кота (слева или справа), наличие или отсутствие кусочка сыра (да или нет) у соответствующей комнаты.


Таблица 3.1
Состояние
Местонахождение кота
Наличие сыра


слева
справа
b1
Слева
Да
Да
b2
Справа
Да
Да
b3
Слева
Да
Нет
b4
Справа
Да
Нет
b5
Слева
Нет
Да
b6
Справа
Нет
Да
b7
Слева
Нет
Нет
B8
Справа
Нет
Нет
Состояние b1 означает, что кот находится около левой комнаты и около обеих комнат лежит по кусочку сыра, состояние b2 — кот находится около правой комнаты и около обеих комнат снова лежит по кусочку сыра и т.д.
Кот может совершать в один и тот же момент времени только одно из следующих действий: переходить к дверям левой комнаты, переходить к дверям правой комнаты и съедать кусочек сыра около той комнаты, где он находится.
Эти действия обозначим с1=Идти налево, с2=Идти направо и с3=Съесть, соответственно. Если среда находится в одном из состояний, перечисленных в табл. 3.1, и кот совершает какое-либо из действий, то нетрудно определить в какое состояние после выполнения действия перейдет среда.
Будем полагать, что нам известно состояние, называемое начальным, с которого могут начаться изменения среды при действиях кота.
Пусть, например это будет состояние b1. Будем изображать состояния кружочками с обозначением состояния внутри кружочка.
Переход из одного состояния в другое, происходящий в результате действия, будем изображать стрелкой, ведущей в это другое состояние и помеченной соответствующим действием. Так, на рис.3.1 изображены все переходы из состояния b1 в результате действий с1,с2 , с3 .
На рис. 3.2 показано дерево всех дальнейших переходов, являющееся продолжением элементарного дерева на рис. 3.1. Построение каждой ветви дерева прекращено на том состоянии, которое встречается повторно на пути, ведущем в него из начального состояния.





Рис. 3.1. Допустимые переходы из начального состояния b1


Рис. 3.2. Дерево переходов
3.1.1. Постановка задачи
Цель кота — не оставить ни одного кусочка сыра, где бы он изначально ни находился. В терминах состояний среды целью кота является перевод ее с помощью своих действий (реакций) в одно из состояний b7 или b8. Состояния, в которые с помощью набора допустимых действий необходимо перевести среду, называются целевыми. Процесс определения этих состояний называют формулировкой цели. Будем полагать в рамках нашего примера, что каждое восприятие совпадает с одним из состояний. Задачей агента является нахождение последовательности действий или пар восприятие – действие, ведущих на дереве переходов из начального состояния в целевые. Процесс нахождения этих последовательностей называют поиском, выводом или рассуждением. Постановкой задачи называют задание всех состояний и действий, которые можно использовать для решения задачи, начального состояния и целевых состояний, а также всех допустимых переходов между состояниями при выполнении действий. Для среды кота постановка задачи уже осуществлена. Все состояния, которые могут использоваться при решении задачи, перечислены в табл. 3.1. Целевыми состояниями являются состояния b7, b8. Все допустимые переходы между состояниями показаны на рис. 3.2. Из рисунка ясно, что решениями задачи является последовательность b1/c2, b2/c3,b4/c1,b3/c3, в результате выполнения которой агент (кот) переведет среду в состояние b7, и последовательность b1/c3, b5/c2, b6/c3, в результате выполнения которой среда окажется в состоянии b8.
3.1.2. Формализация вывода средствами логики высказываний
Для записи задачи на языке исчисления высказываний введем три логические переменные хк, хл, хп.
Истинное значение первой из них означает, что кот находится у левой комнаты, а ложное, что он находится у правой комнаты;
истинное значение переменной хл означает, что кусочек сыра лежит около левой комнаты, а ложное, что его там нет;
истинное значение переменной хп означает, что кусочек сыра лежит около правой комнаты, а ложное, что его там нет.
В результате таких обозначений табл. 3.1 можно заменить на табл. 3.2. Каждое состояние среды можно рассматривать как комбинацию (отношение) простейших свойств объектов, задаваемых значениями отдельных логических переменных. Так, состояние b1 соответствует комбинации свойств кота и кусочков сыра, состоящей в том, что кот находится в левой комнате, и в это же самое время около левой и правой комнат находится по кусочку сыра. На русском языке эту комбинацию можно выразить предложением: «Кот находится около левой комнаты, кусочек сыра лежит около левой комнаты и кусочек сыра лежит у правой комнаты». В соответствии с уже приведенной выше интерпретацией логических переменных хк, хл, хп это предложение можно представить формулой , которая истинна в единственном случае - все логические переменные, входящие в нее, истинны, т.е. среда находится в состоянии b1. Формулы такого типа, являющиеся конъюнкцией переменных с отрицанием или без него, называют элементарными конъюнкциями. Если среда находится в состоянии b2, то истинна формула и т.д.
Элементарную конъюнкцию, в которую входит по одному разу каждая переменная, определяющую состояние среды, с отрицанием или без отрицания, называют полной конъюнкцией, или конституентой.
Аналогично тому, как были введены логические переменные хк, хл, хп, введем логические переменные z 1, z2, z3 для действий кота “Идти налево”, “Идти направо”, “Съесть “,соответственно. Переменная принимает истинное значение, если выполняется соответствующее ей действие. В противном случае она принимает ложное значение.


Таблица 3.2
Состояние
Переменные
Формула, описывающая состояние

xk
xл
xп

b1
И
И
И

b2
Л
И
И

b3
И
И
Л

b4
Л
И
Л

b5
И
Л
И

b6
Л
Л
И

b7
И
Л
Л

b8
Л
Л
Л

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


Таблица 3.3
Переход
Импликация,
соответствующая переходу
Исходное состояние
Действие
Результирующее состояние

b1
c1
b1

b1
c2
b2

b1
c3
b5

b2
c1
b1

b2
c2
b2

b2
c3
b4

b3
c1
b3

b3
c2
b4

b3
c3
b7

b4
c1
b3

b4
c2
b4

b4
c3
b4

b5
c1
b5

b5
c2
b6

b5
c3
b5

b6
c1
b5

b6
c2
b6

b6
c3
b8

Рассмотрим теперь, как могут быть выражены в виде формул переходы среды из одного состояния в другое при совершении котом того или иного действия. Так, если кот находился в состоянии b1, и выполнил действие “Идти направо”, то среда перейдет в состояние b2 . Факт нахождения кота в состоянии b1, и выполнение им в это время действия “Идти направо” означает истинность формулы , а факт перехода состояния b1 при выполнении действия «идти направо» в состояние b2 будем интерпретировать как истинность формулы , что позволяет при истинности сделать заключение об истинности . Точно так же можно выразить в виде аналогичных формул все остальные переходы, показанные на рис. 3.2. Представим их в виде табл. 3.3. В первых трех столбцах этой таблицы указаны переходы, имеющиеся на рис. 3.2, а в последнем -формулы, соответствующие переходам.
3.1.3. Поиск решения
Решения задачи для среды кота практически очевидны, когда построено дерево переходов состояний среды, по которому легко проследить пути, ведущие в целевые состояния из начального. В реальных задачах это дерево может быть очень большим, вследствие чего нецелесообразно использовать стратегию поиска, согласно которой необходимо сначала получать дерево целиком. Вместо этого используются другие более эффективные стратегии поиска, речь о которых пойдет в главе 4. Однако, какая бы из этих стратегий не применялась, элементарным шагом поиска является переход из одного состояния среды в другое и анализ состояния, в которое переход был осуществлен, на принадлежность к числу целевых. Каждый допустимый переход из состояния bi. после совершения действия сj в состояние bk можно задавать с помощью правила перехода: « Если среда находится в состоянии bi. и совершается действие сj, то она должна перейти в состояние bk».
Совокупность правил подобного типа используется в процессе поиска. Одной из очевидных, но чрезвычайно неэкономных стратегий поиска, позволяющей найти все решения для среды кота, может быть следующая.
1.Образовать множество В = {b1}, состоящее из одного начального состояния b1.
2. Для каждого состояния множества В и каждого действия с найти, согласно соответствующим правилам перехода, все состояния bk, в которые переходит среда. Совокупность всех таких состояний, за исключением тех, которые уже вст­речались в ранее образованных множествах В, принять за новое множество В.
3. Проверить, нет ли среди элементов этого множества целевых состояний. Если целевых состояний нет, то перейти к п. 2. Если целевые состояния есть, то выписать в порядке использования правил все последовательности действий, которые привели к целевым состояниям, удалить эти состояния из множества В и перейти к выполнению следующего пункта.
4. Проверить, все ли целевые состояния найдены. Если найдены все, то прекратить поиск. Если найдены не все, то перейти к п. 2.
Проиллюстрируем на примере среды кота применение этой стратегии. Правила перехода выписывать не будем, поскольку в нашем распоряжении уже есть дерево переходов (см. рис. 2.2).
Итак, вначале В={b1}. После выполнения п. 2 имеем совокупность состояний b1,b2,b5. В этой совокупности нет ни одного целевого состояния, а состояние b1 уже встречалось. Поэтому, согласно п. 3, принимаем В={b2,b5} и переходим к выполнению п.2. В результате получаем совокупность состояний b1,b2,b4,b5,b6, среди которых опять нет целевых, а b1,b2,b6 уже встречались. Поэтому В={b4,b6} и снова возвращаемся к п. 2. После очередного выполнения этого пункта имеем совокупность состояний b3,b4,b5,b6,b8. Среди этих состояний b4,b5,b6 уже встречались, а состояние b8, является целевым. В это состояние ведет единственная последовательность действий с3,c2,c3. Однако еще не все целевые состояния найдены, а именно не найдено состояние b7 . Поэтому в соответствии с п. 4 продолжим поиск, вновь переходя к п. 2 с множеством В = {b3}. В результате получим совокупность состояний b3, b4, b7, среди которых b3, b4 уже встречались, а b7 - целевое. Последовательностью действий, ведущих в состояние b7, является c2 c3 c1 c3. И так, все целевые состояния найдены, решение задачи в виде последовательности действий, ведущих в эти состояния, получено. Поиск на этом прекращается.
3.2. Нечеткий логический вывод.
Выше было определено, что правила СИИ формулируются экспертом. Но эксперт не всегда может точно определить, произойдет какое – либо событие , или нет. Например, врач ставит на основании своих наблюдений над пациентом определенный диагноз. Опыт врача во многих случаях с большой точностью позволяет определить заболевание пациента. Но он может и ошибиться, поэтому часто рассматриваются и другие диагнозы.
Люди не всегда могут ответить на вопросы точно. Можно ли узнать, какая у человека температура, если он говорит, что слегка заболел? Скорее всего, нет. Такие слова, как высокий, горячий и легкий, представляют собой лингвистические переменные, которые нельзя определить одним значением.
Лингвистическая переменная состоит из названия переменной, например, ПРОЦЕНТНАЯ СТАВКА и ее значений, например, РАСТЕТ, ПАДАЕТ.
Использование этих понятий при формулировании правил называется нечеткой логикой.
Нечеткий логический вывод может рассматриваться как расширение обычного логического вывода. В обычном логическом выводе производится применение некоторых правил логического вывода (которые считаются истинными) к некоторым посылкам (которые также считаются истинными), что в результате дает выводы, считающиеся достоверными. В нечетком же логическом выводе и исходные посылки, и правила вывода могут иметь произвольный уровень истинности в промежутке от 0 до 1, соответственно и получаемые результаты также могут быть более или менее достоверны.
В качестве примера рассмотрим влияние квартирной платы и цен на продукты питания на уровень жизни семьи. Это влияние описывается следующими утверждениями.
1. ЕСЛИ К_П незначительно растет, ТО У_Ж_1 незначительно падает. ( = 0.9)
2. ЕСЛИ К_П незначительно растет, ТО У_Ж_1 не падает. ( = 0.1)(Если перестают платить)
3. ЕСЛИ К_П значительно растет, ТО У_Ж_1 значительно падает. ( = 0.5)
4. ЕСЛИ К_П значительно растет, ТО У_Ж_1 не падает. ( = 0.5)
5. ЕСЛИ Ц_П незначительно растут, ТО У_Ж_2 незначительно падает. ( = 1)
6. ЕСЛИ Ц_П значительно растут, ТО У_Ж_2 значительно падает. ( = 1)
7. ЕСЛИ У_Ж_1 незначительно падает И У_Ж_2 незначительно падает, ТО У_Ж незначительно падает. ( = 1)
8. ЕСЛИ У_Ж_1 незначительно падает И У_Ж_2 значительно падает ИЛИ У_Ж_1 значительно падает И У_Ж_2 значительно падает, ТО У_Ж значительно падает. (=1)
9. ЕСЛИ У_Ж_1 значительно падает И У_Ж_2 значительно падает, ТО У_Ж очень значительно падает. ( = 1)
Условия К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ и К_П ЗНАЧИТЕЛЬНО РАСТЕТ являются размытыми и выражаются в зависимости от количества процентов роста p следующими формулами.
При 0 < p < 2  (К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ) = p / 2.
При 2 < p < 4  (К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ) = 1.
При 4 < p < 10  (К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ) = (10 - p) / 6.
При p > 10  (К_П НЕЗНАЧИТЕЛЬНО РАСТЕТ) = 1.
При p < 5  (К_П ЗНАЧИТЕЛЬНО РАСТЕТ) = 0.
При 5 < p < 15  (К_П ЗНАЧИТЕЛЬНО РАСТЕТ) = (p - 5) / 10.
При p > 15  (К_П ЗНАЧИТЕЛЬНО РАСТЕТ) = 1.




Условия Ц_П НЕЗНАЧИТЕЛЬНО РАСТУТ и Ц_П ЗНАЧИТЕЛЬНО РАСТУТ также являются размытыми и выражаются формулами
При 0 < p < 1  (Ц_П НЕЗНАЧИТЕЛЬНО РАСТУТ) = p.
При 1 < p < 5  (Ц_П НЕЗНАЧИТЕЛЬНО РАСТУТ) = (5 - p) / 4.
При 0 < p < 10  (Ц_П ЗНАЧИТЕЛЬНО РАСТУТ) = p / 10.
При p > 10  (Ц_П ЗНАЧИТЕЛЬНО РАСТУТ) = 1.
При использовании нечеткой логики для каждой формулы вводятся целый спектр возможных значений, лежащих между 0 (ЛОЖНО) и 1 (ИСТИННО), и правила вычисления этих значений. Вычисленные таким образом значения определяют степень истинности формул. Рассмотрим основополагающие понятия нечеткого множества и функции принадлежности.
Рассмотрим такие понятия, как «растет» и «падает». Отнесем эти понятия к переменным ПРОЦЕНТНАЯ СТАВКА и РУБЛЬ. Применительно к переменной ПРОЦЕНТНАЯ СТАВКА понятие роста может означать повышение уровня цен на бирже на 10 – 30 пунктов по индексу Доу-Джонса, а применительно к переменной РУБЛЬ означает повышение курса рубля по сравнению с какой-либо другой валютой в 20 – 30 раз. В таком контексте слово «растет» называется значением лингвистической переменной. Лингвистическая переменная может принимать различные значения из некоторого интервала, границы которого могут меняться в зависимости от обстоятельств. Например, границы интервала для лингвистической переменной «холодный» могут меняться в зависимости от того, идет ли речь о зиме или весне.
Понятие «падает» – также лингвистическая переменная, использующаяся в правилах, описывающих фондовую биржу. Применяя лингвистические переменные, можно вычислить значения некоторых вероятностей, не обременяя пользователя лишними вопросами. Для этого необходимо несколько конкретизировать лингвистические переменные. Пользователю экспертной системы нужно позволить добавлять к этим переменным определения, например маленький или средний. Пользователь может задать маленькое повышение курса рубля, и экспертная система должна точно знать, что под этим подразумевается.
Рассмотрим правило:
ЕСЛИ ПРОЦЕНТНЫЕ СТАВКИ – ПАДАЮТ И НАЛОГИ УМЕНЬШАЮТСЯ, ТО УРОВЕНЬ ЦЕН НА БИРЖЕ – РАСТЕТ.
Это правило верно не всегда, поэтому можно ему приписать значение некоторого числа m, изменяющегося от 0 до 1. Такое число называют функцией принадлежности μ.
Пусть функция принадлежности данного правила равна 0,9, т.е. вероятность того, что при падении процентных ставок и уменьшении налогов уровень цен на бирже будет падать равна 0.9.
Но выполнение правила зависит от выполнения условий ПРОЦЕНТНЫЕ СТАВКИ ПАДАЮТ и НАЛОГИ УМЕНЬШАЮТСЯ, что происходит не всегда.
Пусть функция принадлежности лингвистической переменной ПРОЦЕНТНЫЕ СТАВКИ ПАДАЮТ равна 0.6, а функция принадлежности лингвистической переменной НАЛОГИ УМЕНЬШАЮТСЯ равна 0.8.
Тогда правило можно записать так:
ЕСЛИ ПРОЦЕНТНЫЕ СТАВКИ ПАДАЮТ (μ - 0.6) И
НАЛОГИ УМЕНЬШАЮТСЯ (μ - 0.8), ТО УРОВЕНЬ ЦЕН НА БИРЖЕ - РАСТЕТ (μ правила - 0.9)
Функция принадлежности того, что уровень цен на бирже будет действительно расти может быть подсчитан следующим образом: выбирается минимальная функция принадлежности для условий части ЕСЛИ правила, разделенных логическим оператором И, и умножается на функцию принадлежности для всего правила. Для приведенного примера: (minimum (0.6, 0.8))*0.9=0.54
Следовательно, при μ - 0,54 можно сказать, что уровень цен на бирже будет падать.
Если в условной части правила имеется логический оператор ИЛИ, то μ для этого вывода нужно выбрать максимальной из μ для вывода первого правила и μ для вывода второго правила. На первый взгляд все это кажется очень сложным, поэтому разберем пример. Прежде всего сформулируем общие принципы.
1.Выбрать максимальное значение μ из μ для условий правила, разделенных логическим оператором И.
2.Если в правиле есть оператор ИЛИ, выбрать максимальное значение из μ для всех условий правила, разделенных оператором И для всех условий, связанных оператором ИЛИ.
3.Умножить выбранный μ на μ правила.
4.Если существует несколько правил с одинаковым логическим выводом, выбрать из всех полученных μ максимальный.
Рассмотрим два правила с одним и тем же логическим выводом С:
ЕСЛИ А (μ =0,3) И В (μ =0.6), ТО С (μ=0.5)
ЕСЛИ D (μ =0.4) И Е (μ =0,7), ТО С (μ=0.9)
В приведенных правилах μ для логического вывода С подсчитывается следующим образом:
maximum ((minimum(0.3,0.6)*0.5), (minimum (0.4,0.7) *0.9)) =
=maximum (03*0.5),(0.4*0.9)) = maximum (0.15,0.36) = 0.36
Возьмем пример с использованием логического оператора ИЛИ:
ЕСЛИ А (μ=0.3) И В (μ=0.6) ИЛИ D (μ=0.5), ТО С (μ=0.4)
В этом примере μ для логического вывода С считается так:
maximum (minimum (0.3,0.6), 0.5)*0.4)= maximum (0.3,0.5)*0.4=0.5*0.4=0.2.
Во многих случаях изначально заданы граничные значения функции принадлежности. Логический вывод считается верным только в том случае, если его μ превышает заранее заданные граничные значения. Работа с базой знаний продолжается до тех пор, пока значение функции принадлежности логического вывода больше граничного значения. В процессе работы выполняются определенные вычисления. Предположим, для частного логического вывода μ равно 0,4. Это значение запоминается. Затем оно сравнивается с граничным значением μ (допустим, что оно равно 0,8). Запомненное значение оказалось меньше граничного, и, значит, работа с базой знаний продолжается. Если при работе с базой знаний встретился тот же самый логический вывод, μ для новой μ и результат прибавляется к запомненному ранее μ. Значение μ , равное 1, свидетельствует об абсолютной уверенности в правильности вывода. Затем вновь запомненное значение μ сравнивается с граничным, и если оно больше, выполняется логический вывод, в противном случае, работа с базой знаний продолжается. Вышесказанное можно записать с помощью равенства:
Запомненный μ = Ранее запомненный μ + (1-Ранее запомненный μ)*μ нового правила.
Например:
Граничное значение μ=0,8
Правило: ЕСЛИ А, ТО В (μ=0,6)
Запомненный μ : 0,6
Новое правило: ЕСЛИ С, ТО В (μ=0,7)
Запомненный μ=0.6+(1-0,6)*0,7=0,88 (граничные значения превышены, и выполняется вывод).
Вопросы для самопроверки к главе 3:
1.Может ли быть в задачах рассуждений в пространстве состояний среды несколько целевых состояний?
2.Можно ли решить задачу рассуждений в пространстве состояний среды , рассматривая на каждом шаге два действия из четырех возможных?
3.Могут ли возможные действия меняться в процессе решения задачи в пространстве состояний среды?
4.При решении нечеткой задачи рассуждений в пространстве состояний среды ответ получаем детерминированный или вероятностный?
5.Может ли функция принадлежности принимать значение, большее единицы?
Тесты к главе 3.
1. Цель поиска:
А) нахождение целевого состояния, Б) нахождение промежуточного состояния, В) нахождение очередного состояния.
2.Поиск, вывод и рассуждение – это
А) одно и то же действие, Б) различные действия, В) ничего общего с действиями не имеют.
3. При нечеткой логике лингвистическая переменная может принимать
А) одно из двух значений «истинно» или «ложно», Б) множество значений внутри заданного интервала, В) одно значение.
4.Постановкой задачи называют
А) Задание всех возможных состояний, Б) задание всех возможных действий, В) задание всех возможных действий и состояний.
5. Если в условной части правила имеется логический оператор ИЛИ, то функцию принадлежности μ для вывода нужно выбрать
А) максимальной из μ для вывода первого правила и μ для вывода второго правила, Б) минимальной, В) функция принадлежности вывода не зависит от функций принадлежности от функций первого и второго правила

Глава 4. Стратегии поиска
В этой главе проанализированы различные стратегии, с помощью которых можно осуществлять поиск целевых состояний.
Ранее было введено понятие вывода для нахождения цели. Вывод не является однозначным и после очередного шага приходится определять, какой же следующий шаг целесообразно сделать, чтобы поскорее достичь цели. Очередной шаг зависит от того, какая стратегия вывода выбрана. Понятие «вывод» обычно используют вместе с той или иной логической системой; понятие «поиск» — безотносительно к какой-либо логической системе.
В настоящей главе описаны некоторые стратегии поиска, иллюстрируемые простыми примерами из области нахождения подходящего маршрута. Напомним некоторые ранее определенные понятия и введем ряд новых.
Состояние (или состояния) среды, с которого агент начинает решение задачи, называют начальным состоянием.
Соответственно множество всех состояний, достижимых из начального с помощью всех допустимых последовательностей действий, называют пространством состояний и обозначают В.
Последовательность вершин, ведущих из начального состояния в другое состояние в данном пространстве состояний, называют путем. Длиной пути называют количество вершин на этом пути.
Процесс нахождения целевого состояния (состояний) называют стратегией поиска цели, или поиском цели.
Агент, являющийся исполнителем той или иной стратегии, должен действовать таким образом, чтобы при анализе состояний среды максимизировать свой успех. Это требование носит слишком общий характер, чтобы его можно было непосредственно воплотить в конкретную стратегию. Рассмотрим сначала, какие оценки могут характеризовать успех.
4.1. Оценки успеха при поиске цели.
Оценки успеха, характеризующие эффективность поиска, могут быть самыми различными. Будем полагать, что оценка успеха является положительным числом или нулем и чем больше число, тем успешнее действует агент. Тогда самая очевидная оценка — это возможность достижения цели вообще. Эта оценка носит двузначный характер: например, она принимает некоторое максимальное значение, если цель достижима, и минимальное в противном случае. Другая оценка может быть ценой пути, вычисляемой с помощью функции цены пути. Третья оценка может быть ценой поиска, характеризующейся объемом необходимых для поиска времени и памяти. Наконец, еще одна оценка успеха может быть общей ценой, являющейся некоторой функцией от цены пути и цены поиска.
Цена поиска зависит от многих обстоятельств. Так, например, если агент сильно стеснен во времени, то цена поиска может быть пропорциональна времени, затрачиваемому на поиск. Общая цена может зависеть от пройденного расстояния и затраченного на поиск времени. Вычисление общей цены непростая задача, поскольку выбор пути, а следовательно, и пройденное расстояние могут определяться временем, затраченным на поиск. Чем меньше времени потрачено на поиск, тем дальше от оптимального может оказаться выбор пути. Зачастую в этих условиях приходится идти на некий компромисс, далекий от оптимального решения.
Стратегии поиска различаются последовательностью или порядком просмотра состояний или множеств состояний в пространстве всех состояний среды. Стратегии поиска в пространстве состояний обычно сравнивают по ряду критериев. Основными критериями являются следующие.
Полнота: стратегия является полной при условии, что она всегда обеспечивает нахождение решения (целевого состояния или состояний), если оно вообще существует в данном пространстве состояний.
Сложность по времени: время, необходимое для нахождения решения.
Сложность по памяти: объем памяти, необходимый для решения задачи.
Оптимальность: стратегию называют оптимальной при условии, что она обеспечивает нахождение решения, которое может не быть наилучшим, но известно, что оно принадлежит некоторому классу или подмножеству, все элементы которого обладают неким общим свойством (или свойствами), согласно которому мы их относим к оптимальным решениям.
Минимальность: стратегия является минимальной, если она гарантирует нахождение наилучшего решения. Минимальность, таким образом, является частным и более сильным случаем оптимальности.
Стратегии поиска разбивают на две большие группы: слепой поиск и направленный поиск. Различие между слепым и направленным поиском можно продемонстрировать на следующем простом примере. Представим себе, что агент приехал в Россию по туристической путевке с целью совершить путешествие по золотому кольцу России. Его самолет сел в аэропорту Шереметьево.
Обратный вылет тоже из Шереметьева. Путешествие по золотому кольцу агент совершал на автобусе. Посетив все города золотого кольца, агент самостоятельно поехал в близлежащий город Иваново, где задержался и отстал от автобуса. В отличие, например, от Ярославля, Иваново не имеет прямой автострады, соединяющей его с Москвой. У агента есть обратный билет на самолет с датой вылета на следующий день, билет не может быть продлен, да к тому же обратных билетов вообще нет на ближайшие две недели. Срок визы также заканчивается через два дня. Отправляясь в поездку, агент ставил перед собой, помимо туристических, несколько других целей: улучшить знание русского языка, завязать полезные деловые контакты, написать несколько пейзажей с видами русской природы и т.п. Но, учитывая серьезность ситуации, главной его целью теперь стало вовремя добраться до аэропорта Шереметьево, не опоздав на свой самолет. После формулировки главной цели агент может принимать во внимание и другие факторы, влияющие на ее достижение.
Прежде всего, следует решить, что мы будем понимать под действиями и состояниями. Если бы вдруг нам пришло в голову в качестве действий выбрать такие, как «повернуть руль на 10 градусов» или «продвинуться вперед на 1 метр», то решение задачи на таком уровне детализации стало бы практически неразрешимой задачей. В нашем случае в качестве действий лучше всего выбрать переезд из одного города в другой, а в качестве состояний нахождение агента в том или ином населенном пункте. Целевым состоянием в этом случае будет нахождение агента в аэропорту Шереметьево (в Москве).
Поиск будет слепым, если агент не имеет никакой информации о дорогах, ведущих из Иванова в другие города, и будет перебирать все дороги подряд. И наоборот, его поиск станет направленным, если он ознакомится с картой, увидит, что Москва лежит на юго-западе от Иванова, и будет пытаться выбирать дороги, ведущие в юго-восточном или близком к нему направлении.
4. 2. Слепой поиск
4.2.1. Поиск в ширину
Одна из самых очевидных стратегий поиска называется поиском в ширину. Поиск начинается с корневой вершины, определяются все последователи корневой вершины, затем все последователи каждого из последователей корневой вершины, далее все последователи каждого из последователей, найденных на предыдущем шаге, и т.д. до тех пор, пока не будут найдены все вершины, соответствующие целевым состояниям. Согласно этой стратегии, вершины глубиной k ищутся после того, как будут найдены все вершины глубиной k-1. На рис. 4. 1 показана последовательность нахождения вершин при поиске в ширину и при числе последователей каждой вершины, равном 2.
При поиске в ширину сначала рассматриваются все пути, длина которых равна 1, затем длиной 2 и т.д. Очевидно, что поиск в ширину удовлетворяет критерию полноты и минимальности, поскольку в процессе этого поиска рассматриваются все пути, ведущие из начальной вершины (состояния) во все остальные.
Оценим время и память, затрачиваемые в процессе поиска в ширину. Будем полагать, что число последователей каждой вершины равно l. Тогда в начале поиска в ширину мы имеем одну начальную вершину, затем l последователей, потом l2 последователей и т.д. В общем случае при глубине дерева поиска, равной к, число вершин, изучаемых в процессе поиска, равно 1 + l+ l 2+ l 3+ ...+ l k. При конкретных значениях l и k по этой формуле можно вычислить максимальное число вершин дерева поиска, которое может быть получено в процессе поиска в ширину. Естественно, решение можно найти раньше, чем будут найдены все последователи.
Однако для некоторых задач эта величина может быть достигнута. Обычно вместо этой формулы употребляют ее обозначение в виде O(l k), которое называют экспоненциальной оценкой сложности.









Рис. 4.1. Деревья поиска в ширину при l=2: нулевая вершина (дерево
глубиной k=0), дерево после нахождения последователей нулевой вершины
(дерево глубиной k = 1), дерево после нахождения последователей первой
вершины, дерево после нахождения последователей второй вершины
(дерево глубиной k = 2)
Если полагать, что получение каждого последователя требует одной единицы времени, то O(lk) является оценкой сложности по времени. В процессе поиска в ширину каждая вершина дерева должна сохраняться до получения требуемого решения. Если полагать, что для этого сохранения требуется единица памяти, то та же формула является одновременно и оценкой сложности по памяти для поиска в ширину.











Посмотрим, что это будут за величины при l=10 для различных значений k (табл. 4.1). Предполагается, что 1000 вершин-последователей могут быть получены за 1 с, и что одна вершина требует 100 байт памяти. Эти значения соответствуют средним затратам времени и памяти, требуемым для решения многих иллюстративных задач типа головоломок. Из табл. 4.1 можно сделать два важных вывода. Во-первых, рост требований к памяти для решения задач поиском в ширину гораздо более серьезная проблема, чем рост требований времени решения тех же задач.
Так, например, вполне приемлемо подождать решения задачи в течение 18 мин при l = 6, но необходимость наличия 111 Мбайт памяти для решения таких сравнительно простых задач кажется слишком высокой ценой.
Во-вторых, для задач, в которых l > 10, помимо катастрофического увеличения требований к памяти, наблюдается стремительный рост временных затрат, не позволяющий решать реальные задачи с помощью поиска в ширину даже на современных мощных компьютерах. Это приводит к следующему заключению: Стратегии поиска, еющие экспоненциальные оценки сложности решения задач по времени и памяти, в частности стратегия поиска в ширину, нельзя использовать i решения задач большой размерности, т.е. задач, у которых 1 > 10.
4.2.2. Монотонный поиск в ширину
Поиск в ширину обеспечивает нахождение целевого состояния, находящегося на минимальной глубине дерева поиска. Однако минимальность цены пути и этом не гарантируется. Монотонный поиск в ширину является некоторой модификацией поиска в ширину, заключающейся в том, что в процессе поиска в ширину всякий раз, когда определяется очередная вершина-последователь, одновременно вычисляется цена пути, ведущего в эту вершину. Эта цена пути используется для оценки целесообразности поиска вершин, продолжающих данный путь, сравнением с другими, уже полученными ценами путей.
Если цена данного пути меньше цен всех этих путей, то поиск вершин на этом пути продолжается. В противном случае поиск вершин на этом пути откладывается, а продолжается поиск вершин на путях, цена которых меньше данного. Когда на каком-либо пути будет достигнута целевая вершина, поиск на путях, цена которых выше цены этого пути, вообще прекращается. Все пути, имеющие одинаковую минимальную цену путей, ведущих в целевую вершину, являются решением задачи.
Вернемся к задаче поиска пути из Иванова в Москву. На рис. 4.2,б схематически показана карта участка дорог, ведущих из Иванова в Москву. Каждая из дорог, ведущих из одного пункта в другой, снабжена числовой оценкой действия. На рис. 4.2, а показана последовательность монотонного поиска в ширину. Каждая из вершин помечена ценой пути, ведущего в эту вершину.




















Рис. 4. 2. Задача нахождения маршрута из Иванова в Москву:
а – порядок монотонного поиска в ширину. Каждая вершина помечена ценой пути, ведущим в нее из начальной вершины (снаружи вершины) и номером ее получения в процессе поиска (внутри вершины). На последнем шаге монотонного поиска в ширину найдена целевая вершина с ценой пути, равным 10;
б – пространство состояний, иллюстрирующее цену действий, соответствующую участкам пути между городами.
4.2.3. Поиск в глубину
При поиске в глубину, начиная с корневой вершины (корневая вершина находится на уровне 1), рассматриваются все инцидентные ей вершины уровня 2, начиная слева направо. Если удается найти среди них все целевые вершины, то на этом поиск прекращается. Если среди них не удается найти все целевые вершины, а максимальная глубина дерева еще не достигнута, то берется самая левая вершина уровня 2 и рассматриваются все инцидентные ей вершины уровня 3 слева направо. Если после этого все целевые вершины все еще не найдены, то берется самая левая вершина из уровня 3. Затем снова рассматриваются все инцидентные ей вершины уровня 3 слева направо, и так до тех пор, пока либо не будут найдены все целевые вершины, либо достигнута максимальная глубина дерева, на которой в соответствии с рассматриваемой процедурой просмотрены все вершины, инцидентные самой левой вершине предыдущего уровня, и все целевые все еще не найдены. В последнем случае осуществляется подъем по дереву на один уровень вверх, выбор на этом уровне самой левой вершины, инцидентные которой вершины следующего уровня еще не рассмотрены, и поиск дальше среди целевых вершин по тому же принципу. И так до тех пор, пока все вершины дерева не будут рассмотрены.
На рис. 4.3 показана последовательность поиска в глубину для дерева с тремя уровнями и степенью ветвления 2. Вершины на этом рисунке пронумерованы в соответствии с последовательностью их просмотра.
Требования к объему памяти при поиске в глубину существенно меньше, чем при поиске в ширину. Как видно из рис. 4.3, в памяти необходимо хранить все вершины, инцидентные вершинам на пути из корневой вершины к любой другой, соседние вершины которой рассматриваются. Очевидно, что при степени ветвления l и глубине дерева k оценка сложности по памяти при поиске в глубину равна O(lk). Оценка сложности по времени для поиска в глубину остается такой же, как и при поиске в ширину, а именно O(lk).


Рис. 4.3. Стратегия поиска в глубину
Для задач, дерево поиска для которых конечно, а число целей сравнительно невелико, поиск в глубину может оказаться эффективным, так как имеет шанс найти это небольшое число целей без просмотра всех вершин. Для задач, имеющих большую или даже бесконечную глубину дерева, поиск в глубину может оказаться крайне неэффективным, так как будет стремиться все время в глубину, в то время как цель может оказаться близкой к корню дерева, но на том пути, который еще не был просмотрен. Поиск же все время уходит вниз и в случае бесконечной глубины дерева может никогда не вернуться назад к просмотру вершин, среди которых находятся целевые. Вследствие этого следует избегать использования поиска в глубину для решения задач с большой или бесконечной глубиной дерева. Поиск в глубину, таким образом, нельзя считать ни полным, ни оптимальным.
4.2.4. Ограниченный поиск в глубину
Ограниченный поиск в глубину является частным случаем поиска в глубину. При этом поиске используется ограничение на глубину поиска. Например, при поиске маршрута из Иванова в Москву при наличии информации о числе населенных пунктов, которые могут встретиться на этом пути, глубину поиска можно ограничить числом этих населенных пунктов. При ограниченном поиске в глубину, как только достигается уровень, совпадающий с этим числом, происходит возврат назад так же, как это делается при обычном поиске в глубину. Ограниченный поиск в глубину полный, если ограничение на глубину поиска выбрано таким образом, чтобы обеспечить просмотр всех вершин дерева. Оценки сложности по времени и памяти при ограниченном поиске в глубину те же, что и при обычном поиске в глубину.
4.2.5. Итеративный поиск в глубину
При ограниченном поиске в глубину сложность поиска зависит от выбора ограничения. Например, при поиске маршрута можно использовать не число всех населенных пунктов в районе поиска подходящего маршрута, а максимальное число населенных пунктов, которые могут встретиться на каждом из возможных маршрутов. Это число называют обычно радиусом поиска. Знание радиуса поиска приводит к более эффективному ограниченному поиску в глубину. Однако в большинстве задач радиус поиска не известен до тех пор, пока задача не будет решена. Итеративный поиск в глубину использует стратегию, основанную на итеративном применении ограниченного поиска в глубину сначала для радиуса поиска, равного 0, затем 2, после этого 3 и т.д. Четыре итерации такого поиска для бинарного дерева иллюстрирует рис. 4. 4. Итеративный поиск в глубину может показаться очень неэффективным, поскольку некоторые вершины просматриваются многократно. Однако для многих задач подавляющая доля вершин находится на низком уровне. Напомним, что оценка сложности по времени при ограниченном поиске в глубину вычисляется по формуле
0(lk)=1+1+l2 …+lk-2+lk-1+lk
Например, для l = 10, k = 5 будем иметь 0(l k) = 111111. При итеративном поиске на глубину k вершины глубины k просматриваются один раз, глубины k-1 — два раза, глубины k-2 — три и т.д. Корневая вершина просматривается k + 1 раз.



















Таким образом, оценка сложности по времени при итеративном поиске в глубину вычисляется по формуле
0(lk)=(k+1)l0+(k)l1+(k-1)l2+ …+3lk-2+2lk-1+1lk
Для l=10, k=5 будем иметь 0(lk)=123456. По сравнению с оценкой сложности по времени для ограниченного поиска в глубину сложность по времени для итеративного поиска в глубину возросла только на 11%. Из формулы, приведенной выше, видно, что чем выше степень ветвления, тем ниже доля сложности, получающейся за счет повторного просмотра вершин. Но даже для случая, когда l=2, сложность по времени итеративного поиска в глубину только в два раза превосходит сложность по времени простого поиска в глубину. Это означает, что оценка сложности по времени итерационного поиска в глубину по-прежнему равна O(lk), а сложность по памяти – O(lk). Итеративный поиск в глубину достаточно хорошо себя зарекомендовал для задач с большим пространством поиска и неизвестной его глубиной. Если цена данного пути меньше цен всех этих путей, то поиск вершин на этом пути продолжается. В противном случае поиск вершин на этом пути откладывается, а продолжается поиск вершин на путях, цена которых меньше данного. Когда на каком-либо пути будет достигнута целевая вершина, поиск на путях, цена которых.
4.2.6. Двунаправленный поиск
Идея двунаправленного поиска основана на использовании сразу двух стратегий – прямого поиска от корневой вершины и обратного от целевой вершины. Процесс поиска прекращается, когда оба этих процесса встретятся на середине глубины. Если считать, что степень ветвления при прямом и обратном поиске одинакова, то оценка сложности по времени двунаправленного поиска будет O(2l k/2) =O(lk/2). Эта оценка существенно лучше, чем аналогичная для рассмотренных стратегий поиска. Однако все это в идеале, т.е. при условии, что цель только одна, степень ветвления и сложность нахождения последователей и предшественников одна и та же. При решении практических задач, однако, это условие может нарушаться. Кроме этого могут возникать и другие проблемы. Например, установление факта появления одной и той же вершины в той и другой половине поиска может потребовать значительных усилий и составить значительную долю сложности. Если все эти проблемы можно решить за постоянное время, не зависящее от числа вершин, то оценка сложности по времени двунаправленного поиска останется равной 0(l k/2).
4.2.7. Сравнение стратегий поиска
Характеристики шести рассмотренных стратегий, где l - степень ветвления, k – глубина поиска, d – максимальная глубина дерева поиска, г – ограничение на глубину поиска, сведены в табл. 4.2.

Таблица 4.2

Критерии
Поиск

В ши-
рину
Монотон-
ный в
ширину
В
глубину
Ограничен-
ный в
глубину
Итератив-
ныйв
глубину
Двунап-
равленный
время
lk
lk
ld
lr
lk
lk/2
память
lk
lk
ld
lr
lk
lk/2
оптима-
льность
да
да
нет
нет
да
да
полнота
да
да
нет
да, если r
да
да
4. 3. Направленный поиск
Как было показано в предыдущем разделе, все стратегии слепого поиска обладают экспоненциальными оценками сложности по времени поиска, а некоторые и по памяти, и, вследствие этого, пригодны для решения сравнительно небольших задач. В стратегиях слепого поиска знания, используемые при выборе очередной вершины, определяют только общий порядок выбора и никак не учитывают качество выбора, например, по сложности поиска целевой вершины. В стратегиях направленного поиска знания, используемые для выбора очередной вершины, более глубокие и используют специальные функции, называемые критериями. Если для каждой вершины b, участвующей в поиске, критерий может быть вычислен, а множество всех вершин упорядочивается по этому критерию, то выбор очередной вершины производится в соответствии со значением этого критерия. Чем лучше значение критерия (например, выше или ниже), тем предпочтительнее выбор. Иными словами, из множества альтернативных вершин выбирается та, для которой критерий имеет наилучшее значение. Поэтому стратегии выбора подобного типа называются стратегиями выбора по наилучшему критерию. Критерии обычно выбираются таким образом, чтобы оптимизировать сложность поиска, найти оптимальное решение или достичь того и другого. В настоящем разделе рассмотрим некоторые стратегии направленного поиска, при котором используются дополнительные знания о среде, позволяющие понизить сложность поиска. Рассмотрим, как осуществляется направленный поиск при решении оптимизационных задач.
4.3.1. Поиск по критерию близости к цели
Критерием близости к цели обычно является числовая функция h(b)>=0 , вычисляемая для вершины b и характеризующая близость этой вершины к целевой. При использовании критерия близости к цели, начиная с корневой вершины, просматриваются все соседние ей вершины, выбирается та, для которой h(b) минимальна, и все повторяется вновь для выбранной вершины.
И так до тех пор, пока не будет достигнута целевая вершина, для которой h(b)=0, т.е. выбирается та вершина, которая ближе всего находится к цели. Вид критерия близости к цели зависит от среды (является проблемно зависимым). Чтобы получить достаточно полное представление об этом критерии, вернемся к задаче поиска маршрута из Иванова в Москву. Критерием выбора в этом случае будет минимальное расстояние по прямой (кратчайшее расстояние) от вершины (населенного пункта) до Москвы. Естественно, чтобы значение критерия могло быть вычислено, необходимо иметь карту или какой-либо другой источник информации, содержащий сведения о кратчайших расстояниях от населенных пунктов до Москвы. На рис. 4.5 показана последовательность поиска по критерию близости к цели для примера с поиском маршрута из Иванова в Москву, использованного при рассмотрении монотонного поиска в ширину.





























Рис. 4.5. Поиск по критерию близости к цели
На первом шаге вычисляется кратчайшее расстояние от корневой вершины (Иваново) до Москвы (h=230). На втором шаге просматриваются все вершины (города), в которые ведет дорога из Иванова и вычисляется кратчайшее расстояние h от этих городов до Москвы. По этому критерию ближайшим по прямой до цели (Москвы) оказывается Юрьев-Польский (h=140). На третьем шаге просматриваются все вершины, в которые ведет дорога из Юрьева- Польского.
Для них снова вычисляется кратчайшее расстояние h до Москвы, кратчайшим оказывается расстояние от Киржача (h=76). Наконец, на последнем шаге вновь просматриваются все вершины, в которые ведет дорога из Киржача, а также вычисляется кратчайшее расстояние до этих городов. Среди этих городов оказывается город с кратчайшим расстоянием h=0, т.е. целевая вершина (Москва).
На этом поиск по критерию близости к цели завершается. Поиск по критерию близости к цели является поиском в глубину, но с выбором на каждом шаге единственной вершины, от которой начинается следующий шаг.
Недостатки этой стратегии те же, что и для слепого поиска в глубину, а именно, она неоптимальная и неполная, поскольку может случиться, что поиск пойдет по бесконечному пути и никогда не вернется назад. Оценка сложности по времени этой стратегии поиска равна 0(ld), где d – максимальная глубина пространства поиска. При поиске по критерию близости к цели приходится хранить все вершины, рассматриваемые при поиске. Поэтому оценка сложности по памяти для этой стратегии та же, что и оценка сложности по времени. Если критерий близости к цели выбран достаточно удачно, то сложность поиска может быть существенно уменьшена.

4.3.2. Поиск по критерию цены пути (А*-поиск)
С помощью этого критерия можно находить пути с минимальной ценой.
Обозначим g(b) – критерий цены пути из корневой вершины в вершину b, a h(b) – уже рассмотренный критерий близости к цели. Пусть оба критерия имеют одну и ту же размерность. Функцию f(b)=g(b)+h(b) можно считать критерием цены пути из корневой вершины в целевую.
Рассмотрим стратегию поиска на основе этого критерия и покажем, что она будет полна и оптимальна, если ввести небольшие ограничения на критерий h(b).
Идея этого ограничения состоит в том, чтобы выбирать критерий h(b) таким образом, чтобы не переоценивать близость к цели, т.е. не выбирать значение h(b) меньше, чем оно есть на самом деле. Критерий h(b), выбираемый таким образом, называется допустимым. Стратегия поиска, использующая критерий f(b) и допустимый критерий h(b), известна как А*-поиск. Критерий близости цели h(b), использованный в примере с поиском маршрута из Иванова в Москву, является типичным примером допустимого критерия, поскольку не может быть пути из одного населенного пункта в другой короче, чем кратчайший путь. На рис. 4.6 показаны первые четыре шага поиска пути из Иванова в Москву с использованием критерия f(b) в А*-поиске. Заметим, что в результате этого поиска, в отличие от поиска только по критерию близости к цели, рассмотренного в предыдущем разделе, выбран путь к Москве не через Юрьев-Польский, а через Владимир, хотя Юрьев-Польский ближе к Москве, чем Владимир. Такой выбор объясняется тем, что цена пути g(b) от Иванова до Юрьева-Польского выше, чем до Владимира вследствие очень плохой дороги.



















Дальнейший выбор маршрута можно проследить по рисунку, где на любом пути от корневой вершины значение критерия f(b) нигде не уменьшается при переходе к рассмотрению очередной вершины. Это не случайность и справедливо почти для всех допустимых критериев h(b) близости к цели. Критерии f(b), для которых имеет место подобное свойство, называются монотонными. Если монотонность нарушается, то путем незначительной коррекции это нарушение может быть устранено. Рассмотрим, например, пару вершин b, b', где b предшественник, а b' – последователь. Предположим, что g(b)=3, h(b)=4. Тогда f(b)=7, т.е. цена пути через вершину b самое меньшее равна 7. Предположим также, что g(b')=4, h(b’)=2, т.е. f(b')=6. Ясно, что в этом случае критерий f(b) не является монотонным. К счастью, благодаря тому, что любой путь через b’ является также путем через b, цена пути f(b')=6 является бессмысленной. Поэтому каждый раз, как рассматривается какая-либо вершина b' и оказывается, что ее цена пути f(b') Таким способом немонотонность может быть всегда устранена, и критерий f(b) никогда не будет уменьшаться вдоль одного и того же пути при условии, что h(b) допустимое. Если же f(b) никогда не уменьшается вдоль одного и того же пути, начинающегося от корневой вершины, то на пространство состояний можно наложить контуры, каждый из которых охватывает множество вершин b, для которых значение критерия f(b) меньше определенной величины с. Процесс поиска можно представить как переход от просмотра еще не просмотренных вершин какого-либо внутреннего контура, для всех вершин b1 которого имеет место f(b1) < с, к просмотру вершин некоторого внешнего контура, для всех вершин b 2 которого имеет место f(b2)<с2 и с1<с2. Это продолжается до тех пор, пока внутри очередного контура не окажется целевая вершина с h(b)=0. При удачном выборе критерия f(b) контуры как бы растягиваются в сторону целевой вершины, фокусируясь вокруг оптимального пути. Обозначим с* цену оптимального пути. Тогда можно утверждать следующее:
А*-поиск просматривает вершины с f(b)<=с*.
А*-поиск осуществляет направленный просмотр вершин, стремясь к просмотру вершин контура, для которых имеет место f(b)=с*.
Решение, получаемое с помощью А*-поиска, является оптимальным, поскольку находится вершина с максимальным значением f(b), a следовательно, и максимальным g(b), так как h(b)=0. А*-поиск является также полным, поскольку, увеличивая постепенно значение критерия f(b), мы должны, в конце концов, найти путь к целевой вершине. Заметим также, что для данного критерия f(b) не существует никакой другой процедуры поиска, которая давала бы более оптимальные решения, чем А*-поиск. Все эти утверждения требуют более строгих доказательств, которые мы здесь не приводим. Оценки сложности по времени и памяти для А*-поиска аналогичны оценкам для поиска по критерию близости цели.
На идее А*-поиска построено много других методов поиска, учитывающих особенности конкретной среды, которые влияют на выбор критериев, и различные ограничения, например по доступным ресурсам (времени выполнения и доступной памяти).

4.3.3. Оптимизирующий итеративный поиск
Во многих задачах поиск целевого состояния (состояний) в пространстве состояний ставится как задача нахождения такого состояния (состояний), которое в определенном смысле наилучшее (оптимальное). При этом не имеет особого значения цена пути нахождения цели, если эта цель может быть достигнута за приемлемые затраты времени и памяти. Идея оптимизирующего итеративного поиска станет понятной, если полагать, что состояния – это точки на поверхности некоторого горного ландшафта. Чем выше точка находится над уровнем моря, тем лучше (оптимальнее) состояние, которое она представляет. Точки, соответствующие пикам, являются оптимальными точками. Задачей оптимизирующего итеративного поиска является такой порядок просмотра точек, или иначе такое движение по поверхности ландшафта, при котором в конце концов достигаются (находятся) оптимальные точки. Имеется большое разнообразие процедур оптимизирующего итеративного поиска. Одной из таких процедур является градиентный поиск. Рассмотрим суть этой процедуры.
Идея градиентного поиска чрезвычайно проста – двигаться в направлении подъема вверх, начиная с некоторого начального состояния. Дерево поиска не хранится, а сохраняется только последнее найденное состояние b и оценка его качества L(b). Если попадаются несколько состояний с одинаковой оценкой качества, то, как правило, выбирается одно из них. Градиентный поиск в чистом виде обладает тремя известными недостатками.
Если вершин несколько, то поднявшись на одну из них, процесс поиска остановится, полагая, что цель достигнута, хотя достигнутая вершина является всего лишь локальным оптимумом и далека от наилучшей.
Если ландшафт имеет плато, то процесс поиска по нему становится случайным.
Если ландшафт имеет гребни (хребты) со слабым наклоном, то легко достигнув гребня, процесс поиска может очень долго идти по гребню, пока не достигнет оптимальной вершины.
После остановки процесса градиентного поиска начинается следующая итерация с другого начального состояния. Найденное оптимальное состояние сохраняется до тех пор, пока не будет найдено лучшее. Этот итеративный процесс поиска осуществляется конечное число раз или пока не будет найдено устраивающее решение.
Ясно, что если провести достаточное число подобных итераций, то оптимальное решение, в конце концов, будет найдено. Успех градиентного поиска сильно зависит от вида пространства состояний. Если число локальных минимумов невелико, то оптимальное решение будет найдено сравнительно быстро. Процедуры градиентного поиска могут отличаться способом выбора очередной вершины в процессе подъема на вершину, выбором очередной вершины для новой итерации и т.д.

Вопросы для самопроверки к главе 4:
1. Какие оценки успеха при поиске цели Вы знаете?
2. При слепом поиске в ширину исследуются сначала все состояния одного уровня, затем все состояния следующего уровня и т.д. или сначала все состояния одного направления, затем все состояния другого направления и т.д?
3.Является ли итеративный поиск одним из видов ограниченного поиска?
4. Что проще: поиск по критерию цены или поиск по критерию близости?
5. В чем различие между методом итерации и рекуррентными методами?

Тесты к главе 4
1.Различные стратегии поиска необходимы потому, что
А) полный перебор возможных состояний не приводит к цели
Б) полный перебор слишком громоздок, В) полный перебор невозможен.
2.Поиск в ширину – это
А) слепой поиск, Б) направленный поиск, В) итеративный поиск.
3 Поиск по критерию близости к цели – это
А) один из видов направленного поиска, Б) слепой поиск,
В) итеративный поиск.
4.Поиск по критерию цены пути учитывает
А) один критерий, Б) два критерия, В) ни одного критерия.
5.При градиентном поиске движение производится по:
А) максимальному значению градиента, Б) минимальному значению градиента, В) по постоянному значению градиента.

Ответы на тестовые задания
Ответы к тестам главы 1 Ответы к тестам главы 2
Тест№ 1 Правильный ответ: В Тест№ 1 Правильный ответ: Б
Тест№ 2 Правильный ответ: А Тест№ 2 Правильный ответ: Б
Тест№ 3 Правильный ответ: В Тест№ 3 Правильный ответ: В
Тест№ 4 Правильный ответ: А Тест№ 4 Правильный ответ: В
Тест№ 5 Правильный ответ: В Тест№ 5 Правильный ответ: А

Ответы к тестам главы 3 Ответы к тестам главы 4
Тест№ 1 Правильный ответ: А Тест№ 1 Правильный ответ: Б
Тест№ 2 Правильный ответ: А Тест№ 2 Правильный ответ: А
Тест№ 3 Правильный ответ: Б Тест№ 3 Правильный ответ: А
Тест№ 4 Правильный ответ: В Тест№ 4 Правильный ответ: Б
Тест№ 5 Правильный ответ: А Тест№ 5 Правильный ответ: А

Тесты по дисциплине.
1.Причиной появления систем искусственного интеллекта явилось: А) потребности производства, Б) наличие математического аппарата, В) наличие компьютеров.
2.База знаний составляется из: А) опыта экспертов, Б) математических формул, В) интуиции программиста.
3.Правила систем искусственного интеллекта записываются для ЭВМ: А) на алгоритмическом языке Бейсик, Б) на алгоритмическом языке дельфи, В) на любом алгоритмическом языке.
4.Агент перерабатывает: А) восприятие в реакцию, Б) реакцию в восприятие, В) ничего не перерабатывает.
5.Статическая среда, это среда: А) в которой за время, протекающее между получением агентом любого восприятия и выработкой им реакции, среде ничего не изменяется, Б) в которой за это время происходит какое-либо изменение. В) в которой агент формирует несколько реакций.
6.Логические рассуждения записываются : А)обязательно на языке исчисления высказываний, Б) обязательно на языке исчисления предикатов, В) на любом математическом языке.
7.Функция принадлежности к нечеткому множеству может принимать: А) любое положительное значение, Б) значение между нулем и единицей, В) любое отрицательное значение.
8.Основными критериями стратегии поиска являются: А) полнота, Б) сложность и оптимальность, В) все эти критерии.
9.Поиск в глубину – это: А) слепой поиск, Б) направленный поиск, В) итеративный поиск.
10.Двунаправленный поиск – это: А) поиск в глубину, Б) поиск в ширину, В) прямой поиск от корневой вершины и обратный от целевой вершины

Список рекомендуемой литературы
1.Девятков В.В. Системы искусственного интеллекта. М., МГТУ им. Баумана, 2001
2.Р.Левин, Д.Дранг, Б.Эделсон. Практическое введение в технологию искусственного интеллекта и экспертных систем. Москва, Финансы и статистика, 1998.
3.Краснов А.Е., Красуля О.Н., Большаков О.В., Шленская Т.Н. Информационные технологии пищевых производств в условиях неопределенности ВНИИМП, Москва, 2001. стр. стр. 66-77, 176-184, 232-256, 478-488.
4.Введение в экспертные системы. Разработка интеллектуальных систем.. Иллюстрированный самоучитель. CD-диск. Market @Allex soft.ru.

Словарь основных понятий
Агенты или носители. Интеллектуальные сущности, объекты, созданием которых занимается искусственный интеллект.
База знаний. Совокупность вопросов, ответы на которые помогают человеку принять окончательное решение.
Вывод логический нечеткий. # Вывод, в котором исходные посылки и правила вывода могут иметь произвольный уровень истинности в промежутке от 0 до 1, соответственно и получаемые результаты также могут быть более или менее достоверны.
Искусственный интеллект (ИИ) .Программная система, имитирующая на компьютере мышление человека.
Лингвистические переменные. Понятия, которые нельзя определить одним значением.
Механизм вывода. Часть интеллек­та, которая помогает извлекать новые факты.
Множество нечеткое. Множество с границами, которые мы точно не знаем.
Множество четкое. Множество с четкими границами .
невыполнимой.
Поиск в глубину слепой. Поиск, при котором сначала рассматриваются все вершины уровня 2, начиная слева направо. Если среди них не удается найти все целевые вершины, то берется самая левая вершина уровня 2 и рассматриваются все инцидентные ей вершины уровня 3 слева направо. Если после этого все целевые вершины все еще не найдены, то берется самая левая вершина уровня 3.
Поиск двунаправленный. Идея двунаправленного поиска основана на использовании сразу двух стратегий - прямого поиска от корневой вершины и обратного от целевой вершины.
Поиск ограниченный. При этом поиске используется ограничение на глубину поиска.
Поиск слепой в ширину. Поиск, при котором вершины глубиной k ищутся после того, как будут найдены все вершины глубиной k-1.
Постановка задачи. Задание всех состояний и действий, которые можно использовать для решения задачи, начального состояния и целевых состояний, а также всех допустимых переходов между состояниями при выполнении действий.
Рассуждение или умозаключение. Ряд мыслей, изложенных в логически последовательной форме.
Система искусственного интеллекта (СИИ). Реальная производственная система, использующая в своей работе методы искусственного интеллекта.
Упрощение .Выбор правильной реак­ции на конкретную ситуацию.
Формула невыполнимая. Формула исчисления высказываний, которая на всех наборах значений ее аргументов принимает ложное значение.
Формула выполнимая. Формула называется выполнимой, если существуют наборы значений ее аргументов, на которых она принимает истинное значение, и наборы значений, на которых она принимает ложное значение.
Формула общезначимая. Формулы исчисления высказываний, истинные на всех наборах значений своих аргументов, называют.
Функция принадлежности. Функция, описывающая принадлежность элемента данному множеству.
Цель. Конечный результат, на который направлены мыслительные процессы человека.
Цепочка рассуждений обратная. Процесс, в котором заключение используется для поиска подтверждающих его данных.
Цепочка рассуждений пря­мая. Цепочка от данных к логическому заключению.
Экспертная система. Система искусственного интеллекта источником знаний для которой служат люди-эксперты в соответствующей предметной области.


Для заметок



















Для заметок
























































Яньков Владимир Юрьевич, Иглицкий Александр Михайлович
Системы искусственного интеллекта
Учебно-практическое пособие

Подписано к печати:
Тираж: 150.
Заказ №