Arbori parțiali de cost minim

În 1926, lui Otakar Borůvka i s-a cerut să planifice cât mai ieftin rețeaua electrică din sudul Moraviei. Întrebarea lui, cum legi toate localitățile folosind cea mai mică lungime totală de linie, este problema arborelui parțial de cost minim, iar ea are unele dintre cele mai simple și mai elegante răspunsuri din toată informatica.

Un graf ale cărui muchii au lungimi, cu muchiile scurte ale unui arbore în creștere evidențiate, o muchie sărită care ar închide un ciclu trasată cu linie întreruptă roșie și dedesubt lista muchiilor rămase de încercat
Un graf ale cărui muchii au lungimi, cu muchiile scurte ale unui arbore în creștere evidențiate, o muchie sărită care ar închide un ciclu trasată cu linie întreruptă roșie și dedesubt lista muchiilor rămase de încercat

Problema

Luați un graf conex ale cărui muchii au lungimi sau costuri. Un arbore parțial este o mulțime de muchii care leagă toate nodurile și nu conține niciun ciclu; cu n noduri are mereu exact n − 1 muchii, pentru că fiecare muchie mai leagă un nod. Dintre toți arborii parțiali, un arbore parțial de cost minim are cea mai mică lungime totală. Un graf poate avea un număr enorm de arbori parțiali, dar nu e nevoie să îi încercați pe toți.

De ce funcționează metoda greedy

Împărțiți nodurile în două grupuri, oricum. Cea mai scurtă muchie dintre grupuri face mereu parte dintr-un arbore parțial de cost minim: dacă un arbore ar folosi în locul ei o muchie mai lungă între grupuri, înlocuirea acesteia cu cea mai scurtă ar lega aceleași noduri cu un cost mai mic. Aceasta este proprietatea tăieturii. Reversul medaliei este proprietatea ciclului: cea mai lungă muchie de pe orice ciclu nu este niciodată necesară. Ambii algoritmi de mai jos doar aplică aceste reguli din nou și din nou.

Un exemplu

Luați muchiile A–B de lungime 1, B–C 2, A–C 3, C–D 4 și B–D 5. Algoritmul lui Kruskal ia A–B, apoi B–C, apoi sare peste A–C, pentru că A și C sunt deja legate și muchia ar închide un ciclu, apoi ia C–D. Arborele are trei muchii pentru patru noduri, deci e gata, cu lungimea totală 7, iar B–D nici nu mai este verificată. Algoritmul lui Prim pornit din A adaugă întâi B prin A–B; muchia B–C (2) a lui B bate A–C (3) ca drum spre C, deci C se alătură prin B–C; muchia C–D (4) a lui C bate B–D (5), deci D se alătură prin C–D. Același arbore, același 7.

Kruskal, Prim și Borůvka

Algoritmul lui Kruskal, publicat de Joseph Kruskal în 1956, sortează muchiile și folosește o structură union-find ca să sară peste muchiile din interiorul unei părți, deci efortul lui crește cu E log E. Algoritmul lui Prim a fost descris prima dată de Vojtěch Jarník în 1930 și redescoperit de Robert Prim în 1957 și de Edsger Dijkstra în 1959; cu un heap binar efortul crește cu E log V, iar cu un simplu tablou cu V², ceea ce e bine pentru grafurile dense. Algoritmul lui Borůvka din 1926 lasă fiecare parte să își ia în același timp cea mai scurtă muchie care iese din ea, ceea ce se potrivește calculatoarelor paralele.

Otakar Borůvka în 1981. În 1926 i s-a cerut să planifice cât mai ieftin rețeaua electrică a Moraviei de sud și a dat primul algoritm pentru un arbore de acoperire minim.
Otakar Borůvka în 1981. În 1926 i s-a cerut să planifice cât mai ieftin rețeaua electrică a Moraviei de sud și a dat primul algoritm pentru un arbore de acoperire minim.

Aplicații

Arborii parțiali de cost minim ajută la proiectarea unor rețele ieftine de cabluri, conducte și drumuri. Grupează datele în clustere: eliminați cele mai lungi muchii ale arborelui, iar părțile rămase sunt clusterele. Oferă un traseu rapid pentru problema comis-voiajorului, cel mult de două ori mai lung decât cel mai bun atunci când distanțele respectă inegalitatea triunghiului. Iar algoritmul lui Kruskal sau Prim pe o grilă cu lungimi aleatorii ale muchiilor este un mod clasic de a genera un labirint.

Explorați

Deschideți aplicația, alegeți Kruskal sau Prim și apăsați Pas. Cu Kruskal, muchiile rămase de încercat sunt listate sub graf de la cea mai scurtă la cea mai lungă; muchiile care ar închide un ciclu sunt trasate cu linie întreruptă roșie. Cu Prim, acolo sunt listate nodurile care așteaptă să se alăture, cu lungimea celei mai bune muchii a lor, trasată cu linie întreruptă. Rulați-i pe amândoi pe același graf și comparați: ordinea diferă, dar lungimea totală este mereu aceeași.

Întrebări frecvente

Câte muchii are un arbore parțial?

Exact cu una mai puțin decât numărul de noduri. Mai puține muchii nu ar putea lega toate nodurile, iar una în plus ar crea mereu un ciclu.

Care este mai rapid, Kruskal sau Prim?

Algoritmul lui Kruskal, care sortează muchiile, este de obicei mai simplu și rapid pe grafuri rare, cu puține muchii. Algoritmul lui Prim cu un heap se descurcă bine pe grafuri dense, iar cu un tablou simplu are nevoie de aproximativ V² pași, indiferent câte muchii există.

Ce este union-find?

O structură de date care ține evidența nodurilor aflate în aceeași parte. Răspunde la întrebarea „sunt aceste două noduri legate?” și unește două părți aproape instantaneu, exact de ce are nevoie algoritmul lui Kruskal pentru fiecare muchie.

Funcționează arborele parțial de cost minim pentru grafuri orientate?

Nu ca atare. Pentru grafuri cu muchii cu sens unic, problema corespunzătoare este arborescența parțială de cost minim, rezolvată de algoritmul Chu–Liu/Edmonds.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Construiți un arbore parțial de cost minim