|
НАЗАД
ПРОГРАММА
большой(медведь). % Предложение 1
большой(слон). % Предложение 2
маленький(кот). % Предложение 3
коричневый (медведь). % Предложение 4
черный (кот). % Предложение 5
серый(слон). % Предложение 6
темный(Z):- черный(Z). % Предложение 7:
% любой черный
% объект является темным
темный( Z):- коричневый( Z). % Предложение 8:
% любой коричневый
% объект является темным
ВОПРОС
?- темный(X), большой( X) % Кто одновременно темный
% и большой?
Знаком % в Прологе обозначается комментарий.
ШАГИ ВЫЧИСЛЕНИЯ
- (1) Исходный список целевых утверждений: темный( X), большой( X).
- (2) Просмотр всей программы от начала к концу и
- поиск предложения, у которого голова сопоставима с первым целевым утверждением: темный(X). Найдена формула 7: темный(Z):- черный( Z). Замена первого целевого утверждения конкретизированным телом предложения 7 - порождение нового списка целевых утверждений. черный(X),большой(X).
- (3) Просмотр программы для нахождения предложения, сопоставимого с черный(X). Найдено предложение 5: черный (кот). У этого пред-ложения нет тела, поэтому список целей при соответствующей конкретизации сокращается до большой(кот)
- (4) Просмотр программы в поисках цели большой(кот). Ни одно предложение не найдено. Поэтому происходит возврат к шагу (3) и отмена конкретизации X = кот. Список целей теперь снова черный(X), большой( X)
- Продолжение просмотра программы ниже предло¬жения 5. Ни одно предложение не найдено. Поэтому возврат к шагу (2) и продолжение просмотра ниже предложения 7. Найдено предложение (8): темный(Z) :- коричневый( Z). Замена первой цели в списке на коричневый(Х), что дает коричневый( X),большой( X)
- (5) Просмотр программы для обнаружения предложе¬ния, сопоставимого коричневый(X). Найдено предложение коричневый(медведь). У этого предложения нет тела, поэтому список целей уменьшается до большой(медведь).
- (6) Просмотр программы и обнаружение предложения большой(медведь). У него нет тела, поэтому список целей становится пустым. Это указыва¬ет на успешное завершение, а соответствующая конкретизация переменных такова: X = медведь.
На рисунке 2 приведены фрагменты программы и ответ на запрос dark(X),big(X)( коричневый( X),большой( X)).
Рисунок 2 - Фрагмент программы и ответ на запрос dark(X),big(X)
Процесс вычисления запроса удобно представить в виде дерева поиска. Дерево поиска ответа на любой запрос строится следующим образом.
- Корнем дерева является исходный вопрос Q.
- Вершины дерева соответствуют целям (резольвентам), которые в общем случае являются конъюнктивными. В каждой выделяется одна цель.
- Для каждого утверждения программы, заголовок которого унифицируется с выделенной в вершине целью, имеется ребро, выходящее из этой вершины.
- На ребрах дерева записываются подстановки, которые образуются в результате унификации выделенной в вершине цели и утверждения.
- Лист дерева называется успешной вершиной, если существует подстановка, удовлетворяющая последнюю цель в списке целей. Лист дерева называется безуспешной вершиной, если нет в программе утверждений, которые сопоставимы с выделенной в вершине целью.
Рассмотрим пример построения дерева поиска для запроса: dark(X),big(X).
Когда выполнение программы достигает тупиковой вершины, отмеченной словом "неуспех", автоматически происходит возврат на предыдущий уровень дерева поиска, так как в Пролог-систему встроен механизм возврата (backtracing). Выполнение алгоритм поиска решения можно представить как обход лабиринта, где на каждой развилке приходится выбирать новый путь. При попадании в тупик, т.е. на безуспешную вершину (лист дерева поиска), надо следовать в обратном направлении до первого перекрестка, и выбирать другой не опробованный путь, Процесс продолжается до тех пор, пока не встретится успешная вершина или будут пройдены все пути дерева поиска.
Рисунок 3 - Дерево поиска для запроса: dark(X),big(X).
НАЗАД
|
