МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Экспертные системы. Классификация экспертных систем. Разработка простейшей экспертной системы

    компоненты систем, основанных на знаниях, является выбор метода поиска

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

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

    определению направления поиска и способа его осуществления. Процедуры,

    реализующие поиск, обычно “зашиты” в механизм вывода, поэтому в большинстве

    систем инженеры знаний не имеют к ним доступа и, следовательно, не могут в

    них ничего изменять по своему желанию.

    При разработке стратегии управления выводом необходимо ответить на два

    вопроса:

    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. Вершины и указатели, построенные в

    Страницы: 1, 2, 3, 4, 5, 6


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.