Zastosowania algorytmów Kruskala i Prima

Question

Czy ktokolwiek mógłby podać niektóre zastosowania dwóch algorytmów, gdzie i dla których aplikacji mogą być używane?

Answer 1

Najpierw badano minimalne drzewa opinające pod kątem sposobów układania sieci elektrycznych w sposób minimalizujący całkowity koszt okablowania. W minimalnym drzewie opinającym wszystkie węzły (domy) byłyby podłączone do zasilania za pomocą przewodów w sposób, który zapewnia minimalny koszt i nadmiarowość (przecięcie dowolnego przewodu koniecznie odcina sieć energetyczną na dwie części).

Od tego czasu problem został dobrze przestudiowany i jest często stosowany jako podprogram w bardziej złożonych algorytmach. Christofides algorithm do znalezienia przybliżonych rozwiązań problemu z podróżującym sprzedawcą używa go w kluczowym kroku, podobnie jak w przypadku niektórych algorytmów wyszukiwania drzew Steinera.

Minimalne drzewa opinające zostały również użyte do generate mazes. Zarówno algorytm Kruskala, jak i Prima zostały użyte w ten sposób, często tworząc wysokiej jakości labirynty.

Jeśli jesteś zainteresowany w pełnej historii problemu minimalnego drzewa rozpinającego, jej zastosowań i jego algorytmów, jest naprawdę doskonały papier available here, który obejmuje wszystkie z nich. Zdecydowanie zaleciłbym przeczytanie tego!

Mam nadzieję, że to pomoże!

Answer 2

Cytując Wikipedia:

Przykładem może być firma telewizja kablowa r kabel do nowej dzielnicy. Jeśli ograniczymy zakopywanie kabla tylko wzdłuż określonych ścieżek, wówczas pojawi się wykres przedstawiający, które punkty są połączone tymi ścieżkami. Niektóre z tych ścieżek mogą być droższe, ponieważ są dłuższe lub wymagają głębszego zakopania kabla; ścieżki te będą reprezentowane przez krawędzie o większych ciężarach. Drzewo spinające dla tego wykresu byłoby podzbiorem tych ścieżek, które nie mają cykli, ale nadal łączą się z każdym domem. Może być kilka drzew opinających. Minimalne drzewo opinające będzie jednym z najniższym całkowitym kosztem.

Źródło: http://en.wikipedia.org/wiki/Minimum_spanning_tree

Answer 3

Najpierw trzeba zrozumieć, że zarówno Prim i Algorytm Kruskala są przydatne do znalezienia Minimum spanning Tree w postaci wykresu. Jednym z praktycznych zastosowań minimalnego drzewa opinającego, mogę myśleć o łączeniu różnych biur tej samej firmy przy najniższym koszcie.

Answer 4

• Topologia
• Kartografia
• Geometria
• Klastry
• routingu Algorytmy
• Generation labiryntów
• mechaniczne/elektryczne/Sieci komputerowe
• Badanie wiązań molekularnych w Chemii

Answer 5

Aplikacje algorytmów Kruskala i Prima często pojawiają się w sieciach komputerowych. Na przykład, jeśli masz dużą sieć LAN z wieloma przełącznikami, znalezienie minimalnego drzewa opinającego będzie kluczowe dla zapewnienia, że ​​tylko minimalna liczba pakietów będzie przesyłana przez sieć.