дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
состоящая из узлов, хранящих информацию (или знания, и ребер, соединяющих узлы. Ребра иногда называют связями, или дугами, а узлы — вершинами. На рис. 3.1 показано бинарное дерево общего видав котором имеются нуль, одно или два ребра в расчете на каждый узел. В ориентированном дереве на самом верхнем уровне иерархии находится корневой узел, а на самых нижних уровнях — листовые узлы. Дерево может рассматриваться как семантическая сеть специального типа, в которой каждый узел, кроме корневого, имеет точно один родительский узел и нуль или больше дочерних узлов. Бинарное дерево обычного типа может содержать не больше двух дочерних узлов в расчете на каждый узел, причем левый и правый дочерние узлы различаются. Рис. 3.1. Бинарное деревосопровождаемого передачей информации от одного слоя сети к другому, в результате чего происходит модификация весовых коэффициентов, возникает обратная связь. Как показано на риса, простой граф не имеет связей, которые возвращаются непосредственно в сам узел, те. петель. Контуром, или циклом, называется путь через граф, который начинается и оканчивается водном и том же узле в качестве примера можно указать путь АВСА на риса. Ациклическим графом называется граф, не имеющий циклов. Связный граф — это граф, в котором имеются связи, протянувшиеся ко всем узлам (см. рис. 3.2, б. А на рис, в показан граф сориентированными связями, называемый ориентированным графом, в котором имеется также петля. Ориентированный ациклический граф называется решеткой, пример решетки см. на рис. 3.2, л. Дерево с единственным путем от корня к его единственному листовому узлу называется вырожденным деревом. На рис. 3.2, д показаны вырожденные бинарные деревья стремя узлами. Как правило, в дереве стрелки явно не показаны, поскольку подразумевается, что стрелки всегда направлены вниз. Деревья и решетки имеют иерархическую структуру (в которой родительские узлы находятся на более высоких уровнях по сравнению с дочерними, поэтому являются удобным средством классификации объектов. Примером может служит генеалогическое дерево, которое показывает родственные связи и родословную близких людей. Еще одной областью применения деревьев и решеток является принятие решений; используемые при этом структуры называются деревьями решений, или решетками решений, и очень широко применяются для формирования простых рассуждений. В данной главе для обозначения и деревьев, и решеток будет использоваться термин структура. Структура, применяемая в процессе Глава 3. Методы логического вывода 196 Рис. 3.2. Примеры простых графов принятия решений, или структура решений, является одновременно и схемой представления знаний, и методом формирования рассуждений о содержащихся в ней знаниях. На рис. 3.3 показан пример дерева решений, предназначенного для классификации животных. Этот пример относится к классической игре, состоящей из двадцати вопросов. В узлах содержатся вопросы, ребра "да" и "нет" показывают возможные ответы на вопросы, а в листовых узлах приведены предположения, касающиеся того, как называется искомое животное. С другой стороны, на рис. 3.4 представлена небольшая часть дерева решений, предназначенного для классификации кустарников малины различных видов. В отличие от деревьев, применяемых в компьютерных науках, допускается изображать деревья классификации с корневым узлом, находящимся в нижней части. В нижней части рисунка показан корень, от которого отходит ребро к узлу "Листья простые" и еще одно ребро к узлу "Листья — сложные. Процесс принятия решения начинается с нижнего узла, с помощью которого выявляются наиболее важные характерные особенности, например, касающиеся того, являются ли листья простыми или сложными. А по мере продвижения вверх по дереву приходится выяснять более конкретные подробности, требующие более внимательного наблюдения. Это означает, что вначале исследуются более крупные множества 3.2. Деревья, решетки и графы 197 Действительно ли является очень большим Издает писк Имеет длинную шею? Предположить, Предположить, что это белка что это мышь Предположить, что это жираф Имеет хобот Любит находиться вводе Предположить, что это слон Предположить, что это носорог Предположить, что это гиппопотам Рис. 3.3. Дерево решений, на котором представлены знания о животных альтернатива затем процесс принятия решений начинает сходиться к тем возможностям, которые представлены с помощью все меньших и меньших множеств. Это — удобный способ организации процесса принятия решений сточки зрения затрат времени и усилий для проведения все более детальных наблюдений. Если все решения являются бинарными, то появляется возможность легко построить бинарное дерево решений, которое становится очень эффективным. Для ответа на каждый вопрос приходится переходить вниз (или вверх) на один уровень дерева. Один вопрос позволяет принять решение о выборе одного из двух возможных ответов, с помощью двух вопросов вырабатывается решение о выборе одного из четырех возможных ответов, три вопроса позволяют выбрать один из восьми возможных ответов и т.д. Если бинарное дерево сконструировано таким образом, что во всех листовых узлах представлены ответы, а на всех ребрах, ведущих вниз, заданы вопросы, то дерево решений позволяет представить максимальное количество ответов на N воoпроoсоoвB, равное 2. Например, десять вопросов позволяют классифицировать одно из 1024 животных, а двадцать находить один из 1 048 576 возможных ответов. Еще одной полезной особенностью деревьев решений является то, что они могут быть самообучающимися. Если предположение оказывается ошибочным, то вызывается процедура, с помощью которой пользователю передается просьба Глава 3. Методы логического вывода 198 Обыкновенная малина Щетинистые волоски, не расширяющиеся на конце Западная малина Ствол имеет небольшой восковой налет (который иногда полностью отсутствует явно обнаруживаются волоски плоды красного цвета Ствол имеет отчетливо выраженный восковой налет плоды черного цвета Душистая малина Нижняя поверхность листа зеленая Нижняя поверхность листа и иногда ствол имеют восковой налет Листья простые Листья сложные Листья растения Рис. 3.4. Часть дерева решений, предназначенного для классификации кустарников малины чтобы он указал новый, правильный классификационный вопрос и дал ответы, связанные с вариантами выбора "да" и "нет. После этого динамически создаются новые родительский узел, ребра и листовые узлы, которые добавляются к дереву. В первоначальной программе, написанной на языке BASIC, знания хранились в операторах РАТА. После того как пользователь обучал программу распознаванию нового животного, происходила автоматическая регистрация результатов обучения, входе которой программа формировала новые операторы содержащие информацию о новом животном. Для обеспечения максимальной эффективности знания о животных хранились в виде деревьев. А язык CLIPS позволяет создавать автоматически новые правила (входе того как программа усваивает новые знания) с помощью ключевого слова build Такая процедура автоматизированного приобретения знаний является очень полезной, поскольку в простых случаях позволяет преодолеть узкое место в приобретении знаний, которое будет рассматриваться в главе 6. 3.3. Пространства состояний и пространства задач 199 IF QUESTION = "IS IT VERY BIG?" AND RESPONSE = "NO" THEN QUESTION := "DOES IT SQUEAK?" IF QUESTION = "IS IT VERY BIG?" AND RESPONSE = "YES" THEN QUESTION := "DOES IT HAVE А LONG NECK?" Аналогичная процедура выполняется и для других узлов. При этом в листовом узле вырабатывается не вопроса ответ ANSWER. Кроме того, могут быть предусмотрены соответствующие процедуры, передающие пользователю запросы на ввод данных и позволяющие создавать новые узлы при обнаружении случаев неправильной классификации. Безусловно, структуры решений являются очень мощными инструментальными средствами классификации, но их возможности ограничены, поскольку структуры решений, в отличие от экспертных систем, не позволяют использовать переменные. Экспертные системы — это инструментальные средства общего назначения, а непростые классификаторы. Пространства состояний и пространства задач Для решения многих практических задач могут применяться графы. Один из удобных методов описания поведения некоторого объекта состоит в определении графа, называемого пространством состояний. Состояние — это коллекция характеристик, которые могут использоваться для определения состояния, или статуса, объекта. Пространство состояний — это множество состояний, с помощью которого представляются переходы между состояниями, которым подвергается объект. В результате перехода объект попадает из одного состояния в другое. Примеры пространств состояний В качестве простого примера использования пространства состояний рассмотрим покупку безалкогольного напитка в автомате. По мере того как в автомат вкладывают монеты, происходит переход из одного состояния в другое. На рис. 3.5 показана диаграмма пространства состояний, подготовленная на основе того предположения, что в распоряжении покупателя имеются только 25-центовые монеты) и 5-центовые монеты (Ха для приобретения напитка необходимо опустить Структуры решений могут быть механически преобразованы в продукционные правила. Такая процедура легко осуществляется с помощью поискав ширину в дереве и выработки в каждом узле правил IF — Например, дерево решений, приведенное на рис. 3.3, может быть частично преобразовано вправила следующим образом Глава 3. Методы логического вывода 200 в автомат 55 центов. Если бы мы предусмотрели возможность использовать монеты другого достоинства, например 10- и 50-центовые, то диаграмма стала бы сложнее, поэтому они здесь не показаны. Рис. Диаграмма состояний автомата по продаже безалкогольных напитков, который принимает 25-центовые монеты (Q) и 5- центовые монеты (Х) Состояния обозначены кружками, а возможные переходы в другие состояния стрелками. Начальное состояние и состояние успеха обозначены двойными кружками, чтобы их было проще отличать от других состояний. Обратите внимание на то, что данная диаграмма представляет собой взвешенный ориентированный граф, в котором весовыми коэффициентами являются монеты разного достоинства, которые могут быть введены в автомат в каждом состоянии. Эта диаграмма называется также диаграммой конечного автомата, поскольку описывает конечное количество состояний автомата. Термин автомат используется в очень общем смысле. Автоматом может быть реальный объект, алгоритм, концепция и т.д. С каждым состоянием связаны действия, позволяющие перевести автомат в другое состояние. Нов каждый конкретный момент времени данный автомат может находиться только водном состоянии. После того как автомат при. Пространства состояний и пространства задач 201 нимает входные данные в каком-либо состоянии, он переходит из этого состояния в другое. Если даны только правильные входные данные, то автомат переходит изначального состояния в состояние успеха, или в конечное состояние. А если некоторое состояние не рассчитано на получение определенных входных данных, то автомат зависает в этом состоянии. Например, данный конечный автомат по продаже безалкогольных напитков не рассчитан на получение монет достоинством в 10 центов. Поэтому если кто-то вложит в автомат 10-центовую монету, то ответ будет неопределенным. Это означает, что качественный проект должен предусматривать возможность неправильного ввода данных в любом состоянии ив связи с этим переход в состояние ошибки. А состояние ошибки проектируется таким образом, чтобы в нем выдавались соответствующие сообщения об ошибках и предпринимались все необходимые корректирующие действия. Конечные автоматы часто используются в компиляторах и других программах для определения того, являются ли действительными входные данные. Например, на рис. 3.6 показана часть конечного автомата, позволяющего проверить, являются ли действительными входные строки. Символы входных строк проверяются один за другим. Автомат принимает только символьные строки WHILE, WRITE и BEGIN. Показаны стрелки, отходящие от состояния BEGIN и соответствующие успешно принятым входным данным, а также стрелки, которые обеспечивают переход в состояние ошибки под действием неправильных входных данных. В целях повышения эффективности некоторые состояния (например, тона которое указывают стрелки "L" и "Т) используются для проверки и строки WHILE, и строки WRITE. Примечание. Показаны только некоторые из переходов в состояние ошибки. Диаграммы состояний являются также полезным средством описания решений задач. В приложениях такого рода пространство состояний может рассматриваться как пространство задач, в котором одни состояния соответствуют промежуточным этапам решения задача другие соответствуют ответам. В пространстве задач может быть несколько состояний успеха, соответствующих возможным решениям. Для поиска решения задачи в пространстве задач необходимо найти действительный путь от начального узла (формулировки задачи) до узла успеха (ответа). Дерево решений, применяемое для классификации животных, может рассматриваться как пространство задач, в котором ответы "да" или "нет" соответствуют вопросам, определяющим переходы между состояниями. Еще один пример пространства задач обнаруживается в решении классической задачи с обезьяной и бананами, которая показана на рис. 3.7. Задача состоит в том, чтобы дать обезьяне инструкции с указаниями, как получить бананы, свисающие с потолка. Бананы находятся вне досягаемости обезьяны. В комнате имеются кушетка и лестница. Исходная начальная конфигурация обычно предусматривает 202 Глава 3. Методы логического вывода Рис. 3.6. Часть конечного автомата для определения допустимых строки такое положение, в котором обезьяна находится на кушетке. Инструкции могут состоять в следующем спрыгнуть с кушетки подойти к лестнице передвинуть лестницу туда, где находятся бананы вскарабкаться на лестницу схватить бананы Инструкции могут изменяться в зависимости от начальной конфигурации, в которой находятся обезьяна, кушетка и лестница. Количество начальных состояний велико, поэтому на диаграмме не показаны специальные двойные кружки, обозначающие начальное состояние. Например, еще одним возможным начальным состоянием является тов котором обезьяна находится на кушетке, стоящей под бананами. В таком случае обезьяна должна убрать кушетку с этого места, прежде чем пододвинуть лестницу под бананы. А в простейшем начальном состоянии обезьяна уже находится на лестнице, стоящей под бананами. Безусловно, решение указанной задачи для человека кажется очевидным, но оно требует значительного объема рассуждений. Практическим приложением системы формирования рассуждений, подобных этой, является выдача инструкций для робота, касающихся решения задачи. Общим решением должна стать система формирования рассуждений, которая не исходит из того предположения, что все объекты в рассматриваемой среде постоянно находятся на одном и том же ме- 203 3.3. Пространства состояний и пространства задач Кушетка под бананами Обезьяна на кушетке Обезьяна на полу Обезьяна должна спрыгнуть r кушетки Кушетка обнаружена под бананами Обезьяна должна передвинуть кушетку Кушетка обнаружена не под бананами Кушетка не под бананами Обезьяна должна перейти в другое место Обезьяна обнаружена на лестнице Лестница не под бананами Лестница обнаружена не под бананами Лестница обнаружена под бананами Обезьяна должна передвинутьлестницу Лестница под бананами Обезьяна должна взобраться на лестницу Схватить бананы Рис. Пространство состояний для задачи с обезьяной и бананами сте, а обеспечивает возможность справляться с самыми различными ситуациями. Решение задачи с обезьяной и бананами, основанное на использовании правил, распространяется вместе с компакт-диском с программным обеспечением CLIPS, прилагаемым к данной книге. Обезьяна на лестнице Обезьяна на лестнице Обезьяна не на Обезьяна обнаружена лестнице не на лестнице Глава 3. Методы логического вывода 204 Рис. 3.8. Задача коммивояжера В зависимости от алгоритма поиска процесс исследования путей, выполняемого в целях поиска правильного пути, может потребовать выполнения значительного объема перебора с возвратами. Например, предположим, что вначале был выбран неудачный путь АВА, затем выполнен возврат к узлу В, а от узла В безуспешно проведен поиск с использованием путей СА, СВ, CDB и CDC. Еще одним полезным приложением графов является исследование путей для поиска решения некоторой задачи. На риса приведена простая сеть для задачи коммивояжера. Предположим, что в этом примере задача состоит в том, чтобы найти полный путь от узла А, в котором посещаются все прочие узлы. Как обычно предусмотрено в задаче коммивояжера, ни один узел не должен посещаться дважды. На рис. 3.8, б в форме дерева приведены всевозможные пути, начинающиеся от узла А. На этом графе жирными линиями показаны правильные пути АВ.ОСА и ACDBA. |