ТОП 10:

Простой абстрактный интерпретатор логических программ.



Интерпретатор выполняет вычисления и выдает ответы «да» или «нет». Он анализирует некоторую программу Р и заданный вопрос Q и выдает ответ:

«да», если Q выводится из Р;

«нет» - в противном случае.

Если цель не выводима из программы, то интерпретатор может не выдать никакого ответа.

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

Общий алгоритм работы интерпретатора:

Шаг 1: Положить резольвенту равной Q.

Шаг 2: Цикл: Пока резольвента A1 ,…, An не пуста Do

{выбор Ai 1< i <n и поиск такого основного примера предложения A*B2 ,…, Bk (k > 0), что A* = Ai, т.е. резольвента унифицируема

Если $ A* То Exit.

Выбор следующей Ai.

Выполнение подстановки Q к резольвенте.}

Если резольвента пуста То Да.

Пример цели содержится в Q.

Иначе – Нет.

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

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

Метод, в соответствии с которым добавляются и удаляются цели в резольвентах, называется методом расписания интерпретатора.

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

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

Дерево вывода состоит из вершин и ребер и отображает цели, снимаемые в процессе вычислений. Цели соответствуют вершинам дерева.

Направленное ребро, ведущее из одной вершины в другую, соответствует переходу от снимаемой цели к производной.

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

Пример 5.2

сын(X, Y) :- родитель(Y, X), M(X). % R

? – сын(петя, вася)

1-ая редукция снимает цель и строит 2 производные цели на основе наиболее общего примера R, найденного в программе.

2-ая и 3-я редукции подтверждают поставленные подцели и не создают новых производных целей.

Дерево вывода выглядит следующим образом:

сын(петя, вася)

 

родитель(вася, петя) М(вася)

Значением логической программы Р называется множество основных единичных целей М(Р), выводимых из программы.

Примечание: Значением программы, содержащим только факты, является сама программа.

Программа Р корректна относительно некоторого заданного значения Mi, если оно является подмножеством всех значений данной программы Mi Î M(P). Другими словами, программа корректна, если вычисляет только то, что требуется.

Программа Р называется полной, если она вычисляет все возможные значения программы.

Цель называется истинной относительно подразумеваемого значения, если цель входит в данное значение (выводится из него). В противном случае цель называется ложной.

Унификация является основой автоматической дедукции и логического вывода в задачах искусственного интеллекта. Унификатором 2-х термов А и В называется такая подстановка Q, которая делает их равными: AQ = BQ.

Если существует унификатор 2-х термов, то такие термы называются унифицируемыми.

Каждый унификатор характеризует общий пример терма. Для каждого терма возможно множество общих примеров. Для 2-х унифицируемых термов существует единственный наиболее общий унификатор.

Алгоритм унификации находит наиболее общий унификатор 2-х термов, если таковой существует.

Общая схема алгоритма унификации:

T1Q = T2Q. Q - ?

Будем считать, что Q – ячейка памяти.

1) Q = 0. Стек: T1, T2, отказ = false.

2) Пока стек не пуст и не отказ

Do

считать X = Y из стека

ветвление:

1. X-переменная, не входящая в терм Y: замена всех Х в стеке и в языке программирования Q на Y.

2. Y-переменная, X-терм: замена Y на X.

3. X = Y: ® продолжить

4. X-функтор X = f(q1, … , qn) и

Y-функтор Y = f(q1, … , qn), т.е.

X и Y – составные термы:

поместить Xi и Yi " в стек.

3) Если термы не унифицируемы,

то отказ = true

иначе результат хранится в Q.

Этот алгоритм использует стек для хранения входных равенств, подлежащих решению, и язык программирования Q для хранения результата подстановки.

В цикле из стека считается и обрабатывается на каждом шаге одно равенство.

Пример 5.3

1) like(john, wine) = like(john, X).

X = wine

2) a(b, C, d(e, F)) = a(B, c, d(E, f)).

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

B = b, С = с,E = e, F = f.

 

Тема 6.

Экспертные системы (ЭС).







Последнее изменение этой страницы: 2017-02-10; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.226.243.36 (0.004 с.)