Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лабораторная работа - Бинарные деревья. Графы - файл 1.docx


Лабораторная работа - Бинарные деревья. Графы
скачать (155 kb.)

Доступные файлы (1):

1.docx155kb.02.12.2011 10:32скачать


1.docx

Рекурсивно-логическое программирование

ОТЧЕТ


по лабораторной работе №5
Задание.

Запрограммировать на языке Пролог указанные ниже предикаты. Продемонстрировать различные варианты их использования на примерах.

Для каждой из групп предикатов А и Б построить дерево вывода для произвольно выбранного основного вопроса.
А. Предикаты работы с бинарными деревьями

Аргументы Т, Т1 и Т2 обозначают деревья, представляемые в виде термов, записываемых с помощью тернарного функтора tree (левое поддерево, правое поддерево, метка) и константы nil, например: tree (tree (nil, nil, f), tree (tree(nil, nil, p), tree (nil, nil, r), k))

1. tree_depth(Т,N): N – глубина дерева (т.е. количество ребер в самой длинной ветви дерева);

2. sub_tree(Т1,Т2): дерево Т1 является непустым поддеревом дерева Т2;

3. flatten_tree(Т,L): L – список меток всех узлов дерева Т;

4. insert(Т1,N,Т2): Т2 – дерево, полученное путем добавления натурального числа N в упорядоченное дерево Т1 с учётом упорядоченности (упорядоченное бинарное дерево – дерево, в котором для каждого узла все элементы левого поддерева меньше, а все элементы правого поддерева больше значения элемента в этом узле). Натуральные числа представлять в обычном виде (1,2,3,…).
Б. Предикаты для работы с графами

Граф может быть представлен либо явно – в виде одной структуры, либо неявно – набором фактов вида edge(P,R,N), устанавливающих наличие ребра (дуги) между вершинами (узлами) P и R и стоимость N (целое неотрицательное число) этого ребра. При явном способе задания графа он представляется термом, включающим в свой состав список ребер (заданных аналогично с помощью тернарного функтора edge) и, возможно, список вершин графа.

Граф может быть задан неявно фактами edge(a,c,8), edge(a,b,3), edge(c,d,12), edge(b,d,0), edge(e,d,9), а в явной форме – например, термом graph([edge(a,c,8), edge(a,b,3), edge(c,d,12), edge(b,d,0), edge(e,d,9)], [a,b,c,d,e]), где graph – бинарный функтор.

В нижеследующем описании предикатов используется первый (неявный) способ задания графа, Х и Y обозначают вершины графа, а L – список вершин.

5. path(Х,Y,L): L – путь без петель между вершинами Х и Y, т.е. список вершин между этими вершинами;

6. min_path(Х,Y,L): L – путь между вершинами Х и Y, имеющий минимальную стоимость 

(стоимость пути равна сумме стоимостей входящих в него ребер);

7. short_path(Х,Y,L): L – самый короткий путь между вершинами Х и Y (длина пути равна количеству ребер, входящих в него);

8. cyclic: граф является циклическим (т.е. не является деревом);

9. is_connected: граф является связным (т.е. для любых двух его вершин существует связывающий их путь).
Замечания:

  1. В предикатах 5-8 граф предполагается связным и может содержать циклы;

  2. Все вышеописанные предикаты работы с графами для второго способа представления графа должны содержать дополнительный аргумент – сам граф, например: path(G,X,Y,L), где G – структура, представляющая граф.


Выполнение работы.

A. Предикаты работы с бинарными деревьями

tree(void).
tree(E,L,R):-tree(L),tree(R).
%tree(a,tree(b,void,void),tree(c,tree(d,void,void),tree(e,void,void)))

max(X,Y,X):-X>Y.
max(X,Y,Y).

conc([],Xs,Xs).
conc([X|Xs],Ys,[X|Zs]):-conc(Xs,Ys,Zs).

%tree_depth(Т,N): N – глубина дерева
tree_depth(void,0).
tree_depth(tree(E,L,R),D):-tree_depth(L,D1),tree_depth(R,D2),
                           max(D1,D2,D3),D is D3+1.

%sub_tree(Т1,Т2): дерево Т1 является непустым поддеревом дерева Т2
sub_tree(tree(E,void,void),tree(E,_,_)).
sub_tree(tree(E1,L1,void),tree(E1,L2,R2)):-sub_tree(L1,L2).
sub_tree(tree(E1,void,R1),tree(E1,L2,R2)):-sub_tree(R1,R2).
sub_tree(tree(E1,L1,R2),tree(E1,L2,R2)):-sub_tree(L1,L2),sub_tree(R1,R2).
sub_tree(tree(E1,L1,R1),tree(E2,L2,R2)):-E1\==E2,sub_tree(tree(E1,L1,R1),L2);
                                         E1\==E2,sub_tree(tree(E1,L1,R1),R2).



%flatten_tree(Т,L): L – список меток всех узлов дерева Т
flatten_tree(void,[]).
flatten_tree(tree(E,L,R),Xs):-flatten_tree(L,Ls),flatten_tree(R,Rs),
                              conc(Ls,[E|Rs],Xs).

%insert(Т1,N,Т2): Т2 - упорядоченное дерево из Т1 и N 
insert(void,X,tree(X,void,void)).
insert(tree(E,L,R),X,tree(E,L1,R)):-X<E,insert(L,X,L1),!.
insert(tree(E,L,R),X,tree(E,L,R1)):-X>=E,insert(R,X,R1).
Результаты работы программы.
tree_depth(tree(a,void,tree(c,tree(d,void,void),void)),X)
X = 3.
1 Solution
sub_tree(X,tree(a,tree(b,void,void),tree(c,void,void)))
X = tree(a,void,void).
X = tree(a,tree(b,void,void),void).
X = tree(a,void,tree(c,void,void)).
X = tree(a,tree(b,void,void),tree(c,void,void)).
X = tree(b,void,void).
X = tree(c,void,void).

6 Solutions
sub_tree(tree(a,void,tree(c,tree(d,void,void),void)),tree(a,tree(b,void,void),tree(c,tree(d,void,void),tree(e,void,void))))
True
1 Solution
flatten_tree(tree(a,tree(b,void,void),tree(c,tree(d,void,void),tree(e,void, void))),X)
X = [b,a,d,c,e].
1 Solution
insert(tree(5,tree(4,void,void),tree(8,tree(6,void,void),tree(10,void,void))),9,X)
X = tree(5,tree(4,void,void),tree(8,tree(6,void,void),tree(10,tree(9,void, void),void))).
1 Solution




Б. Предикаты для работы с графами
member(X,[X|Xs]).
member(X,[Y|Xs]):- member(X,Xs).

delete(X,[X|Xs],Xs).
delete(Z,[X|Xs],[X|Ys]):-X\==Z,delete(Z,Xs,Ys).

delete_all(X,[],[]).
delete_all(X,[X|Xs],Ys):-delete_all(X,Xs,Ys).
delete_all(Z,[X|Xs],[X|Ys]):-X\==Z,delete_all(Z,Xs,Ys).

no_doubles([X],[X]).
no_doubles([X|Xs],[X|Ys]):-member(X,Xs),delete_all(X,Xs,Zs),no_doubles(Zs,Ys).
no_doubles([X|Xs],[X|Ys]):-not member(X,Xs),no_doubles(Xs,Ys).

length([],0).
length([X|Xs],N):-length(Xs,N1),N is N1.

conc([],Xs,Xs).
conc([X|Xs],Ys,[X|Zs]):-conc(Xs,Ys,Zs).

% неявно заданный граф
edge(a,b,1).
edge(b,c,2).
edge(a,c,3).
edge(a,d,4).
edge(d,e,5).
edge(e,f,6).
edge(f,c,7).
edge(f,d,8).

move(X,Y,Z):-edge(X,Y,Z);edge(Y,X,Z).
node(X):-edge(X,_,_);edge(_,X,_).



%path(Х,Y,L): L – список вершин между вершинами Х и Y
path(E1,E2,Es):-tpath(E1,[E2],Gs),delete(E2,Gs,Es).

tpath(E,[E|Es],Es).
tpath(E1,[E2|Gs],Es):-move(E3,E2,_),not member(E3,Gs),
                      tpath(E1,[E3,E2|Gs],Es). 

%min_path(Х,Y,L): L – путь между вершинами Х и Y c минимальной стоимостью
path_w(E1,E2,Es,C):-tpath_w(E1,[E2],0,Gs,C),delete(E2,Gs,Es).

tpath_w(E,[E|Es],C,Es,C).
tpath_w(E1,[E2|Gs],C1,Es,C):-move(E3,E2,C3),not member(E3,Gs),
                             C2 is C1+C3,tpath_w(E1,[E3,E2|Gs],C2,Es,C).

min_path(E1,E2,MinP):-path_w(E1,E2,MinP,MinC), 
                      not (path_w(E1,E2,_,C),C<MinC).

%short_path(Х,Y,L): L – самый короткий путь между вершинами Х и Y 
path_e(E1,E2,Es,C):-tpath_e(E1,[E2],0,Gs,C),delete(E2,Gs,Es).

tpath_e(E,[E|Es],C,Es,C).
tpath_e(E1,[E2|Gs],C1,Es,C):-move(E3,E2,_),not member(E3,Gs),
                             C2 is C1+1,tpath_e(E1,[E3,E2|Gs],C2,Es,C).

short_path(E1,E2,ShP):-path_e(E1,E2,ShP,MinL), 
                       not (path_e(E1,E2,P,L),L<MinL).

%cyclic: граф является циклическим 
temp_n(E1,E2,Es,CountE):-temp_n1(E1,[E2],0,Es,CountE).
temp_n1(E,[E|Es],C,[E|Es],C).
temp_n1(E1,[E2|Gs],C1,Es,C):-move(E3,E2,_),not member(E3,Gs),
                             C2 is C1+1,temp_n1(E1,[E3,E2|Gs],C2,Es,C). 
max_path(E1,E2,MaxP):-temp_n(E1,E2,MaxP,MaxL),
                      not (temp_n(E1,E2,P,L),L>MaxL).
list_node(Xs):-edge(X,Y,_),max_path(X,Y,Xs),!.

temp_e(E1,E2,Edges):-temp_e1(E1,[E2],Es,Edges).
temp_e1(E,[E|Es],Es,[]).
temp_e1(E1,[E2|Gs],Es,[edge(E3,E2)|Edges]):-move(E3,E2,_),not member(E3,Gs),
                                            temp_e1(E1,[E3,E2|Gs],Es,Edges).



list_edge(Es):-temp_e(E1,E2,Es1),temp_e(E1,E2,Es2),Es1\==Es2,
               conc(Es1,Es2,Es3),no_doubles(Es3,Es).

cyclic:-list_edge(Ls),list_node(Ns),
        length(Ls,Edges),length(Ns,Nodes),
        Edges+1>Nodes.
        
%is_connected: граф является связным
is_connected:-path(X,Y,P),edge(X,Z,_),edge(Z,Y,_),Z\==X,Z\==Y;false.

                      

Результаты работы программы.
path(a,f,P)
P = [d,e].
P = [b,c].
P = [c].
P = [d].
4 Solutions

path_w(a,f,Path,Weight)
PATH = [d,e].
WEIGHT = 15.
PATH = [b,c].
WEIGHT = 10.
PATH = [c].
WEIGHT = 10.
PATH = [d].
WEIGHT = 12.
4 Solutions
min_path(a,f,P)
P = [b,c].
P = [c].
2 Solutions
path_e(a,f,Path,Count_edge)
PATH = [d,e].
COUNT_EDGE = 3.
PATH = [b,c].
COUNT_EDGE = 3.


PATH = [c].
COUNT_EDGE = 2.
PATH = [d].
COUNT_EDGE = 2.
4 Solutions


short_path(a,f,P)
P = [c].
P = [d].
2 Solutions
list_node(Nodes)
NODES = [a,d,e,f,c,b].
1 Solution
cyclic
True
1 Solution


is_connected
True
1 Solution


Деревья вывода.

А.

insert(void,X,tree(X,void,void)).
insert(tree(E,L,R),X,tree(E,L1,R)):-X<E,insert(L,X,L1),!.
insert(tree(E,L,R),X,tree(E,L,R1)):-X>=E,insert(R,X,R1).


Б.

path(E1,E2,Es):-tpath(E1,[E2],Gs),delete(E2,Gs,Es).
tpath(E,[E|Es],Es).
tpath(E1,[E2|Gs],Es):-move(E3,E2,_),not member(E3,Gs),
                      tpath(E1,[E3,E2|Gs],Es). 





Скачать файл (155 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации