Minimalt udspændende træer
I 1926 blev Otakar Borůvka bedt om at planlægge elnettet i det sydlige Mähren så billigt som muligt. Hans spørgsmål, hvordan man forbinder alle steder med den mindste samlede længde ledning, er problemet om det minimalt udspændende træ, og det har nogle af de enkleste og mest elegante svar i hele datalogien.
Problemet
Tag en sammenhængende graf, hvis kanter har længder eller omkostninger. Et udspændende træ er en mængde kanter, der forbinder alle knuderne og ikke indeholder nogen kreds; med n knuder har det altid præcis n − 1 kanter, fordi hver kant forbinder én knude mere. Blandt alle udspændende træer har et minimalt udspændende træ den mindste samlede længde. En graf kan have et enormt antal udspændende træer, men der er ingen grund til at prøve dem alle.
Hvorfor grådighed virker
Del knuderne i to grupper på en hvilken som helst måde. Den korteste kant, der går mellem grupperne, hører altid til et minimalt udspændende træ: hvis et træ i stedet brugte en længere kant mellem grupperne, ville et bytte til den kortere forbinde de samme knuder billigere. Det er snitegenskaben. Den anden side af sagen er kredsegenskaben: den længste kant i en kreds er aldrig nødvendig. Begge algoritmer nedenfor bruger bare disse regler igen og igen.
Et eksempel
Tag kanterne A–B med længde 1, B–C 2, A–C 3, C–D 4 og B–D 5. Kruskals algoritme tager A–B, så B–C, springer så A–C over, fordi A og C allerede er forbundet, og den ville lukke en kreds, og tager så C–D. Træet har tre kanter til fire knuder, så det er færdigt med samlet længde 7, og B–D bliver slet ikke set på. Prims algoritme fra A tilføjer først B via A–B; B's kant B–C (2) slår A–C (3) som vej til C, så C kommer med via B–C; C's kant C–D (4) slår B–D (5), så D kommer med via C–D. Det samme træ, de samme 7.
Kruskal, Prim og Borůvka
Kruskals algoritme, udgivet af Joseph Kruskal i 1956, sorterer kanterne og bruger en union-find-struktur til at springe kanter inden for ét stykke over, så dens arbejde vokser med E log E. Prims algoritme blev først beskrevet af Vojtěch Jarník i 1930 og genopdaget af Robert Prim i 1957 og Edsger Dijkstra i 1959; med en binær hob vokser dens arbejde med E log V, og med et simpelt array med V², hvilket er godt til tætte grafer. Borůvkas algoritme fra 1926 lader hvert stykke tage sin korteste udgående kant på samme tid, hvilket passer til parallelle computere.
Anvendelser
Minimalt udspændende træer bruges til at designe billige net af kabler, rør og veje. De deler data op i klynger: fjern træets længste kanter, og de stykker, der er tilbage, er klyngerne. De giver en hurtig rute til den handelsrejsendes problem, som højst er dobbelt så lang som den bedste, når afstandene overholder trekantsuligheden. Og Kruskals eller Prims algoritme på et gitter med tilfældige kantlængder er en klassisk måde at lave en labyrint på.
Udforsk det
Åbn appen, vælg Kruskal eller Prim, og tryk på Trin. Med Kruskal står de kanter, der endnu skal prøves, under grafen fra kortest til længst; kanter, der ville lukke en kreds, tegnes stiplet med rødt. Med Prim står de knuder, der venter på at komme med, der sammen med længden af deres bedste kant, som tegnes stiplet. Kør begge på den samme graf, og sammenlign: rækkefølgen er forskellig, men den samlede længde er altid den samme.
Ofte stillede spørgsmål
Hvor mange kanter har et udspændende træ?
Præcis én færre end antallet af knuder. Færre kanter kunne ikke forbinde alle knuder, og én mere ville altid danne en kreds.
Hvad er hurtigst, Kruskal eller Prim?
Kruskals algoritme, som sorterer kanterne, er som regel enklere og hurtig på tynde grafer med få kanter. Prims algoritme med en hob klarer sig godt på tætte grafer, og med et simpelt array skal den bruge omkring V² trin, uanset hvor mange kanter der er.
Hvad er union-find?
En datastruktur, der holder styr på, hvilke knuder der er i samme stykke. Den svarer på »er de to forbundet?« og slår to stykker sammen næsten med det samme, hvilket er præcis, hvad Kruskals algoritme har brug for ved hver kant.
Virker et minimalt udspændende træ for orienterede grafer?
Ikke direkte. For grafer med ensrettede kanter er det tilsvarende problem den minimalt udspændende arborescens, som løses af Chu–Liu/Edmonds-algoritmen.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Byg et minimalt udspændende træ