!7. Метод редукции. Поиск решения на и/или графах. Алгоритм ао*.

При решении ряда задач удобно бывает свести задачу к подзадачам – метод редукции. Задача разбивается на дочерние подзадачи и т. д. Множество задач и подзадач представляется в виде графа, содержащего вершины типа И и вершины типа ИЛИ.

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

Заключительные вершины должны быть разрешимы – это элементарные задачи. Прочие вершины разрешимы, если: - для вершин типа И разрешимы все ее подзадачи; - для вершины типа ИЛИ разрешима хотя бы одна из подзадач.

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

!8. Модели представления знаний.

К типичным моделям представления знаний относятся логическая, продукционная, фреймовая и модель семантической сети.

Каждой модели отвечает свой язык представления знаний. На практике редко удается обойтись рамками одной модели при разработке ИИС за исключением самых простых случаев.

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

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

Продукционная модель в силу своей простоты получила наиболее широкое распространение. В этой модели знания представляются в виде совокупности правил типа «ЕСЛИ — ТО». В состав экспертной системы продукционного типа входят база правил, база фактических данных (рабочая память) и интерпретатор правил, реализующий определенный механизм логического вывода. Любое продукционное правило, содержащееся в БЗ, состоит из двух частей: антецедента и консеквента. Антецедент представляет собой посылку правила (условную часть) и состоит из элементарных предложений, соединенных логическими связками И, ИЛИ. Консеквент (заключение) включает одно или несколько предложений, которые выражают либо некоторый факт, либо указание на определенное действие, подлежащее исполнению.

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

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

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

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

В последние годы термин «фреймовый» часто заменяют термином «объектно-ориентированный». Существуют специализированные языки представления знаний на основе фреймовой модели: FRL, KRL. Известны экспертные системы фреймового типа: ANALYST, МОДИС.

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

Для реализации семантических сетей существуют специальные сетевые языки: NET, язык реализации систем SIMER+MIR. Известны экспертные системы, использующие семантические сети в качестве языка представления знаний: PROSPECTOR, CASNET, TORUS.

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