Искусственный интеллект и экспертные системы

методы поиска в иерархических  пространствах - методы, предназначенные  для работы в областях большой  размерности;

методы поиска при неточных и неполных данных;

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

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

 

4.1 Поиск решений в одном  пространстве.

    Методы поиска  решений в одном пространстве  обычно делятся на:

поиск в пространстве состояний (рассмотрим подробно);

поиск методом редукции;

эвристический поиск;

поиск методом "генерация-проверка".

 

Поиск в пространстве состояний.

 Задача поиска в  пространстве состояний обычно  формулируется в теоретико-графовой интерпретации.

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

    Цель: определять  такую последовательность операторов, которая преобразует начальные  состояния в конечные.

    Процесс решения  в виде графа G=(Х, Y), где X={х0, х1,...} - множество (в общем случае бесконечное) вершин графа, состояний, а Y - множество, содержащее пары вершин (xi, xj), (xi, xj)?X. Если каждая пара (xi, xj) неупорядочена, то ее называют ребром, а граф - неориентированным. Если для каждой пары (xi, xj) задан порядок (направление), то пару (xi, xj) называют дугой (ориентированным ребром), а граф называют ориентированным (направленным). Вершины пары (xi, xj) называют концевыми точками ребра (дуги).

    Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (xi, xj) свидетельствует о существовании некоторого оператора f (f?F), преобразующего состояние, соответствующее вершине xi, в состояние xj. Для некоторой вершины xi выделяем множество всех направленных пар (xi, xj)?Y, т.е. множество дуг, исходящих из вершины хi, (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины xi, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине хi.

    В множестве вершин X выделяют подмножество вершин Х0 принадлежит Х, соответствующее множеству начальных состояний (So),, и подмножество вершин Хт?X, соответствующее множеству конечных (целевых) состояний (SТ). Множество Хт может быть задано как явно, так и неявно, т.е. через свойства, которыми должны обладать целевые состояния.

    Отметим, что  граф С может быть задан явно и неявно. Неявное задание графа G стоит в определении множества Х0?Х (соответствующего множеству начальных состояний) и множества операторов, которые, будучи применимы к некоторой вершине графа, дают все ее дочерние вершины.

    Итак, граф G задает  пространство состояний, т.е. пространство, в котором осуществляется поиск  решения. Построение пространства  осуществляется с помощью следующего  процесса. Берется некая вершина  х0?Х, к ней применяются все возможные операторы, порождающие все дочерние вершины. Этот процесс называют процессом раскрытия вершин. Если получена целевая вершина, то она не раскрывается. Процесс построения пространства состояний заканчивается, когда все нераскрытые вершины являются целевыми, или терминальными (т.е. вершинами, к которым нельзя применить никаких операторов). В связи с тем, что пространство состояний может содержать бесконечное количество вершин, на практике процесс порождения пространства ограничивают либо временем, либо объемом памяти.

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

поиск в глубину (сначала раскрывается та вершина, которая была построена самой последней). Рисунок 7.a.

поиск в ширину. (вершины раскрываются в том же порядке, в котором они порождаются.) Рисунок 7.б.

 

 

 

Рисунок 7. Пространство состояний, построенное поиском в глубину (а) и поиском в ширину (б).

 

    Целевые вершины  помечены черными квадратами, а  терминальные - белыми квадратами. При  использовании каждого из способов  могут быть найдены все решения.  При переборе всего пространства  оба метода будут анализировать  одинаковое количество вершин, однако  метод поиска в ширину будет  требовать существенно больше  памяти, так как он запоминает  все пути поиска (а не один, как при поиске в глубину).

 

Поиск методом редукции.

    При поиске  методом редукции решение задачи  сводится к решению совокупности  образующих ее подзадач. Этот  процесс повторяется для каждой  подзадачи до тех пор, пока  каждая из полученного набора  подзадач, образующих решение исходной  задачи, не будет иметь очевидное  решение. Процесс решения задачи  разбиением ее на подзадачи  можно представить в виде специального  направленного графа G, называемого И/ИЛИ-графом; Каждой вершине этого графа ставится в соответствие описание некоторой задачи (подзадачи). В графе выделяют два типа вершин: конъюнктивные вершины и дизъюнктивные вершины.

    Решение задачи  при поиске методом редукции (при  поиске в И/ИЛИ-графе) сводится к нахождению в И/ИЛИ-графе решающего графа.

    Цель процесса  поиска в И/ИЛИ-графе - показать, что начальная вершина разрешима, т.е. для этой вершины существует решающий граф. Определение разрешимой вершины в И/ИЛИ-графе можно сформулировать рекурсивно следующим образом:

Конечные (целевые) вершины  разрешимы, так как их решение  известно по исходному предположению.

Вершина ИЛИ разрешима  тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин.

Вершина И разрешима тола и только тогда, когда разрешима каждая из ее дочерних вершин.

 

 

 

Графическое представление  разбиения задачи на подзадачи.

     Решающий граф  определяется как подграф из  разрешимых вершин, который показывает, что начальная вершина разрешима  (в соответствии с приведенным  выше определением). На Рисунке  8 разрешимые вершины зачернены,  а неразрешимые оставлены белыми.

 

 

Пример И/ИЛИ графа

     Для графа И/ИЛИ, так же как для поиска в пространстве состояний, можно определить поиск в глубину и поиск в ширину как в прямом, так и в обратном направлении. На Рисунке 9 приведен пример поиска в ширину (Рисунок 9.а) и поиска в глубину (Рисунок 9.б). На рисунке вершины пронумерованы в том порядке, в котором они раскрывались, конечные вершины обозначены квадратами, разрешимые вершины зачернены, дуги решающего графа выделены двойными линиями.

 

 

Рисунок 9.Пример разбиения  задачи на подзадачи при поиске в  ширину(а) и при поиске в глубину(б).

 

Эвристический поиск.

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

Поиск методом "генерация-проверка".

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

4.2. Поиск решений в  иерархии пространств. 

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

Методы поиска решения  в иерархических пространствах  обычно делятся на:

поиск в факторизованном  пространстве;

поиск в фиксированном  множестве пространств;

поиск в изменяющемся множестве  пространств.

 

Поиск в факторизованном  пространстве.

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

Поиск в фиксированном  множестве пространств.

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

Поиск в изменяющемся множестве  иерархических пространств.

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

возможно осуществить частичное упорядочение понятий области, приемлемое для всех решаемых задач;

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

 

4.3. Поиск решений в  альтернативных пространствах. 

     Рассмотренные  выше методы поиска исходят  из молчаливой предпосылки, что  знания о предметной области  и данные о решаемой задаче  являются точными и полными  и для них справедливо следующее: 

все утверждения, описывающие  состояние, являются истинными;

применение оператора  к некоторому состоянию формирует  некоторое новое состояние, описание которого состоит только из истинных фактов.

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

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

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

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

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