«Пятеро студентов едут на велосипедах.
Их зовут Сергей, Борис, Леонид, Григорий и Виктор.
Велосипеды сделаны в пяти городах: Риге, Пензе, Львове, Харькове и Москве.
Каждый из студентов родился в одном из этих городов, но ни один из студентов не едет на велосипеде, сделанном на его родине.
Сергей едет на велосипеде, сделанном в Риге. Борис родом из Риги, у него велосипед из Пензы.
УВиктора велосипед из Москвы.
УГригория велосипед из Харькова. Виктор родом из Львова.
Уроженец Пензы едет на велосипеде, сделанном на родине Леонида. Кто из студентов родом из Москвы ?» Для решения этой проблемы можно предложить следующую про-
грамму:
Программа 18 |
|
|
DOMAINS |
|
|
|
name=simbol |
|
PREDICATES |
|
|
|
student(name) |
\* имя студента * \ |
|
gorod(name) |
\* название города *\ |
|
velo(name,name) |
\* владелец и «родина» велосипеда *\ |
|
fact(name,name) |
\* факты о принадлежности велосипедов *\ |
|
fact1(name,name) |
\* факты о месте рождения *\ |
|
rodom(name,name) |
\* описание места рождения студента *\ |
|
rodom_penza(name) \* описание для уроженца Пензы *\ |
|
CLAUSES |
|
|
\* 1 *\ |
student(X):- X=serg; X=boris; X=vict; X=grig; X=leo. |
|
\* 2 *\ |
gorod(Y):- Y=penza; Y=lvov; Y=moskva; Y=xarkov; Y=riga. |
|
\* 3 *\ |
fact(serg,piga). |
|
|
fact(boris,penza). |
|
|
fact(vict,moskva). |
|
|
fact(grig,xarkov). |
|
\* 4 *\ |
velo(X,Y):- student(X),gorod(Y), fact(X,Y), ! ; |
|
|
student(X),gorod(Y), not( fact(X, _ )),not(fact( _, Y)). |
|
\* 5 *\ |
fact1(boris,riga). fact1(vict,lvov). |
|
26
\* 6 *\ |
rodom_penza(X) :- student(X), Z=penza,not(fact1(X,_)), |
|
|
|
gorod(U),not(U=Z),velo(X,U),rodom(leo,U). |
\* 7.1 |
*\ |
rodom(X,Z) :- student(X),gorod(Z),fact1(X,Z), ! ; |
\*7.2 *\ |
student(X),not(X=leo),Z=penza,rodom_penza(X), !; |
|
\* 7.3 *\ |
student(X),gorod(Z),not(fact1(_,Z)),X=leo,not(Z=penza), |
|
|
|
student(K),not(fact1(K,_)),velo(K,Z); |
\*7.4 *\ |
student(X),not(X=leo),gorod(Z),not(Z=penza),not(fact1(_,Z)), |
|
|
|
not(fact1(X,_)), gorod(Y),not(Y=Z),velo(X,Y), |
not(rodom(leo,Z)),not(rodom(leo,Y)).
Рассмотрим описание фактов и правил в этой программе.
Первые два правила описывают возможные ограничения на значения предикатов student и gorod. Это необходимо, чтобы осуществлять допустимые подстановки при поиске решения.
Факты, обозначенные цифрой три, описывают известные нам данные о том, где сделаны велосипеды некоторых студентов.
Цифрой 4 обозначено правило, описывающее принадлежность некоторого велосипеда некоторому студенту. Правило состоит из двух альтернативных частей, разделенных знаком “;” . Первая часть правила говорит, что студент X владеет велосипедом Y, если мы знаем такой факт. Вторая часть правила позволяет делать любые подстановки, если это не противоречит известным фактам. Предикат отсечения “!” здесь прекращает поиск новых вариантов, если оказались выполненными все предшествующие ему условия. Эта операция называется отсечением.
Цифрой 5 обозначены известные факты о месте рождения студентов.
Цифрой 6 описаны представления о том, кто из студентов может быть родом из Пензы. Это не могут быть Борис или Виктор, поскольку мы знаем, что они родились в других городах, и должен быть студент, велосипед которого сделан на родине Леонида.
Состоящее из четырех частей правило 7 описывает общие представления о родине каждого из студентов. Во-первых, может быть известен такой факт и тогда другие варианты рассматривать нет необходимости. Вторая часть правила описывает, кто может быть родом из Пензы. Третья часть правила описывает возможное место рождения Леонида. И, наконец, четвертая часть правила описывает, из какого города, кроме Пензы, могут быть студенты, кроме Леонида. Загрузив эту программу, можно получить искомое решение.
27
Одной из часто встречающихся практических задач является задача составления расписаний. Рассмотрим пример подобной задачи (взятый из журнала “Наука и жизнь”):
«Пять студентов должны посещать лекции всю неделю, но по определенным ими установленным правилам, а именно:
1.Если пришли Андрей и Дмитрий, то Бориса быть не должно, но если Дмитрий не пришел, то Борис должен быть, а Виктор быть не должен.
2.Если Виктор пришел, то Андрея быть не должно и наоборот.
3.Если Дмитрий пришел, то Григория быть не должно.
4.Если Бориса нет, то Дмитрий должен быть, но если нет также и Виктора, а если Виктор есть, Дмитрия быть не должно, но должен быть Григорий.
5.Каждый день студенты должны приходить в разных сочетаниях. Какие это сочетания?»
Для решения этой проблемы может быть предложена программа:
Программа 19
DOMAINS s=symbol
PREDICATES
st_A(s) st_D(s) st_B(s) st_V(s) st_G(s) ogr1(s,s,s,s,s) ogr2(s,s,s,s,s) spisok(s,s,s,s,s)
norm1(s,s,s,s,s) norm2(s,s,s,s,s) norm3(s,s,s,s,s) norm4(s,s,s,s,s)
CLAUSES st_A(A):-A=andre; A=net.
st_D(D):-D=dmitri; D=net. st_B(B):-B=boris; B=net. st_V(V):-V=victor; V=net. st_G(G):-G=grig; G=net.
ogr1(andre,_,_,net,_). ogr1(net,_,_,victor,_). ogr2(_,dmitri,_,_,net). ogr2(_,net,_,_,_).
norm1(andre,dmitri,net,_,_). norm2(andre,net,boris,net,_).
28
norm3(_,dmitri,net,net,_). norm4(_,net,net,victor,grig).
spisok(A,D,B,V,G):-st_A(A),st_D(D),st_B(B),st_V(V),st_G(G), norm1(A,D,B,V,G),ogr1(A,D,B,V,G),ogr2(A,D,B,V,G);
st_A(A),st_D(D),st_B(B),st_V(V),st_G(G), norm2(A,D,B,V,G),ogr1(A,D,B,V,G),ogr2(A,D,B,V,G);
st_A(A),st_D(D),st_B(B),st_V(V),st_G(G), norm3(A,D,B,V,G),ogr1(A,D,B,V,G),ogr2(A,D,B,V,G);
st_A(A),st_D(D),st_B(B),st_V(V),st_G(G), norm4(A,D,B,V,G),ogr1(A,D,B,V,G),ogr2(A,D,B,V,G).
st_A(A),st_D(D),st_B(B),st_V(V),st_G(G), not(norm1(A,D,B,V,G)),not(norm2(A,D,B,V,G)), not(norm3(A,D,B,V,G)),not(norm4(A,D,B,V,G)), ogr1(A,D,B,V,G),ogr2(A,D,B,V,G).
Возможно, может быть сформулировано более изящное программное решение, чем приведенное выше. При его поиске читатель может убедиться, что в подобных случаях очень большое значение имеет выбор предикатов и правил, которые могут определяться неединственным образом. При неудачном выборе правил можно получить заведомо ложные решения или исчерпать ресурсы компьютера при вложенном обращении одного правила к другому.
9. БАЗЫ ДАННЫХ И ЗНАНИЙ НА ПРОЛОГЕ
Факты, описанные в разделе clauses, можно рассматривать, как статическую базу данных (БД). Эти факты являются частью кода программы и не могут быть оперативно изменены. Для создания динамической базы данных в ПРОЛОГе предусмотрен специальный раздел database.
Предикаты в этом разделе могут иметь такую же форму представления, что и в статической части ПРОЛОГ-программы, но должны иметь другое имя.
Рассмотрим простой пример.
Программа 20
DOMAINS
name = symbol rost, ves = integer
29
DATABASE
dplayer(name, rost, ves) PREDICATES
player(name, rost, ves) CLAUSES
player(“Михайлов”, 180, 87) player(“Петров”, 187, 93) player(“Харламов”, 177, 80)
Допустим, что необходимо после запуска программы переместить данные из статической БД в динамическую. Для этого можно описать следующее правило:
assert_database:-player(N, R, V), assertz(dplayer(N, R, V)),fail.
В этом правиле использован встроенный предикат assertz, который помещает утверждение в базу данных после всех утверждений, которые там уже имеются. Есть также встроенные предикаты для удаления утверждений (retract), считывания с диска (consult), записи БД на диск (save) и сбора данных из БД в список (findall).
Главное достоинство БД на ПРОЛОГе, как и любой другой БД, заключается в возможности быстрого выборочного доступа к информации. Например, в приведенном выше примере это может быть запрос:
GOAL: player(N, R, V),R>180
Если сравнивать основные понятия ПРОЛОГа и реляционных БД, то получится следующая табл.4.
|
Таблица 4 |
|
|
ПРОЛОГ |
Реляционные БД |
|
|
Предикат |
Отношение (таблица) |
|
|
Объект |
Атрибут отношения |
|
|
Отдельное утверждение |
Элемент отношения (запись) |
|
|
Количество утверждений |
Мощность отношения |
|
|
Таким образом, можно сказать, что любая ПРОЛОГ-программа может быть названа базой данных.
Каково же главное отличие ПРОЛОГ-программ от реляционных БД? В БД можно только извлекать существующие сведения или изменять данные по заданному закону. В ПРОЛОГ-программе за счет использо-
30