Pull to refresh

Задача Прима-Краскала на языке Пролог

Reading time 3 min
Views 11K
В этом топике пойдет речь о задаче Прима-Краскала (“жадный алгоритм”) и ее решении на языке «Пролог».

Начали!


Задача: Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной.

Уточнение задачи. В задаче речь идет о телефонной связи, т.е. подразумевается транзитивность связи: если i-и город связан с j-ым, а j-ый с k-ым. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов.

В терминах теории графов задача Прима-Краскала выглядит следующим образом:
Дан граф с n вершинами; заданы длины ребер. Найти остовное дерево минимальной длины.
Как известно, дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы ни возникали циклы).

Краткое описание алгоритма Прима-Краскала: В цикле n-1 раз делай: ”выбрать самое короткое еще не выбранное ребро при условии, что они не образуют цикл с уже выбранными”.
Выбранные таким образом ребра и образуют искомое дерево.

Для решения задачи будет создан граф, представленный как список ребер и вершин.

Алгоритм поиска остовного дерева можно поделить на следующие этапы:

• отсортировать список ребер в порядке возрастания их длины;
• применить “жадный” алгоритм и получить список ребер;
• проверить является ли полученный список ребер остовным деревом.

Жадный алгоритм работает следующим образом: необходимо выбрать еще не выбранное ребро минимальной длины (ребро не должно образовывать цикл с другими выбранным ребрами).

Теперь реализация полученного алгоритма на SWI-Prolog:

%ищет оптимальную конфигурацию
launch:-
write_ln('Города:'), read(X),
write_ln('Расстояния между городами:'), read(Y),
city(X,Y,Z),
write_ln('Оптимальная конфигурация телефонной связи:'),
write(Z).

launch:-
write_ln('Невозможно связать города телефонной связью').

%ищет соединение минимальной длины
%
%Z1 - выбранные ребра,
%Y- список ребер
%Z2 - результат
minimum([],Z,Z):- !.

minimum([[X1,X2,_]|Y],Z1,Z2):-
not(search(X1,X2,Z1,[X1])),!,
minimum(Y,[[X1,X2]|Z1],Z2).

minimum([_|Y],Z1,Z2):- minimum(Y,Z1,Z2). %пропустить ребро

%реализует поиск пути от вершины Х1 к вершине Х2
%алгоритм поиска - поиск в глубин7у.
%где, Y - список ребер, Z - список вершин (которые пройдены).
search(X1,X2,Y,_):- member([X1,X2],Y).

search(X1,X2,Y,_):- member([X2,X1],Y).

search(X1,X2,Y,Z):- member([X1,X3],Y),
not(member(X3,Z)), search(X3,X2,Y,[X3|Z]).

search(X1,X2,Y,Z):- member([X3,X1],Y),
not(member(X3,Z)), search(X3,X2,Y,[X3|Z]).

% реализует вставку в список (с сортировкой)
%
% L1 - список, X - элемент, а L2 - результат
ins(X,[],[X]).

ins([X1,X2,R1],[[Y1,Y2,R2]|L],[[X1,X2,R1]|[[Y1,Y2,R2]|L]]):- R1<R2,!.
ins(X,[Y|L1],[Y|L2]):- ins(X,L1,L2).

%реализует сортировку вставкой
%
%L - список,Y1 - отсортированный список, а Y3 - результат.
sortrast([],Y,Y). sortrast([X|L],Y1,Y3):- ins(X,Y1,Y2), sortrast(L,Y2,Y3).

%соединяет города телефонной связью.
%
%Z - результат X - города, Y - рассояния,
city([X|L],Y,Z):- sortrast(Y,[],Y1), minimum(Y1,[],Z), all(X,L,Z).

%проверяет зону охвата всех
%городов телефонной связью
% x -город, Z - список ребер L - список городов
all(_,[],_).
all(X,[Y|L],Z):- search(X,Y,Z,[X]),!,all(X,L,Z).


В программе были реализованы следующие предикаты:
Launch – используется для вывода информации на экран. Например, список городов и рассеяний между ними.
Sortrast (L1, L2, L3) – сортирует список L1 методом вставок, где L2 –текущий список, L3 – результат.
Сity (X, Y, Z) – соединение городов телефонными линиями, где Х – список городов, Y – список расстояний, Z – результат.
Search (X1, X2, Y, Z) – реализует поиск пути от вершины Х1 к вершине Х2, где Y — список ребер, Z — список вершин (которые пройдены).
all(X,Y,Z) — проверяет зану охвата городов телефонной сетью. Где X – первый город, L – список остальных городов, Z – список телефонных линий.
ins(X,L1,L2) – предикат вставляет элемент X в L1 (отсортированный список ребер). L2 – результат.
minimum (Y, Z1, Z2) – предикат для поиска минимального (по длине) соединения. Где Y – список ребер, Z1 – выбранные ребра, Z2 – результат.

Результаты работы программы:




Tags:
Hubs:
+17
Comments 16
Comments Comments 16

Articles