Вопрос 6. Методы поиска решений в экспертных системах.

 

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

системах, можно классифицировать следующим образом:

1. методы поиска в одном пространстве – предназначены для использования в следующих условиях: области небольшой размерности, полнота модели, точные и полные данные; ·методы поиска в иерархических пространствах – предназначены для работы в областях большой размерности;
2. методы поиска при неточных и неполных данных;
3. методы поиска, использующие несколько моделей, предназначены для работы с областями, для адекватного описания которых одной модели недостаточно.

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

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

· поиск в пространстве состояний;

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

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

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

Задача поиска в пространстве состояний обычно формулируется в теоретико-графовой интерпретации. Поиск в пространстве состояний естественно представить в виде ориентированного графа. Наличие пары (x_i, x_j) свидетельствует о существовании некоторого оператора f (f Î F), преобразующего состояние, соответствующее вершине x_i в состояние х_j. С точки зрения поиска в пространстве состояний для некоторой вершины x_i уместно выделить множество всех направленных пар (x_i, x_j) Î Y, т.е. множество дуг, исходящих из вершины х_i (родительской вершины), и множество вершин (называемых дочерними вершинами), в которые эти дуги приводят. Множество дуг, исходящих из вершины х_i, соответствует множеству операторов, которые могут быть применены к состоянию, соответствующему вершине x_i.

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

Рисунок 2. Теоретико-графовая интерпретация поиска в пространстве.

 

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

Рисунок 3. Теоретико-графовая интерпретация поиска методом индукции.

 

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

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

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

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

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

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

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

 

⇐ Предыдущая1234Следующая ⇒

Поделиться: