рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Экспертные системы. Классификация экспертных систем. Разработка простейшей экспертной системы

Экспертные системы. Классификация экспертных систем. Разработка простейшей экспертной системы - раздел Программирование, Содержание Глава 1. Экспертные Системы, Их Особенности. Применение Экспертны...

Содержание Глава 1. Экспертные системы, их особенности. Применение экспертных систем.История развития. 1. Определение экспертных систем. Главное достоинство и назначение экспертных систем. 2. Отличие экспертных систем от других программных продуктов. 3. Отличительные особенности. Экспертные системы первого и второ- го поколения. 4. Области применения. а Медицинская диагностика. б Прогнозирование. в Планирование. г Интерпретация. д Контроль и управление. е Диагностика неисправностей в механических и электрических устройствах. ж Обучение. 5. Критерии использования экспертных систем для решения задач. 6. Ограничения в применении экспертных систем. 1.7. Преимущества экспертных систем перед человеком-экспертом. 8. История развития экспертных систем. 1. Основные линии развития экспертных систем. 2. Проблемы, возникающие при создании экспертных систем. Перспективы развития.

Глава 2. Структура систем, основанных на знаниях. 1. Категории пользователей экспертных систем. 2.2. Подсистема приобретения знаний. 3. База знаний. 4. Подсистема вывода. 1. Подсистема вывода, способы логического вывода. 2. Компонента вывода. 3. Управляющий компонент. 5. Объяснение. Глава 3. Стратегии управления выводом. 1. Разработка стратегии управления выводом. 2. Повышение эффективности поиска. а Сопоставление методов поиска в глубину и в ширину. б Альфа-бета алгорнтм. в Разбиение на подзадачи. г Использование формальной логики при решении задач. 3. Представление задач в пространстве состояний. 1. Описание состояний. 2. Состояния и операторы. 3. Запись в виде графа. Глава 4. Методы поиска в пространстве состояний. 1. Процессы поиска на графе. 2. Методы полного перебора. 1.Метод полного перебора. 2. Метод равных цен. 3. Метод перебора в глубину. 4. Изменения при переборе на произвольных графах. 5. Обсуждение эвристической информации. 6. Использование оценочных функций. 7. Использование других эвристик. 1. Перебор этапами. 2. Ограничение числа дочерних вершин. 3. Поочередное построение дочерних вершин. Приложение 1. Приложение 2. Введение Экспертные системы ЭС возникли как значительный практический результат в применении и развитии методов искусственного интеллекта ИИ - совокупности научных дисциплин, изучающих методы решения задач интеллектуального творческого характера с использованием ЭВМ. Область ИИ имеет более чем сорокалетнюю историю развития. С самого начала в ней рассматривался ряд весьма сложных задач, которые, наряду с другими, и до сих пор являются предметом исследований автоматические доказательства теорем, машинный перевод автоматический перевод с одного естественного языка на другой, распознавание изображений и анализ сцен, планирование действий роботов, алгоритмы и стратегии игр. ЭС- это набор программ, выполняющий функции эксперта при решении задач из некоторой предметной области.

ЭС выдают советы, проводят анализ, дают консультации, ставят диагноз.

Практическое применение ЭС на предприятиях способствует эффективности работы и повышению квалификации специалистов.

Главным достоинством экспертных систем является возможность накопления знаний и сохранение их длительное время.

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

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

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

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

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

Глава 1. Экспертные системы, их особенности. Применение экспертных систем. 1.

Определение экспертных систем. Главное достоинство и назначение экспертных систем

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

История развития экспертных систем

Это семейство медицинских ЭС и сервисных программных средств для их по... В систему AM первоначально было заложено около 100 правил вывода и бол... Отсюда и типичные первоначальные постановки задачи по созданию ЭС Разр... Iaoiaeea iauaeoii- i?eaioe?iaaiiiai i?ia?aiie?iaaiey iniiaaia ia iiaae... База знаний База знаний- наиболее важная компонента экспертной системы...

заключение удается найти, то оно заносится в рабочее множество. Прямой вывод часто называют выводом, управляемым данными. Для иллюстрации добавим к нашему примеру базы знаний о погоде еще одно правило ЕСЛИ скоро пойдет дождь ТО нужно взять с собой зонтик. правило 2 Предположим также, что факты Небо покрыто тучами и Барометр падает имеются в рабочем множестве, а целью системы является ответ на вопрос пользователя Нужно взять с собой зонтик? При прямом выводе работа системы будет протекать следующим образом Шаг 1. Рассматривается правило 1. Его условие истинно, так как оба элемента коньюнкции имеются в рабочем множестве.

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

Если она оказалась правильной, то выбирается следующая гипотеза, детализирующая первую являющаяся по отношению к ней подцелью.

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

Переходим к правой части правила и рассматриваем в качестве текущей цели утверждения Скоро пойдет дождь. Шаг 3. Текущей цели нет в рабочем множестве. Рассмотрим правило 1, которое содержит цель в правой части. Обе компоненты его условия имеются в рабочем множестве, так что условие истинно. Применяем привило 1 в результате выводим утверждение Скоро пойдет дождь которое было нашей предыдущей целью. Шаг 4. Применяем правило 2, условием которого является данное утверждение. Получаем вывод исходного утверждения.

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

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

Такой комбинированный метод получил название циклического. Рис 4. Стратегия вывода. Поиск в глубину Обратный вывод Прямой вывод 4 Начало 1 3 поиска 2 5 2 Начало 3 6 1 поиска 4 7 Заключения Заключения Поиск в ширину Начало 8 Начало поиска 1 поиска 12 7 2 13 1 11 6 3 2 10 5 4 3 9 4 5 8 6 Заключения 7 Выше уже отмечалось, что механизм вывода включает в себя два компонента- один из них реализует собственно вывод, другой управляет этим процессом. Компонент вывода выполняет первую задачу, рассматривая имеющиеся правила и факты из рабочего множества и добавляя в него новые факты при срабатывании какого-нибудь правила.

Управляющий компонент определяет порядок применения правил. Рассмотрим каждый из этих компонентов более подробно. 2.4.2. Компонент вывода Его действия основаны на применении правила вывода, обычно называемого модус поненс, суть которого состоит в следующем пусть известно, что истинно утверждение А и существует правило вида Если А, то В , тогда утверждение В так же истинно.

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

Понять факты становиться еще сложнее, если они являются составными частями продукций, которые используют правило модус поненс для вывода заключения. Приведем такой пример ЕСЛИ Белый автомобиль легко заметить ночью И Автомобиль Джека белый ТО Автомобиль Джека легко заметить ночью Это заключение легко выведет даже ребенок, но оно оказывается не под силу ни одной из современных ЭС. Компонент вывода должен обладать способностью функционировать при любых условиях. Механизм вывода должен быть способен продолжить рассуждение и со временем найти решение даже при недостатке информации.

Это решение может и не быть точным, однако система ни в коем случае не должна останавливаться из-за того, что отсутствует какая-либо часть входной информации. 2.4.3. Управляющий компонент. Этот компонент определяет порядок применения правил, а также устанавливает, имеются ли еще факты, которые могут быть изменены в случае продолжения консультации. Управляющий компонент выполняет четыре функции 1. Сопоставление- образец правила сопоставляется с имеющимися фактами 2. Выбор- если в конкретной ситуации могут быть применены сразу несколько правил, то из них выбирается одно, наиболее подходящее к заданному критерию разрешение конфликта . 3. Срабатывание- если образец правила при сопоставлении совпал с какими- либо фактами из рабочего множества, то правило срабатывает. 4. Действие- рабочее множество подвергается изменению путем добавления в него заключения сработавшего правила.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим теперь работу подсистемы объяснения. Для получения объяснения в процессе консультации пользователь может перехватить инициативу диалога в тот момент, когда система задает очередной вопрос, переспро- сив в ответ систему, почему она его задала. Таким образом, вместо ответа на вопрос системы, пользователь может задать ей встречный вопрос ПОЧЕМУ? Почему система задала такой вопрос Система интерпретирует вопрос Почему? в понятных ей терминах дерева вывода, поднимаясь по нему на один ярус выше и находя правило, для применения которого система задает этот вопрос.

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

Ранее было установлено, что 1.1 Небо покрыто тучами. Следовательно, если 1.2 Барометр падает, то скоро пойдет дождь. Правило 1 . Двойные номера в квадратных скобках имеют следующий смысл. Для облегчения работы пользователя подсистема объяснения нумерует свои ответы номер ответа, в данном случае- 1. является первой цифрой номера, а в каждом ответе- нумерует также утверждения, о которых в нем идет речь. Пользователь может использовать двойные номера для ссылок на утверждения, не выписывая их явно. Например, номер 1.1 обозначает утверждение Небо покрыто тучами. Допустим, что пользователь хочет еще дальше проследить логику рассуждений системы и узнать, почему ей необходимо установить, скоро ли пойдет дождь. Для этого он может повторно задать ей вопрос ПОЧЕМУ? Почему необходимо установить, что скоро пойдет дождь Второй ответ системы аналогичен первому в нем указывается, что это необходимо для применения правила 2 с целью установить, что нужно взять с собой зонтик 2.0 Эта информация необходима, чтобы установить, что нужно взять с собой зонтик. Если 2.1 Скоро пойдет дождь, то нужно взять с собой зонтик.

Правило 2 . Утверждение 2.0 является исходным целевым утверждением системы.

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

Вопрос ПОЧЕМУ? позволяет проследить ход рассуждений системы от посылок к заключениям. Однако для более детального осмысления процесса вывода удобно было бы иметь возможность изучать его и в противоположном порядке- от заключений к посылкам. Для этого служит другой вопрос, который также понимает подсистема объяснений КАК N? где N- номер утверждения, выданный подсистемой объяснения на одном из предыдущих шагов диалога. Например, в ответ на вопрос КАК 2.0? Как получен утверждение 2.0? подсистема объяснения выдает информацию в правиле, которое было применено для его получения 3.1 Используется правило 2, заключением которого является, что нужно взять с собой зонтик.

Чтобы получить более подробную информацию о том, как было использовано правило 2, следует повторно задать вопрос КАК? КАК 3.1? Как было использовано правило 2 Ответ системы Ранее установлено, что 4.1 Скоро пойдет дождь. Следовательно, нужно взять с собой зонтик.

Выясним теперь, как получено утверждение 4.1 КАК 4.1? Ответ системы 5.1 Используется правило 1, заключением которого является, что скоро пойдет дождь. Наконец, выясним. как использовано правило 1 КАК 5.1? Ответ системы Ранее установлено, что 6.1 Небо покрыто тучами. 6.2 Барометр падает. Следовательно скоро пойдет дождь. Как были получены утверждения 6.1 и 6.2 пользователь помнит, поскольку он отвечал на вопросы системы относительно этих утверждений. Если все же он задаст системе вопрос КАК 6.1? или КАК 6.2 то система напомнит ему об этом. Описанная модель объяснения используется в системе MYCIN. Достоинством ее является возможность получения объяснения любого шага работы системы, недостатком- жесткая привязка к дереву вывода.

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

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

Процедуры, реализующие поиск, обычно зашиты в механизм вывода, поэтому в большинстве систем инженеры знаний не имеют к ним доступа и, следовательно, не могут в них ничего изменять по своему желанию. При разработке стратегии управления выводом необходимо ответить на два вопроса 1. Какую точку в пространстве состояний принять в качестве исходной? Дело в том, что еще до начала поиска решения система, основанная на знаниях, должна каким- то образом выбрать исходную точку поиска- в прямом или обратном направлении. 2. Как повысить эффективность поиска решения? Чтобы добиться повышения эффективности поиска решения, необходимо найти эвристики разрешения конфликтов, связанных с существованием нескольких возможных путей для продолжения поиска в пространстве состояний, поскольку требуется отбросить те из них, которые заведомо не ведут к искомому решению. 3.2. Повышение эффективности поиска В системах, база знаний которых насчитывает сотни правил, весьма желательным является использование какой- либо стратегии управления выводом, позволяющей минимизировать время поиска решения и тем самым повысить эффективность вывода.

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

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

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

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

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

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

При сведении задачи к подзадачам производится исследовании исходной задачи с целью выделения такого множества подзадач, чтобы решение некоторого определенного подмножества этих подзадач содержало в себе решение исходной задачи. Рассмотрим, например, задачу о проезде на автомобиле из Пало-Альто штат Калифорния в Кембридж штат Массачусетс. Эта задача может быть сведена, скажем, к следующим подзадачам Подзадача 1. Проехать из Пало-Альто в Сан-Франциско.

Подзадача 2.Проехать из Сан-Франциско в Чикаго. Подзадача 3. Проехать из Чикаго в Олбани. Подзадача 4. Проехать из Олбани в Кембридж. Здесь решение всех четырех подзадач обеспечило бы некоторое решение первоначальной задачи. Каждая из подзадач может быть решена с применением какого-либо метода. К ним могут быть применены методы, использующие пространство состояний, или же их можно проанализировать с целью выделения для каждой своих подзадач и т.д. Если продолжить процесс разбиения возникающих подзадач на еще более мелкие, то в конце концов мы прийдем к некоторым элементарным задачам, решение которых может считаться тривиальным. На каждом из этапов может возникнуть несколько альтернативных множеств подзадач, к которым может быть сведена данная задача.

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

Часто для решения задач либо требуется проведение логического анализа в определенном объеме, либо поиск решения существенно отличается после такого анализа. Иногда такой анализ показывает, что определенные проблемы неразрешимы. В игре в пятнадцать, например, можно доказать, что целевая конфигурация 1 не может быть получена из начальной конфигурации 2 . 1. 2. 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3.3. Представление задач в пространстве состояний 3.3.1. Описание состояний Чтобы построить описание задачи с использованием пространства состояний, мы должны иметь определенное представление о том, что собой состояния в этой задаче.

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

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

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

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

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

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

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

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

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

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

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

Такие графы носят название направленных графов. Если некоторая дуга направлена от вершины ni к вершине nj, то говорят, что вершина nj является дочерней для вершины ni, а вершина ni является родительской вершиной для nj. Может оказаться, что наши две вершины будут дочерними друг для друга в этом случае пара направленных дуг называется иногда ребром графа. В случае, когда граф используется для представления пространства состояний, с его вершинами связывают описание состояний, а с его дугами- операторы.

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

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

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

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

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

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

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

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

Простой алгоритм полного перебора на дереве состоит из следующей последовательности шагов 1 Поместить вершину в список, называемый ОТКРЫТ. 2 Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу. 3 Взять первую вершину из списка ОТКРЫТ и перенести ее в список ЗАКРЫТ назовем эту вершину n. 4 Раскрыть вершину n, образовав все вершины, непосредственно следующие за n. Если непосредственно следующих вершин нет, то переходить сразу же к шагу 2 . Поместить имеющиеся непосредственно следующие за n вершины в конец списка ОТКРЫТ и построить указатели, ведущие от них назад к вершине n. 5 Если какие- нибудь из этих непосредственно следующих за n вершин являются целевыми вершинами, то на выход выдать решение, получающееся просмотром вдоль указателей в противном случае переходить к шагу 2 . В этом алгоритме предполагается, что начальная вершина не удовлетворяет поставленной цели, хотя нетрудно ввести этап проверки такой возможности.

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

Мы будем называть такое поддерево деревом перебора. В методе полного перебора непременно будет найден самый короткий путь к целевой вершине при условии, что такой путь вообще существует. Если такого пути нет, то в указанном методе будет объявлено о неуспехе в случае конечных графов, а в случае бесконечных графов алгоритм никогда не кончит свою работу. Пуск Поместить S в список ОТКРЫТ нет да Пуст ли список Неудача ОТКРЫТ? Взять первую вершину из списка ОТКРЫТ и поместить ее в список ЗАКРЫТ. Обозначить эту вершину через n Раскрыть n. Поместить дочерние вершины в конец списка ОТКРЫТ. Провести от них к n указателю. нет Являются ли да какие-либо из Успех дочерних вершин целевыми? рис.6 Блок- схема программы алгоритма полного перебора для дерева. 4.2.2 Метод равных цен. Могут встретится задачи, в которых решению предъявляются какие-то иные требования, отличные от требования получения наикратчайшей последовательности операторов.

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

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

В случае деревьев перебора мы можем быть уверены, что g n является к тому же стоимостью того пути, который имеет минимальную стоимость т.к. этот путь единственный. В методе равных цен вершины раскрываются в порядке возрастания стоимости g n. Этот метод характеризуется такой последовательностью шагов 1 Поместить начальную вершину s в список, называемый ОТКРЫТ. Положить g s 0. 2 Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу. 3 Взять из списка ОТКРЫТ ту вершину, для которой величина g имеет наименьшее значение, и поместить ее в список ЗАКРЫТ. Дать этой вершине название n. В случае совпадения значений выбирать вершину с минимальными g произвольно, но всегда отдавая предпочтение целевой вершине. 4 Если n есть целевая вершина, то на выход выдать решающий путь, получаемый путем просмотра назад в соответствии с указателями в противном случае переходить к следующему шагу. 5 Раскрыть вершину n, построив все непосредственно следующие за ней вершины.

Если таковых нет переходить к шагу 2 . Для каждой из такой непосредственно следующей дочерней вершины ni вычислить стоимость g n, положив g ni g n c n, ni. Поместить эти вершины вместе с соответствующими им только что найденными значениями g в список ОТКРЫТ и построить указатели, идущие назад к n. 6 Перейти к шагу 2 . Блок- схема этого алгоритма показана на рис.7. Проверка того, является ли некоторая вершина целевой, включена в эту схему так, что гарантируется обнаружение путей минимальной стоимости.

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

Если имеется несколько начальных вершин, о алгоритм просто модифицируется на шаге 1 все начальные вершины помещаются в список ОТКРЫТ. Если состояния, отвечающие поставленной цели, могут быть описаны явно, то процесс перебора можно пустить в обратном направлении, приняв целевые вершины в качестве начальных и используя обращение оператора Г. Пуск Поместить s в список ОТКРЫТ. Положить g s 0. нет Пуст ли да список неудача ОТКРЫТ? Взять из списка ОТКРЫТ вершину с наименьшим значением g и поместить ее в список ЗАКРЫТ. Обозначить ее через n. нет Является ли n да успех вершиной цели? Раскрыть n. Вычислить значение g для дочерних вершин.

Поместить эти вершины в список ОТКРЫТ. Провести от них указатели к n. рис.7 Блок- схема программы алгоритма равных цен для деревьев. 4.3 Метод перебора в глубину.

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

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

Такой подход может привести к процессу, разворачивающемуся вдоль некоторого бесполезного пути, поэтому нужно ввести некоторую процедуру возвращения. После того как в ходе процесса строится вершина с глубиной, превышающей некоторую граничную глубину, мы раскрываем вершины наибольшей глубины, не превышающей этой границы и т.д. Метод перебора в глубину определяется следующей последовательностью шагов 1 Поместить начальную вершину в список, называемый ОТКРЫТ. 2 Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае перейти к шагу 3 . 3 Взять первую вершину из списка ОТКРЫТ и перенести в список ЗАКРЫТ. Дать этой вершине название n. 4 Если глубина вершины n равна граничной глубине, то переходить к 2 , в противном случае к 5 . 5 Раскрыть вершину n, построив все непосредственно следующие за ней вершины.

Поместить их в произвольном порядке в начало списка ОТКРЫТ и построить указатели, идущие от них к n. 6 Если одна из этих вершин целевая, то на выход выдать решение, просматривая для этого соответствующие указатели, в противном случае переходить к шагу 2 . На рис.8 приведена блок- схема для метода перебора в глубину.

Пуск Поместить s в список ОТКРЫТ. нет Пуст ли да список неудача ОТКРЫТ? Взять первую вершину из списка ОТКРЫТ и поместить ее в список ЗАКРЫТ. Обозначить ее через n. да Равна ли глубина нет n граничной глубине Раскрыть n. Вычислить значение g для дочерних вершин.

Поместить эти вершины в список ОТКРЫТ. Провести от них указатели к n Являются ли нет какие- либо да из дочерних вершин успех целевыми? рис.8 Блок-схема программы алгоритма поиска в глубину для деревьев. В алгоритме поиска в глубину сначала идет перебор вдоль одного пути, пока не будет достигнута максимальная глубина, затем рассматриваются альтернативные пути той же или меньшей глубины, которые отличаются от него лишь последним шагом, после чего рассматриваются пути, отмечающимися последними двумя шагами, и т.д. 4.4. Изменение при переборе на произвольных графах При переборе на графах, а не на деревьях, нужно внести некоторые естественные изменения в указанные алгоритмы.

В простом методе полного перебора не нужно вносить никаких изменений, следует лишь проверять, не находиться ли уже вновь построенная вершина в список ОТКРЫТ или ЗАКРЫТ по той причине, что она уже строилась раньше в результате раскрытия какой- то вершины. Если это так, то ее не нужно вновь помещать в список ОТКРЫТ. Прежде чем делать какие- либо изменения в алгоритме перебора в глубину, нужно нужно решить, что понимать под глубиной вершины в графе.

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

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

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

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

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

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

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

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

Через f n обозначим значение этой функции на вершине n. Эта функция совпадает с оценкой стоимости того из путей, идущих от начальной вершины к целевой и проходящих через вершину n, стоимость которого - наименьшая из всех таких путей. Условимся располагать вершины, предназначенные для раскрытия, в порядке возрастания их значений функции f. Тогда можно использовать некоторый алгоритм подобный алгоритму равных цен, в котором для очередного раскрытия выбирается та вершина списка ОТКРЫТ, для которой значение f оказывается наименьшим.

Будем называть такую процедуру алгоритм упорядоченного перебора. Чтобы этот алгоритм упорядоченного перебора был применен для перебора на произвольных графах а не только на деревьях, необходимо предусмотреть в нем возможность работы в случае построения вершин, которые уже имеются либо в списке ОТКРЫТ, либо в списке ЗАКРЫТ. При использовании некоторой произвольной функции f нужно учесть, что величина f для некоторой вершины из списка ЗАКРЫТ может понизится. если к ней найден новый путь f n может зависеть от пути из s к n даже для вершин из списка ЗАКРЫТ . Следовательно, мы должны тогда перенести такие вершины назад в список ОТКРЫТ и позаботиться об изменении направлений соответствующих указателей.

После принятия этих необходимых мер алгоритм упорядоченного поиска может быть представлен такой последовательностью шагов 1 Поместить начальную вершину s в список, называемый ОТКРЫТ, и вычислить f s . 2 Если список ОТКРЫТ пуст, то на выход дается сигнал о неудаче в противном случае переходи к следующему этапу. 3 Взять из списка ОТКРЫТ ту вершину, для которой f имеет наименьшее значение, и поместить ее в список ЗАКРЫТ. Дать этой вершине название n. В случае совпадения значений выбирать вершину с минимальными f произвольно, но всегда отдавая предпочтение целевой вершине. 4 Если n есть целевая вершина, то на выход выдать решающий путь, получаемый прослеживанием соответствующих указателей в противном случае переходить к следующему шагу. 5 Раскрыть вершину n, построив все непосредственно следующие за ней вершины.

Если таковых нет переходить к шагу 2 . Для такой дочерней вершины ni вычислить значение f ni . 6 Связать с теми из вершин ni, которых еще нет в списках ОТКРЫТ или ЗАКРЫТ, только что прочитанные значения f ni. Поместить эти вершины в список ОТКРЫТ и провести от них к вершине n указатели. 7 Связать с теми из непосредственно следующих за n вершинами. которые уже были в списке ОТКРЫТ или ЗАКРЫТ, меньшие из прежних или только что вычисленных значений f. Поместить в список ОТКРЫТ те из непосредственно следующих за n вершин, для которых новое значение f оказалось ниже, и изменить направление указателей от всех вершин, для которых значение f уменьшилось, направив их к n 8 Перейти к 2 . Общая структура алгоритма идентична структуре алгоритма равных цен см. рис. 7 , поэтому мы не приводим для него блок-схему.

Отметим, что множество вершин и указателей, порождаемых этим алгоритмом, образует дерево дерево перебора, причем на концах этого дерева расположены вершины из списка ОТКРЫТ. 4.6. Использование других эвристик 4.6.1. Перебор этапами.

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

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

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

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

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

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

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

Для того, чтобы воспользоваться этой идеей вместе с оценочными функциями для упорядочения вершин, в алгоритм упорядоченного перебора следует внести соответствующие изменения. Список литературы 1. И. Братко. Программирование на языке Пролог для искусст- венного интеллекта М. Мир, 1990. 2. Г. Долин. Что такое ЭС Компьютер Пресс, 1992 2. 3. Д. Р. Малпасс.

Реляционный язык Пролог и его применение. 4. Д. Н. Марселлус. Программирование экспертных систем на Турбо Прологе М. Финансы и статистика, 1994. 5. К. Нейлор. Как построить свою экспертную систему М. Энергоатомиздат, 1991. 6. Н. Д. Нильсон. Искусственный интеллект. Методы поиска решений М. Мир, 1973. 7. В. О. Сафонов. Экспертные системы- интеллектуальные помощники специалистов С Пб Санкт-Петербургская организация общества Знания России, 1992. 8. К. Таунсенд, Д. Фохт. Проектирование и программная реализация экспертных систем на персональных ЭВМ М. Финансы и статистика, 1990. 9. В. Н. Убейко.

Экспертные системы М. МАИ, 1992. 10. Д. Уотермен. Руководство по экспертным системам М. Мир, 1980. 11. Д. Элти, М. Кумбс. Экспертные системы концепции и примеры М. Финансы и статистика, 1987.

– Конец работы –

Используемые теги: Экспертные, системы, Классификация, экспертных, систем, Разработка, простейшей, экспертной, системы0.111

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

Что будем делать с полученным материалом:

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

Еще рефераты, курсовые, дипломные работы на эту тему:

Лекция 1. Тема: Операционная система. Определение. Уровни операционной системы. Функции операционных систем. 1. Понятие операционной системы
Понятие операционной системы... Причиной появления операционных систем была необходимость создания удобных в... Операционная система ОС это программное обеспечение которое реализует связь между прикладными программами и...

Разработка подсистемы вывода в диагностической экспертной системе
Работа выполнялась с 1 сентября 1998 года по 30 мая 1999 года. Тип работы инженерная является плановой разработкой института. Особенностью данной дипломной работы является возможность ее работы с… При этом подсистема вывода будет использовать экспертные знания, также допускающие элементы нечеткости и неточности.

Лекции по дисциплине Устройство и функционирование информационных систем Раздел 1. Информационные системы. Основные понятия и классификация
Раздел Информационные системы Основные понятия и классификация... Тема Информационные системы Основные понятия и... В данной теме рассматриваются общие понятия относящиеся к операционным системам определяются их типы и базовые...

Конспект лекций по дисциплине Системы и сети связи с подвижными объектами Курск 2011 Тема1: Классификация телекоммуникационных систем
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Юго Западный государственный университет... Факультет информатики и вычислительной техники...

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

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

Критерии оценки СКУД. Классификация средств и систем контроля. Классификация СКУД
Зона доступа - совокупность точек доступа, связанных общим местоположением или другими характеристиками (например, точки доступа, расположенные на… Идентификатор доступа, идентификатор (носитель идентификационного признака) -… Карточка со штриховым кодом - идентификатор с нанесенными на его поверхность полосами, ширина и расстояние между…

Основные характеристики и классификация CASE-систем. Классификация CASE-систем. Основные подсистемы CASE-систем.
На сайте allrefs.net читайте: Основные характеристики и классификация CASE-систем. Классификация CASE-систем. Основные подсистемы CASE-систем....

Разработка фрагментов оболочки экспертной системы
Экспертная система expert system, knowledge based system - это программная система, знания и умения которой сравнимы с умением и знаниями… Экспертные системы вместе с системами обработки естественных языков являются … В рамках исследования искусственного интеллекта созданы многочисленные экспертные системы для разных областей знания,…

0.086
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам