Шекет В.І. Конспект лекцій по логічному програмуванню
Подождите немного. Документ загружается.
Предикат zapytannia задає питання і організовує
обробку відповіді. Якщо відповідь починається з букви Y, тоді
система приймає відповідь Yes, а, якщо відповідь починається з
N, тоді в якості відповіді приймається - No.
zapytannia(X,Y,yes):-!,write(X,"it",Y,'\n'),
readln(Reply),
frontchar(Reply, 'y',_),
pamjataty(X,Y,yes).
zapytannia(X,Y,no):- !,write(X,"it",Y,'\n'),
readln(Reply),
frontchar(Reply, 'n',_),
remember(X,Y,no).
pamjataty(X,Y,yes):-assertr(xpositive(X,Y)).
pamjataty(X,Y,no) :-assertr(xnegative(X,Y)).
При роботі з базами даних потрібно також пам`ятати
наступне. Під час поповнення бази новими фактами, старі
факти повинні зсуватись, щоб не затертись новими. Цю
функцію в програмі виконує вмонтований предикат
retractall, який використовується при визначенні предикату
zrozymilifacty.
zrozymili_facty:-
write("\n\n Please press the space bar
to exit\n"),
retractall(_, dbasedom),
readchar(_).
Якщо ви попередньо наберете програму і наповните базу,
тоді для запуску програми ви можете використати предикат run.
run:-
tvaryna_je(X),!,
write("\nYour animal may be a(an)", X),
113
nl,nl, clear_facts.
run:- write("\nUnable to determine what"),
write("your animal is.\n\n"),
zrozymili_facty.
9.2 Макетування: задача маршрутизації
Ця програма ілюструє особливості Прологу, які роблять
його корисним при вирішенні задач макетування. Припустимо ,
ми хочемо створити систему, яка б допомогала вибрати маршрут
при поїздці із одного міста в інше.
Початкову програму будемо використовувати для
подальшого аналізу вирішення поставленої задачі.
Нас будуть цікавити питання типу:
* Чи існує пряма дорога з одного міста в інше?
* Які з міст знаходяться на віддалі меншій 10 км від
конкретного міста?
Нехай ми будемо реалізовувати карту прототипу,
зображену на мал.9.2.
IvanoFrankivsk
O-----------------------
Kolomyja
O--------- O Kalush --------O Rogatyn
Рисунок 9.2- Карта прототипу
Наступна програма є класичним прикладом
використання бектрекінгу і рекурсії для вирішення задачі
планування маршруту.
domains
114
misto=symbol
Vidstan=integer
predicates
shljah(misto,misto,vidstan)
marshrut(misto,misto,vidstan)
clauses
shljah(Rogatyn,Kalush,40).
shljah(Kolomyja,Rogatyn,150).
shljah(Kalysh,Kolomyja,100).
shljah(Kalush,Ivano_Frankivck,30).
shljah(Kolomyja,Ivano_Frankivck,40).
marshrut(Misto1,Misto2,Vidstan) :-
shljah(Misto1,Misto2,Vidstan).
marshrut(Misto1,Misto2,Vidstan) :-
shljah(Misto1,X,Vids1),
marsrut(X,Misto2,Vids2),
Vidstan=Vids1+Vids2,!.
Кожна фраза для предикату shljah є фактом, який описує
дорогу із одного міста в інше, довжина якої визначається в
кілометрах. Фрази marsrut характеризують те, чи можна
створити маршрут із одного міста в інше через декілька
проміжних пунктів. Третій параметр визначає пройдену відстань
між містами.
Предикат marsrut визначається рекурсивно; маршрут
може просто складатись із одного проміжку дороги ( перша
фраза). В цьому випадку віддаль буде довжиною дороги. Ми
також можемо сконструювати маршрут із Misto1 в
Misto2, використовуючи проміжний пункт Х. Загальна віддаль
буде тоді сумою віддалей між Misto1 і Х а також із Х в Misto
2, що й показано в другій фразі route.
При подальшому аналізі задачі на складнішій структурі
міст приходимо до необхідності вирішення наступних проблем:
115
1.Пролог система не повинна вибирати маршрут, який
приводить до відвідин одного міста двічі.
2.Попередження переміщень по колу, яке дасть
впевненість в тому, що програма не прийде до нескінченного
циклу. Ці проблеми досить просто можна вирішити, якщо ми в
програмі створимо і будемо заповнювати, а потім аналізувати
список міст, які вже були відвідані при прокладенні маршруту.
Приклад реалізації такого списку приводиться далі.
9.3 Пригоди в дивних печерах
Розв'яжемо модифіковану задачу пошуку шляху в
лабіринті. Нехай ми маємо печеру з скарбами. Печера є
лабіринтом галлерей, які з'єднують кімнати з монстрами та
грабіжниками. В одній з кімнат знаходяться скарби. Будемо
вважати, що вам треба зайти в печеру, забрати скарби і вийти
живими з лабіринту. Розглянемо таку карту печери:
entry m
O O O
O O
m s f exit
O O O O
hell
пекло
ernaind
русалка
вхід
fontain robbers
onster ood goldtreasure
фонтан
грабіжник
монстр
їдальня
золотий вихід
Рисунок 9.2-Лабіринт галлерей
domains
kimnata=symbol
spysokkimnata=kimnata *
predicates
prochid(kimnata,kimnata) /* існує коридор */
116
/* між двома кімнатами */
susidjarkimnata(kimnata,kimnata) /* Визначення
*/
/* сусідських */
/* кімнат */
unyknuty(spysokkimnat)
ity(kimnata,kimnata)
marshrut(kimnata,kimnata,spysokkimnat)/*Тут
spysok kimnat*/
/* містить кімнати */
/* відвідані */
vhodzhennja(kimnata,spysokkimnat)= vhodzhennja
clauses
galereja(vhid,monstry).
galereja(vhid,fontan).
galereja(fontan,peklo).
galereja(fontan,jizha).
galereja(vyhid,zolotyj_skarb).
galereja(fontan,mermaid).
galereja(robbers,zolotyj_skarb).
galereja(fontan,grabizhnyki).
galereja(jizha,zolotyj_skarb).
galereja(mermaid,vyhid).
galereja(monstry,zolotyj_skarb).
galereja(zolotyj_skarb,vyhid).
susidjarkimnata(X,Y):- galereja(X, Y).
susidjarkimnata(X,Y):- galereja(Y, X).
unyknuty([monstry,grabizhnyki]).
ity(Here,There):-marshrut(Here,There,[Here]).
ity(_, _).
marshrut(Kimnata,Kimnata,VidvidKimnata):-
117
vhodzhennja(zolotyj_skarb, 6 0
VidvidKimnata),
write(VidvidKimnata),nl.
marshrut(Kimnata,Way_out,VidvidKimnata):-
susidjarkimnata(Kimnata,NastupnaKimnata),
unyknuty(NebezpechnaKimnata),
not(vhodzhennja(NastupnaKimnata,NebezpechnaKimn
ata)),
not(vhodzhennja(NastupnaKimnata,VidvidKimnata))
,
marshrut(NastupnaKimnata,Way_out,[NastupnaKimna
ta | VidvidKimnata]).
vhodzhennja(X,[X|_]).
vhodzhennja(X,[_|H]):-vhodzhennja(X, H).
Кожна печера описана фактом. Предикати ity і
marshrut задають правила. Задавши програмі ціль
ity(vhid,vyhid), отримаємо відповідь. Вона буде містити
список кімнат, які ми повинні пройти, щоб забрати скарби і
повернутись. Як ми і говорили, в попередньому розділі для
усунення вад минулої програми використовується список уже
пройдених кімнат. Ця дія виконується в рекурсивному
предикаті marshrut третім аргументом. Тому, якщо ви
знаходитесь в кімнаті виходу, і цей список містить кімнату
zolotyj_skarb, тоді ви досягли поставленої мети.
Звернемо вашу увагу на наступне. Враховуючи нашу
побудову предикату marshrut, якщо задача може мати і декілька
розв'язків, програма буде завжди видавати тільки один
розв'язок. Для видачі всіх можливих розв'язків нам потрібно
організувати бектрекінг за допомогою предикату fail в
першому правилі визначення marshrut:
118
marshrut(Kimnata,Kimnata,VidvidKimnata):-
vhodzhennja(zolotyj_skarb,VidvidKimnata),
write(VidvidKimnata),nl,fail.
9.4 Моделювання апаратних засобів
Прологівські програми є зручними для моделювання
роботи різних складних систем обробки інформації,
наприклад радіотехнічних систем. Кожна логічна лінія зв'язку
може бути описана відповідним предикатом прологу. Предикат
характеризує відношення між сигналами на вході і виході.
Базові функції основних компонент об'єктів описують за
допомогою таблиць істинності.
Покажемо як це робиться на прикладі моделювання
роботи лінії зв'язку типу взаємовиключного АБО, схема якого
приведена на рисунку 9.3.
Рисунок 9.3- Базова лінія зв'язку XOR
В наступній програмі вона описана предикатом xor.
domains
d = integer
119
predicates
not_(d, d)
and_(d, d, d)
or_(d, d, d)
xor(d, d, d)
clauses
not_(1, 0). not_(0, 1).
and_(0, 0, 0). and_(0, 1, 0).
and_(1, 0, 0). and_(1, 1, 1).
or_(0, 0, 0). or_(0, 1, 1).
or_(1, 0, 1). or_(1, 1, 1).
xor(Input1, Input2, Output) :-
not_(Input1, N1), not_(Input2, N2),
and_(Input1, N2, N3), and_(Input2, N1,
N4),
or_(N3, N4, Output).
Якщо ми задамо ціль :
goal:xor(Input1,Input2,Output)
Проінтерпретуємо отриманий результат як таблицю
істинності, тоді ми можемо перевірити, чи наша програма вірно
моделює потрібну лінію зв'язку.
9.5 Задача про ханойські башні
Розглянемо класичну задачу про ханойські башні. Історія
цієї задачі базується на старовинній легенді про буддійський
монастир у В'єтнамі. Легенда говорить про наступне. В цьому
храмі монахи постійно, з давніх часів, виконують таку роботу.
Вони переміщують по спеціальному алгоритму шістдесят
чотири диски на трьох сердечниках при певних обмеженнях. Як
тільки вони закінчать переміщення дисків з першого
сердечника на третій, наступить кінець світу.
120
Уточнимо постановку задачі. Нехай ми маємо три
спеціальних сердечники, на яких проходить переміщення дисків.
Висота сердечників достатня для того, щоб на ній могли
розміститись всі n дисків. Всі диски різного діаметру, а
внутрішній отвір більший за діаметр сердечників. Спочатку всі
диски розміщені на першому сердечнику в спадному, згідно
зовнішнього діаметра, порядку. Їх потрібно перенести на третій
сердечник, використовуючи другий сердечник, так , щоб вони
розмістились в такому ж порядку, як були на першому
сердечнику. При переміщеннях потрібно дотримуватись такого
обмеження: ніколи диск більшого диаметра не може
знаходитись зверху хоча б над одним диском меншого діаметра.
Для переносу можна запропонувати наступний
рекурсивний алгоритм.
* Один диск можна перенести прямо на потрібний
сердечник.
* N дисків можна перемістить так:
1.Перемістить останній (N-ий) диск прямо на третій
(правий) сердечник;
2.Перемістить N-1 диск на другий (середній) сердечник;
3.Перемістить прямо N-ий диск з третього сердечника на
перший (лівий);
4.Перемістить N-1 диск з другого на третій;
5.Перемістить N-ий диск прямо з першого на третій
сердечник;
Програма Прологу, яка вирішуз задачу про Ханойські
Башні, буде використовувати три предикати:
1. hanoi з одним параметром, який характеризує загальну
кількість дисків.
2. move, який описує переміщення N дисків з одного
сердечника на інший, використовуючи третій сердечник, як
тимчасове місцезнаходження дисків.
3. inform, відображає на екрані дисплею, як проходять
переміщення.
121
domains
loc = right;
middle;
left
predicates
hanoi(integer)
move(integer, loc, loc, loc)
inform(loc, loc)
clauses
hanoi(N) :- move(N, left, middle, right).
move(1, A, _, C) :- inform(A, C), !.
move(N, A, B, C) :- N1=N-1,
move(N1, A, C, B),
inform(A, C),
move(N1, B, A, C).
inform(Loc1, Loc2) :-
write("\nMove a disk from ", Loc1,
"to", Loc2).
Для вирішення задачі з трьома дисками, потрібно задати
ціль
goal: hanoi(3).
9.6 Ділення слів на склади
На прикладі вирішення цієї задачі продемонструємо
можливості Прологу при обробці текстової інформації в
редакторах.
Для вирішення задачі ділення слів на склади, будемо
використовувати простий алгоритм, який базується на
впорядкуванні голосних і приголосних в слові. Наприклад,
розглянемо дві послідовності:
1) приголосна - голосна - приголосна. В цьому випадку,
слово ділится після першої голосної:
ruler ---> ru-ler
122