Экспертные системы

   в)  Разбиение на подзадачи. 

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

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

   Рассмотрим, например, задачу о проезде на автомобиле  из Пало-Альто (штат Калифорния) в Кембридж (штат Массачусетс). Эта задача может быть сведена, скажем, к следующим подзадачам:

Подзадача 1. Проехать из Пало-Альто в Сан-Франциско.

Подзадача 2.Проехать из Сан-Франциско в Чикаго.

Подзадача 3. Проехать из Чикаго в Олбани.

Подзадача 4. Проехать из Олбани в Кембридж.

Здесь решение всех четырех  подзадач обеспечило бы некоторое решение  первоначальной задачи.

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

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

   г)  Использование формальной логики при решении задач.  

   Часто для решения  задач либо требуется проведение  логического анализа в определенном  объеме, либо поиск решения существенно отличается после такого анализа. Иногда такой анализ показывает, что определенные проблемы  неразрешимы.

 

  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. Видно, что проблема нахождения последовательности операторов, преобразующих одно состояние в другое, эквивалентна задаче поиска пути на графе.

 

 

 

 

 

 

 

 

Список литературы:

 

1). И. Братко. Программирование на языке Пролог для искусственного интеллекта М.: Мир, 1990.

 

2).  Г. Долин. Что такое ЭС.- Компьютер Пресс, 1992/2.

 

3).  Д. Р. Малпасс. Реляционный язык Пролог и его применение.

 

4). Д. Н. Марселлус. Программирование экспертных систем на Турбо Прологе М.: Финансы и статистика, 1994.

 

5). К. Нейлор. Как построить свою экспертную систему М.: Энергоатомиздат, 1991.

 

6).  Н. Д. Нильсон. Искусственный интеллект. Методы поиска решений М.: Мир, 1973.

 

7).  В. О. Сафонов. Экспертные системы - интеллектуальные помощники специалистов С.-Пб: Санкт-Петербургская организация общества “Знания” России, 1992.

 

8).  К. Таунсенд, Д. Фохт. Проектирование и программная реализация  экспертных систем на персональных ЭВМ.- М.: Финансы и статистика, 1990.

 

9).  В. Н. Убейко. Экспертные системы М.: МАИ, 1992.

 

10). Д. Уотермен. Руководство по экспертным системам М.: Мир, 1980.

 

11). Д. Элти, М. Кумбс. Экспертные системы: концепции и примеры М.: Финансы и статистика, 1987.