Алгоритм прима паскаль — Мир ПК

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

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

Задача: Дана плоская страна и в ней 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,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]).

В программе были реализованы следующие предикаты:
• 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 – результат.

Алгоритм Краскала

Алгоритм Краскала — это алгоритм минимального остовного дерева, что принимает граф в качестве входных данных и находит подмножество ребер этого графа, который формирует дерево, включающее в себя каждую вершину, а также имеет минимальную сумму весов среди всех деревьев, которые могут быть сформированы из графа.

Как работает алгоритм Краскала

Он подпадает под класс алгоритмов, называемых «жадными» алгоритмами , которые находят локальный оптимум в надежде найти глобальный оптимум.

Мы начинаем с ребер с наименьшим весом и продолжаем добавлять ребра, пока не достигнем нашей цели.

Шаги для реализации алгоритма Краскала следующие:

1. Сортировать все ребра от малого веса до высокого.
2. Возьмите ребро с наименьшим весом и добавьте его в остовное дерево. Если добавление ребра создало цикл, то отклоните это ребро.
3. Продолжайте добавлять ребра, пока не достигнете всех вершин.

Пример алгоритма Краскала

Алгоритм Краскала. Псевдокод.

Любой минимальный алгоритм остовного дерева вращается вокруг проверки, создает ли ребро цикл или нет.

Наиболее распространенный способ выяснить это — алгоритм Union FInd . Алгоритм Union-Find разделяет вершины на кластеры и позволяет нам проверить, принадлежат ли две вершины одному кластеру или нет, и, следовательно, решить создает ли добавление ребра цикл.

Реализация алгоритма Краскала в C ++

Ниже приведен код для реализации в C ++. Мы используем стандартные библиотеки шаблонов, чтобы сделать нашу работу проще и чище.

Когда мы запускаем программу, мы получаем вывод как:

Алгоритм Краскала vs Прима

Алгоритм Прима является еще одним популярным алгоритмом минимального остовного дерева, который использует другую логику для нахождения MST графа. Вместо того, чтобы начинать с ребра, алгоритм Прима начинается с вершины и продолжает добавлять ребра с наименьшим весом, которых нет в дереве, пока все вершины не будут покрыты.

Рекомендуем хостинг TIMEWEB

Рекомендуемые статьи по этой тематике

Подписчики

Платёжная система

• mafulechka
• 4846
• 1
• 3
• 0

• Vladimir Sergeevich
• #
• 25 июля 2019 г. 12:20
• (ред.)

Я так понимаю, это перевод статьи?

Вот такие фразы выглядят стремно: «Любой минимальный алгоритм остовного дерева»
«популярным алгоритмом минимального остовного дерева»
Возможно, должно быть «алгоритмом построения . «

Первое предложение тоже несогласованное.

Странной кажется идея запихивания графа в класс. Да и все равно можно выстрелить в ногу, вызвав print до вызова kruskal.

Не очевидна связь приведенного кода с описанным алгоритмом. — Что это за массив parent и почему (кстати) он не уничтожается в деструкторе?

Псевдокод не понятный. Что делает функция UNION(u, v) ?
Обе строки 7 и 8 вложены внутрь блока if?

У нормальной реализации алгоритма сложность N*log(N). А у вас для каждого узла графа вызывается функция find_set, которая имеет трудоемкость O(N). И того — O(N^2). Функция find_set при этом вообще особо кривая. Не понятно что она должна вернуть в каком случае.

Ну и еще, вот эта структура выглядит очень плохо:
vector

Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала

Минимальное остовное дерево

Остовным деревом графа называется дерево, которое можно получить из него путём удаления некоторых рёбер. У графа может существовать несколько остовных деревьев, и чаще всех их достаточно много.

На иллюстрации приведено одно из остовных деревьев (рёбра выделены синим цветом) решёткообразного графа.

Для взвешенных графов существует понятие веса остовного дерева, которое определено как сумма весов всех рёбер, входящих в остовное дерево. Из него натурально вытекает понятие минимального остовного дерева — остовного дерева с минимальным возможным весом.

Для нахождения минимального остовного дерева графа существуют два основных алгоритма: алгоритм Прима и алгоритм Крускала. Они оба имеют сложность , поэтому выбор одного из них зависит от ваших личных предпочтений. В этой лекции мы разберём оба.

Алгоритм Прима

Алгоритм Прима в идее и реализации очень похож на алгоритм Дейкстры. Как и в алгоритме Дейкстры, мы поддерживаем уже обработанную часть графа (минимального остовного дерева), и постепенно её расширяем за счёт ближайших вершин.

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

Таким образом, для нахождения минимального остовного дерева начнём с произвольной вершины и будем постепенно добавлять ближайшие к уже имеющимся.

На иллюстрации красным цветом выделены рёбра, уже вошедшие в минимальный остов, а чёрным — текущие кандидаты, из которых выбирается ребро с минимальным весом.

Реализация алгоритма Прима

Будем искать вес минимального остовного дерева. Для нахождения ближайшей вершины воспользуемся очередью с приоритетом (аналогично алгоритму Дейкстры), в которой будем хранить пары (расстояние от остова до вершины, номер вершины).

Алгоритм Крускала

Алгоритм Крускала достаточно прост в своей идее и реализации. Он заключается в сортировке всех рёбер в порядке возрастания длины, и поочерёдному добавлению их в минимальный остов, если они соединяют различные компоненты связности.

Более формально: пусть мы уже нашли некоторые рёбра, входящие в минимальный остов. Утверждается, что среди всех рёбер, соединяющих различные компоненты связности, в минимальный остов будет входить ребро с минимальной длиной.

Для реализации алгоритма Крускала необходимо уметь сортировать рёбра по возрастанию длины (для этого воспользуемся собственным типом данных) и проверять, соединяет ли ребро две различных компоненты связности. Для этого будем просто поддерживать текущие компоненты связности с помощью структуры данных DSU.

Визуализация работы алгоритма Крускала:

Реализация алгоритма Крускала

Используем реализацию DSU со всеми оптимизациями из соответствующей лекции:

Различия в скорости работы

Хотя оба алгоритма работают за , существуют константные различия в скорости их работы. На разреженных графах (количество рёбер примерно равно количеству вершин) быстрее работает алгоритм Крускала, а на насыщенных (количество рёбер примерно равно квадрату количеству вершин) — алгоритм Прима (при использовании матрицы смежности).

На практике чаще используется алгоритм Крускала.

brestprog

Олимпиадное программирование в Бресте и Беларуси

Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала

Минимальное остовное дерево

Остовным деревом графа называется дерево, которое можно получить из него путём удаления некоторых рёбер. У графа может существовать несколько остовных деревьев, и чаще всех их достаточно много.

На иллюстрации приведено одно из остовных деревьев (рёбра выделены синим цветом) решёткообразного графа.

Для взвешенных графов существует понятие веса остовного дерева, которое определено как сумма весов всех рёбер, входящих в остовное дерево. Из него натурально вытекает понятие минимального остовного дерева — остовного дерева с минимальным возможным весом.

Для нахождения минимального остовного дерева графа существуют два основных алгоритма: алгоритм Прима и алгоритм Крускала. Они оба имеют сложность , поэтому выбор одного из них зависит от ваших личных предпочтений. В этой лекции мы разберём оба.

Алгоритм Прима

Алгоритм Прима в идее и реализации очень похож на алгоритм Дейкстры. Как и в алгоритме Дейкстры, мы поддерживаем уже обработанную часть графа (минимального остовного дерева), и постепенно её расширяем за счёт ближайших вершин.

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

Таким образом, для нахождения минимального остовного дерева начнём с произвольной вершины и будем постепенно добавлять ближайшие к уже имеющимся.

На иллюстрации красным цветом выделены рёбра, уже вошедшие в минимальный остов, а чёрным — текущие кандидаты, из которых выбирается ребро с минимальным весом.

Реализация алгоритма Прима

Будем искать вес минимального остовного дерева. Для нахождения ближайшей вершины воспользуемся очередью с приоритетом (аналогично алгоритму Дейкстры), в которой будем хранить пары (расстояние от остова до вершины, номер вершины).

Алгоритм Крускала

Алгоритм Крускала достаточно прост в своей идее и реализации. Он заключается в сортировке всех рёбер в порядке возрастания длины, и поочерёдному добавлению их в минимальный остов, если они соединяют различные компоненты связности.

Более формально: пусть мы уже нашли некоторые рёбра, входящие в минимальный остов. Утверждается, что среди всех рёбер, соединяющих различные компоненты связности, в минимальный остов будет входить ребро с минимальной длиной.

Для реализации алгоритма Крускала необходимо уметь сортировать рёбра по возрастанию длины (для этого воспользуемся собственным типом данных) и проверять, соединяет ли ребро две различных компоненты связности. Для этого будем просто поддерживать текущие компоненты связности с помощью структуры данных DSU.

Визуализация работы алгоритма Крускала:

Реализация алгоритма Крускала

Используем реализацию DSU со всеми оптимизациями из соответствующей лекции:

Различия в скорости работы

Хотя оба алгоритма работают за , существуют константные различия в скорости их работы. На разреженных графах (количество рёбер примерно равно количеству вершин) быстрее работает алгоритм Крускала, а на насыщенных (количество рёбер примерно равно квадрату количеству вершин) — алгоритм Прима (при использовании матрицы смежности).

На практике чаще используется алгоритм Крускала.

brestprog

Олимпиадное программирование в Бресте и Беларуси