В этом топике пойдет речь о задаче Прима-Краскала (“жадный алгоритм”) и ее решении на языке «Пролог».
Начали!
Задача: Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной.
Уточнение задачи. В задаче речь идет о телефонной связи, т.е. подразумевается транзитивность связи: если i-и город связан с j-ым, а j-ый с k-ым. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов.
В терминах теории графов задача Прима-Краскала выглядит следующим образом:
Дан граф с n вершинами; заданы длины ребер. Найти остовное дерево минимальной длины.
Как известно, дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы ни возникали циклы).
Краткое описание алгоритма Прима-Краскала: В цикле n-1 раз делай: ”выбрать самое короткое еще не выбранное ребро при условии, что они не образуют цикл с уже выбранными”.
Выбранные таким образом ребра и образуют искомое дерево.
Для решения задачи будет создан граф, представленный как список ребер и вершин.
Алгоритм поиска остовного дерева можно поделить на следующие этапы:
• отсортировать список ребер в порядке возрастания их длины;
• применить “жадный” алгоритм и получить список ребер;
• проверить является ли полученный список ребер остовным деревом.
Жадный алгоритм работает следующим образом: необходимо выбрать еще не выбранное ребро минимальной длины (ребро не должно образовывать цикл с другими выбранным ребрами).
Теперь реализация полученного алгоритма на SWI-Prolog:
В программе были реализованы следующие предикаты:
• 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 – результат.
Результаты работы программы:
Начали!
Задача: Дана плоская страна и в ней 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 – результат.
Результаты работы программы: