Завдання Прима-Краскала на мові Пролог
У цьому топіці йтиметься про завдання Пріма-Краскала (“жадібний алгоритм”) та її рішення мовою «Пролог».
У термінах теорії графів завдання Прима-Краскала виглядає так: Даний граф з n вершинами; задані довжини ребер. Знайти остовне дерево мінімальної довжини. Як відомо, дерево з n вершинами має n-1 ребер. Виявляється, кожне ребро треба вибирати жадібно (аби не виникали цикли).
Короткий опис алгоритму Прима-Краскала: У циклі n-1 раз роби: ”вибрати найкоротше ще не вибране ребро за умови, що вони не утворюють цикл із уже обраними”. Вибрані таким чином ребра і утворюють дерево, що шукається.
Для вирішення завдання буде створено граф, представлений як список ребер та вершин.
Алгоритм пошуку остовного дерева можна розділити на такі етапи:
• відсортувати список ребер у порядку зростання їх довжини; • застосувати “жадібний” алгоритм та отримати список ребер; • перевірити чи є отриманий список ребер кістяковим деревом.
Жадібний алгоритм працює таким чином: необхідно вибрати ще не обране ребро мінімальної довжини (ребро не повинно утворювати цикл з іншими вибраними ребрами).
Тепер реалізація отриманого алгоритму на SWI-Prolog:
%шукає з'єднання мінімальної довжини % %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,Z):- member([X1,X3],Y), not(member(X3,Z)), search(X3,X2,Y,[X3Z]).
search(X1,X2,Y,Z):- member([X3,X1],Y), not(member(X3,Z)), search(X3,X2,Y,[X3Z]).
% реалізує вставку до списку (з сортуванням) % % L1 - список, X - елемент, а L2 - результат ins(X,[],[X]).
Результати роботи програми:
А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише у полі «секретний пароль» запровадити «Хабр»