Методы обработки знаний

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

Задачу поиска в пространстве состояний можно сформулировать следующим образом:

(S, F, T)

S – это множество начальных состояний.

F – множество операторов, отображающих одни состояния в другие.

T – множество целевых состояний.

Решение задачи состоит в нахождении последовательности операторов F, которые преобразуют начальные состояния в конечные.

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

Поиск в глубину

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

Поиск в ширину

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

Поиск на основе стоимости дуг

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

Поиск с возвратом

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

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

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

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

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

Недостатком эвристического поиска является …. <пропустил> однако, в реальности часто сталкиваются с нечеткими и неполными данными.

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

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