Похожие презентации:
Логическое программирование. Графы. Деревья
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. Результат
goalwrite_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).