СВЯЗЫВАНИЕ ПЕРЕМЕННЫХ
СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ
Константные, с переменными.
При поиске решения ПРОЛОГ может выполнять следующие операции: сопоставление с образцом, связывание переменных, откат и освобождение переменных.
Рассмотрим эту операцию на примере простой константной цели.
| CLAUSES man(tom). man(jon). man(bob). | GOAL man(jon). Требуется доказать, что Джон - мужчина. |
Метод решения прост - надо просмотреть все предикаты man(symbol) и сопоставить аргументы предложения-цели и предложения-факта. Если они совпадают - цель доказана. Пролог подтверждает YES, если такого факта нет, то NO. Но это не значит, что Джон не мужчина. Просто такого факта в базе знаний нет!
Операция сравнения цели с предложениями программы называется операцией сопоставления с образцоми начинается сверху вниз, а сравнение параметров слева направо.
Поиск составной константной цели отличается тем, что операция сопоставления производится необходимое количество раз.
| CLAUSES father(jon, lisa). father(bob, tom). father(bob, pat). man(jon). man(tom). man(bob). woman(lisa). woman(pat). | GOAL father(bob, pat),woman(pat). Является ли Пат дочерью Боба? |
Чтобы доказать составную цель, необходимо доказать все подцели слева направо. В данном случае 1 цель совпадает с 3 предложением, а вторая цель - с 8 предложением. То есть цель доказана.
Рассмотрим операцию на примере поиска простой цели с переменными.
| CLAUSES father(jon, lisa). father(bob, tom). father(bob, pat). | GOAL father(Who, tom). Кто отец Тома? |
Пролог начинает операцию сопоставления с образцом (сверху вниз), причем сопоставляются только константы цели и образца. Первым подходящим предложением является второе:
цель father(Who, tom). образец father(bob, tom).
Далее Пролог делает операцию связывания свободной переменнойWhoс константой образца. Свободная переменная становится связанной переменной со значением bob.
Прологу удалось найти факт, не противоречащий цели, связав переменную Who. Цель доказана. Пролог выводит значение связанной переменной Who=bob. Операцию связывания называют также операцией унификации, а программы ее осуществляющие - программами унификации. Программы унификации ищут все возможные решения.
При поиске составной цели с переменными также производится связывание переменных, а в случае неудачи – откат и возвращение на предыдущую позицию.
| CLAUSES father(jon, lisa). father(bob, tom). father(bob, pat). man(jon). man(tom). man(bob). woman(sui). woman(pat). | GOAL father(bob, X),woman(X). Есть ли у Боба дочь? |
Пролог начинает доказывать 1 цель. Образец father(bob, X) удается сопоставить со вторым предложением father(bob, tom). При этом свободная переменная Х связывается значением X=tom. Подцель доказана.
Пролог переходит к доказательству второй подцели - woman(tom). Вторая цель не может быть доказана, так как такого факта нет. НЕУСПЕХ. Но решение то есть. Просто первое связывание оказалось неудачным.
Пролог освобождает связанную переменную и возвращается (откатывается) к доказательству первой подцели, так как еще есть предложения с которыми можно сопоставлять.
Второе сопоставление образца father(bob, X) с предложением father(bob, pat) связывает X значением pat. Доказательством второй подцели - woman(pat) является 8 предложение. Пролог нашел решение:
X=pat
1 Solution
Рассмотрим дерево решений (поиска) для предыдущего примера.
При доказательстве 1 подцели father(bob, X) возможны три варианта. Пролог просматривает их поочередно: первый отбрасывает, второй – подходит, поэтому «разворачивает» эту ветвь до конца. При доказательстве 2-ой подцели просматривает два варианта. Таким образом, возникает шесть возможных вариантов решения. Такой метод поиска, когда Пролог обходит дерево решений сверху вниз и слева направо, называется поиском в глубину. Схема дерева решений представлена на рис. 1. Крестиком помечены ложные пути, т.е. откат.
 |
Рис. 1. Дерево решений для цели father(bob, X),woman(X).
Сопоставление с предложением правилом. Предложение правило состоит из двух частей: головы и хвоста (заголовка и тела). В этом случае цель сопоставляется с заголовком правила. Имеющиеся свободные переменные связываются с соответствующими значениями. Если правило, в свою очередь содержит в заголовке переменные, то свободные переменные цели связываются со свободными переменными заголовка без значения. Затем Пролог переходит к доказательству подцелей правила.
Пример 1.
CLAUSES
likes(bob, nut). Боб любит орехи
likes(jim, apple). Джим любит яблоки
likes(tom, X):-likes(jim,X). Том любит то, что любит Джим
GOAL
likes(tom,Y). Что любит Том?
Здесь подходит 3-ий предикат. Но он является правилом. Поэтому переменная Y связывается с переменной X правила. Затем Пролог начнет доказывать подцель likes(jim,Y). Такой факт находится Y=apple. Тогда X=apple. Том любит яблоки.
Пример 2.
| тип(копытное, животное). тип(рыба, животное). вид(зебра, копытное). вид(сельдь, рыба). вид(акула, рыба). живет(зебра, земля). живет(лягушка, земля). живет(лягушка, вода). живет(акула, вода). может_плавать(Y):- тип(Х, животное), вид(Y, X), живет(Y, вода). | GOAL может_плавать(Who), write("может плавать", Who). |
Решение.
1. Y=Who. Докажем три подцели
тип(X,животное),
вид(Who, X),
живет(Who, вода).
Первая подцель
X=копытное (1-я строка).
Вторая подцель
вид(Who,копытное) Who=зебра
Третья цель
живет(зебра, вода) не разрешается Откат
2. Первая подцель
X=рыба
Вторая подцель
вид(Who,рыба) Who=сельдь
Третья цель
живет(сельдь, вода) не разрешается Откат
3. Вторая подцель
вид(Who,рыба) Who=акула
Третья цель
живет(акула, вода) разрешается.
Решение: может плавать акула.
ВНЕШНЯЯ И ВНУТРЕННЯЯ ЦЕЛЬ
Внешней считается цель (запрос), которая задается в результате диалога с пользователем, т.е. после запуска программы в окне Dialog. В таком случае программа находит все правильные решения.
Внутренняя цель включается непосредственно в саму программу. Создается отдельный раздел goal. Каждое предложение, задающее цель, должно оканчиваться точкой. После нахождения первого правильного решение, выполнение программы прекращается. Для вывода всех правильных решений используется специальный предикат fail.