logo
Учебник_Final

4.6. Методы поиска, реализованные в экспертных системах

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

Рассмотрим некоторые известные методы.

Слепой поиск

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

Рис. 4.4. Методы поиска

Метод редукции

Данный метод описывается с помощью и/или-графа. Реализация задачи подразумевает ее разбиение на совокупность подзадач, каждая из которых представляется дугой графа. Каждая дуга графа имеет свое назначение. Различают дизъюнктивные ветви (дуги «или») и конъюнктивные дуги (дуги «и»).

При выполнении подзадач с помощью дуги «или» должна быть выполнена хотя бы одна из подзадач текущей задачи. При реализации дуги «и» должны быть выполнены все подзадачи. Конъюнктивные дуги на графе объединяются специальным значком в виде дужки (рис. 4.5). При поиске результата на «и/или»-графе обычно применяются стратегии поиска «вширь» и «вглубь».

Рис. 4.5. Метод редукции

Эвристический метод поиска

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

Метод поиска с помощью генерации и проверки

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

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

Метод поиска в иерархических пространствах

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

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