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

Question

Может ли кто -нибудь дать несколько заявлений о двух алгоритмах, где и какие приложения их можно использовать?

Answer 1

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

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

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

Если вы заинтересованы в полной истории минимальной проблемы с деревьями, ее приложениями и ее алгоритмами, есть действительно отличная бумага доступна здесь Это покрывает все это. Я настоятельно рекомендую прочитать это!

Надеюсь это поможет!

Answer 2

Цитируя Википедию:

Одним из примеров может быть кабельная компания, которая закладывает кабель в новый район. Если он ограничен, чтобы похоронить кабель только по определенным путям, то будет график, представляющий, какие точки связаны этими путями. Некоторые из этих путей могут быть дороже, потому что они длиннее или требуют, чтобы кабель был похоронен глубже; Эти пути будут представлены краями с большими весами. Оскоростное дерево для этого графика было бы подмножеством тех путей, которые не имеют циклов, но все же соединяются с каждым домом. Может быть несколько охваченных деревьев. Минимальное дерево охватывающих будет одно с самой низкой общей стоимостью.

Источник: http://en.wikipedia.org/wiki/minimum_spanning_tree

Answer 3

Сначала вы должны понимать, что алгоритм и алгоритм Prim's и Kruskal полезен для поиска Минимальное охраняющее дерево на графике. Я могу придумать, что одно из правых применений минимального охватывающего дерева - это соединение разных офисов одной компании с наименьшими затратами.

Answer 4

• Топология
• Картография
• Геометрия
• Кластеризация
• Алгоритмы маршрутизации
• Поколение лабиринтов
• Механические / электрические / компьютерные сети
• Изучение молекулярных связей в химии

Answer 5

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