Алгоритм работы инт-ра
ПРОЛОГ
Клаузы вида a&b&c -> d запис. в виде d, если a&b&c, а чаще d:-a,b,c. Клаузы м. содержать переменные: d(x,y):-a(x,y),b(x,z),c(z).
Клаузы с одинаковыми предикатами в заголовке принято размещать подряд.
При запросе ПРОЛОГ на каждый шаг пытается доказать
истинность заключения d,
кот. называют целью. Посылки
из правой части назыв. подцелями. Подразум.
что знач. между подцелями соотв. &
d:-a,b,c,d ; ->V
d:-a,b.
d:-c,d.
Подцели сопост. в порядке слева-направо, что соотв движению по деревувыводов вниз.
Суть работы инт-ра заключ-ся в поиске ответов на запросы(запрос -это фактич. гипотеза G). Запросы м.б. 2 типов:
1) d(l,m) -где l и m -const. Возможн. ответы: Да или Нет.
2) запросы 2-го типа м. содержать переменные.
отец(а,X) -такой запрос успешно сопоставл. если в базе фактов найдутся факты вида:
отец(а,b); отец(а,c);...;отец(а,n).
Возм. ответ: X=b, X=c, X=n.
Запрос отец(а,Х) считается успешно сопоставленным.
В Базе знаний для фиксации того, какая из одн. клауз обр-ся в наст. момент, ввод маркер-указатель. Запросу соотв. маркер М. Начальное положение всех маркеров на начале Базы знаний.
Если подцель является не фактом, а правилом, то ввод. маркер след. уровня иерархии.
Маркер - указатель, показывающий смещение клаузы от начала БЗ.
Начальное состояние маркера при его состоянии указывает на 1-ю клаузу.
Состояние процесса вывода оценивается множеством текущих целей различного уровня. Сдвиг любого маркера вниз возможен, когда получена ясность (сопоставляется или нет) на всех комбинациях маркеров ниже расположенных уровнях.
Маркер цели М устанавливается на начало БЗ (базы знаний).
Делается попытка согласовать цель (запрос) с 1-й клаузой БЗ. Для этого
заголовок цели сравнивается с заголовком первой клаузы:
1) Если не сопоставляется - инкремент маркера, все повторяется, если М дошел до конца БЗ выдается ответ «нет».
2) цель сопоставляется с фактом
21) если запросы с аргументами константами, выдается ответ «да», окончание работы.
22) если запрос (цель) содержит переменные, происходит означивание переменных, работа продолжится, продолжится движение М по базе знаний
3) цель сопоставляется с заголовком правила, содержащего несколько посылок или подцелей. В этом случае вводятся маркеры соответствующих подцелей М1, М2,…, установленные на начало БЗ. Подцели поочередно сопоставляются в порядке слева на право, при этом М стоит на месте, а М1 (маркер первой подцели) начинает движение по БЗ, при этом возможны те же самые ситуации. Если первая подцель согласуется, подстановки, измененные при этом фиксируются, начинается движение маркера второй подцели и т.д. Если очередная подцель не согласуется ни в каких вариантах, происходит откат на один шаг назад, подстановки изменяемые при фиксации заданного маркера отменяются и делается попытка переслать предыдущую подцель с другими подстановками. В случае успеха продолжается согласование ближайшей правой подцели, в случае не успеха откат делается ещё на один шаг назад. В худшем случае если откат дошел до крайне левой подцели, то подстановки сделанные при остановке главного маркера отменяются и маркер переводится на следующую клаузу. Если запрос содержит переменные то работа осуществляется до тех пор пока не будут выбраны все комбинации переменных при которых цель сопоставляется.