103 Методы поиска решений в экспертных системах. Логический и эвристический методы поиска решений в экспертных системах.

Дисциплина «Интеллектуальные информационные системы»

Существует 5 методов поиска: поиск как основа функционирования ЭС; Метод эвристического поиска, Формализация задач в пространстве состояний; Метод поиска в глубину и ширину; Представление пространства состояний в виде базы знаний.

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

В ЭС поиск цели выполняется автом-ки, на основе метода ЭС, к-ый: реализует возможность выбора; позволяет выполнять шаги от начального состояния к новым состояниям, более или менее близким к цели. Методы поиска ЭС отыскивают цель, шагая от одного состояния сис к др и распознают ситации, когда они находят цель или попадают в тупик. На промежуточных стадиях вычисляется число с помощью которого программа поиска оценивает свой ход и определяет дальнейшее направление. Для определения следующего шага поиска программа использует два метода: поиск в ширину и поиск в глубину. При поиске в глубину программа полностью исследует сначала один вариант пути, а потом остальные. Как правило сначала исследуется левая ветвь дерева, когда программа заходит в тупик, она возвращается на верх и выбирает следующий вариант пути.

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

При методе в ширину программа сначала переходит к соседним вершинам, с лева на право (к 1-ой,2-ой,3-ей и т.д), пока не будет найдена цель. В отличии от поиска в глубину, поиск в ширину применяется тогда, когда ветви поиска в дереве имеют разную длину.

Метод эвристического поиска

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