Логическое программирование. Графы. Деревья

1. Логическое программирование. Графы. Деревья.

Лектор:
доцент каф. АОИ
Салмина Нина
Юрьевна

2. Работа со строками

Предикаты:
Str_len (S, N) – определение
длины строки S
Concat (X, Y, S) объединение
строк X и Y в S
Frontstr (N, S, X, Y) X – первые
N символов строки S, Y –
последние символы
Substring (S, NF, NL, X) X –
подстрока S длиной NL,
начиная с позиции NF
Примеры:
Str_len (asdf, Y)
=> Y=4
Concat (ab, cd, S) => S=abcd
Frontstr (2, abcde, X, Y) =>
X=ab, Y=cde
Substring (abcde, 2, 3, X) =>
X=bcd

3. Тест

Оттранслируйте следующее утверждение в
предикаты на Прологе: «Всякий, кто имеет
ребенка, счастлив» (введите предикаты
счастлив, имеет_ребенка и используйте
предикат родитель(X,Y)).
Оттранслируйте следующее утверждение в
предикаты на Прологе: «Ни один человек не
является четвероногим. Все женщины – люди»
для ответа на вопрос: «Является ли женщина
четвероногой?».

4. Тест

Определен следующий предикат:
repeat (X, Y) :- Y=X+1, Y<10, fail.
repeat (X, X).
Что будет ответом на вопрос
? – repeat (4, Y).
Определен следующий предикат:
repeat (X, Y) :- Y=X-2, Y>0, !, fail.
repeat (X, X).
Что будет ответом на вопрос
? – repeat (4, Y).

5. Представление графов

Список смежностей:
G=[ [a, b, c], [b, d], [c, d, b], …]
База предикатов смежностей:
edge (a, [b, c]).
edge (b, [d]).
…
База предикатов ребер:
edge (a, b).
edge (a, c).
edge (b, d).
…

6. Пример. Поиск пути в лабиринте

Пусть имеется следующий лабиринт:
Он будет представлен в программе так:
p_room(jr,[kr]).
p_room(kr,[jr,rr,qr,cr]).
p_room(cr,[kr,br]).
p_room(br,[cr,ar]).p_room(ar,[br]).
p_room(rr,[kr,qr]).
p_room(qr,[kr,rr,vr,pr,wr]). p_room(wr,[qr]).
p_room(vr,[qr,zr,tr]).
p_room(zr,[vr]).
p_room(tr,[vr,mr]).p_room(mr,[tr,lr,sr,ir]).
p_room(lr,[mr,nr]).p_room(nr,[lr,sr]).
p_room(sr,[mr,nr]).
p_room(pr,[qr,ir]).
p_room(ir,[pr,mr,hr]).
p_room(hr,[ir]).

7. Прохождение лабиринта. Программа.

% Выбор соседней комнаты
next ([A | _ ], A).
next ([ _ | T], A) :- next (T, A).
reverse (X,Y) :- reverse1(X,[ ],Y).
reverse1 ([ ], R, R).
reverse1 ([X| T], S, R) :- reverse1 (T, [X| S], R).
% Формирование пути из Х в Y
path(X,Y,L,P) :-p_room(X,S), next(S,Y), reverse([Y|L],P).
path(X,Y,L,P) :-p_room(X,S), next(S,A), A<>Y,
not (member(A,L)), path(A,Y,[A|L],P).

8. Лабиринт. Вывод всех путей.

% Формирование списка всех путей
all_path(X,Y,L,P):- path(X,Y,[X],Z), not(member(Z,L)), !,
all_path(X,Y,[Z|L],P).
all_path(_,_,X,X).
% ИЛИ Вывод по отдельным строкам всех путей +
% их количество
write_path(X,Y,Z,K):- path(X,Y,[X],L), not(member(L,Z)),
!, write(L), nl, K1=K+1, write_path(X,Y,[L|Z],K1).
write_path(_,_,_,K):-write(K).

9. Результат

goal
write_path (ar, pr, [ ], 0).
["ar","br","cr","kr","rr","qr","pr"]
["ar","br","cr","kr","rr","qr","vr","tr","mr","ir","pr"]
["ar","br","cr","kr","qr","pr"]
["ar","br","cr","kr","qr","vr","tr","mr","ir","pr"]
4
Yes

10. Другой вариант представления лабиринта

room (ar, br).
room (br, cr).
room (cr, kr).
room (kr, jr).
room (kr, qr).
room (kr, rr).
room (rr, qr).
room (qr, wr).
room (qr, vr).
room (qr, pr).
room (vr, zr).
room (vr, tr).
room (tr, mr).
room (mr, lr).
room (lr, nr).
room (nr, sr).
room (sr, mr).
room (mr, ir).
room (pr, ir).
room (ir, hr).
next (X, Y) :- room (X, Y).
next (X, Y) :- room (Y, X).
path1 (X, Y, L, P) :- next (X, Y), reverse ([Y | L], P).
path1 (X, Y, L, P) :- next (X, S), S<>Y, not (member (S, L)),
path1 (S, Y, [S | L], P).

11. Остовное дерево

Пусть G=(N, A) – неориентированный
связный граф.
Остовным деревом S графа G называется
неориентированное дерево вида
S=(N, T), T ∈ A

12. Алгоритм построения остовного дерева

А – множество ребер графа G: ((a b) (b c) (c d)…)
T – искомое остовное дерево
V – множество узлов графа вида: ((a) (b) (с) …)
Алгоритм:
1) Формируется множество V;
2) Последовательно выбираются ребра (v, w) из А.
Проверяется, принадлежат ли узлы v и w разным
подмножествам множества V. Если да, то эти два
подмножества объединяются, объединение
добавляется к множеству V, а исходные два
подмножества удаляются из V. Ребро (v, w)
добавляется к множеству Т.

13. Построение остовного дерева. Программа

% база предикатов ребер
room (ar, br)
…
% построение остовного дерева
ost_tree (T) :- form_graf (V, A),
form_tree (V, A, [ ], T).
goal
ost_tree(T).

14. Построение остовного дерева. Программа

% удаление повторяющихся элементов в списке
del_double ([X| XT], Y) :- member (X, XT), !, del_double (XT, Y).
del_double ([X| XT], [ [X] | Y]) :- !, del_double (XT, Y).
del_double ([ ],[ ]).
% формирование списка ребер
form_edge ([ ], [ ], [ ]).
form_edge ([X| XT], [Y| YT], [[X, Y] | L]) :- form_edge (XT, YT, L).
% формирование графа
form_graf (V, A) :- findall (X, room (X, _), L1),
findall (Y, room (_, Y), L2),
append (L1, L2, L), del_double (L, V),
form_edge (L1, L2, A).

15. Построение остовного дерева. Программа

% выбор списка, которому принадлежит вершина
member_list (X, [L | _], L) :- member (X, L), !.
member_list (X, [_ | T], L) :- member_list (X, T, L).
% обе вершины принадлежат одному списку?
member_both (X, Y, [L | _ ]) :- member (X, L), member (Y, L), !.
member_both (X, Y ,[_ | T]) :- member_both (X, Y, T).
% формирование остовного дерева
form_tree (_, [ ], T, T).
form_tree (V, [ [X, Y] | AT], TO, T) :member_both (X, Y, V), !, form_tree (V, AT, TO, T).
form_tree (V, [ [X, Y] | AT], TO, T) :member_list (X, V, L1), member_list (Y, V, L2),
append (L1, L2, L),
delete (L1, V, V1), delete (L2, V1, V2),
form_tree ([L | V2], AT, [ [X, Y] | TO], T).

16. Остовное дерево для лабиринта

T= [ ["ir","hr"], ["mr","ir"], ["nr","sr"], ["lr","nr"],
["mr","lr"], ["tr","mr"], ["vr","tr"], ["vr","zr"],
["qr","pr"], ["qr","vr"], ["qr","wr"], ["kr","rr"],
["kr","qr"], ["kr",“jr"], ["cr","kr"], ["br","cr"],
["ar","br"] ]
1 Solution

17. Бинарные деревья

Бинарное дерево либо пусто, либо состоит
из левого поддерева, корня и правого
поддерева.
Корень может принимать любые значения.
Левое и правое поддеревья являются
бинарными деревьями.

18. Представление бинарного дерева в Прологе

nil – пустое дерево
tree – трехмерный функтор: tree = tree(tree,integer,tree); nil
Пример:
tree (tree (tree (nil, 4, tree (nil, 7, nil)),
2,
tree (nil, 5, nil)),
1,
tree (nil,
3,
tree (tree (nil, 8, nil), 6, nil)) ).

19. Определение принадлежности элемента бинарному дереву

% искомый элемент – это корень
intree (X, tree ( _, X, _)).
% искомый элемент принадлежит левому
поддереву
intree (X, tree ( L, X, _)) :- intree (X, L).
% искомый элемент принадлежит правому
поддереву
intree (X, tree ( _, X, R)) :- intree (X, R).

20. Прохождение бинарного дерева (посещение каждого узла)

Прямой порядок
–
–
–
Обратный порядок
–
–
–
Корень дерева
Левое поддерево в прямом порядке
Правое поддерево в прямом порядке
Левое поддерево в обратном порядке
Правое поддерево в обратном порядке
Корень
Внутренний порядок
–
–
–
Левое поддерево во внутреннем порядке
Корень
Правое поддерево во внутреннем порядке

21. Пример программ прохождения бинарного дерева (прямой порядок)

go_direct ( tree (L, A, R), G) :go_direct (L, GL),
go_direct (R, GR),
append ([A| GL], GR, G).
go_direct (nil, [ ]).

22. Пример программ прохождения бинарного дерева (обратный порядок)

go_back ( tree (L, A, R), G) :go_back (L, GL),
go_back (R, GR),
append (GR, [A], G1),
append (GL, G1, G).
go_back (nil, [ ]).

23. Пример программ прохождения бинарного дерева (внутренний порядок)

go_in ( tree (L, A, R), G) :go_in (L, GL),
go_in (R, GR),
append (GL, [A | GR], G).
go_in (nil, [ ]).

24. Простая сортировка

insert_sort ([ ],[ ]).
insert_sort ([H | L], S) :- insert_sort (L, S1),
insert (H, S1, S).
insert (X, [A | S1], [A | S2]) :- A<X, !,
insert (X, S1, S2).
insert (X, S, [X | S]).

25. Быстрая сортировка

quik_sort (L, S) :- sort (L, [ ], S).
sort ([X | L], SP, S) :- split (X, L, L1, L2),
sort (L2, SP, PR),
sort (L1, [X | PR], S).
sort ([ ], S, S).
split ( _ , [ ], [ ], [ ]).
split (X, [A | T], [A | L1], L2) :- A<X, !, split (X, T, L1, L2).
split (X, [A | T], L1, [A | L2]) :- split (X, T, L1, L2).