Alberi ricoprenti minimi
Nel 1926 a Otakar Borůvka fu chiesto di progettare la rete elettrica della Moravia meridionale al minor costo possibile. La sua domanda, come collegare ogni località con la minima lunghezza totale di linea, è il problema dell'albero ricoprente minimo, e ha alcune delle risposte più semplici ed eleganti di tutta l'informatica.
Il problema
Prendi un grafo connesso i cui archi hanno una lunghezza, o un costo. Un albero ricoprente è un insieme di archi che collega tutti i nodi e non contiene cicli; con n nodi ha sempre esattamente n − 1 archi, perché ogni arco collega un nodo in più. Tra tutti gli alberi ricoprenti, un albero ricoprente minimo ha la lunghezza totale più piccola. Un grafo può avere un numero enorme di alberi ricoprenti, ma non serve provarli tutti.
Perché l'approccio greedy funziona
Dividi i nodi in due gruppi come vuoi. L'arco più corto che passa da un gruppo all'altro appartiene sempre a qualche albero ricoprente minimo: se un albero usasse invece un arco più lungo tra i gruppi, scambiarlo con quello più corto collegherebbe gli stessi nodi spendendo meno. Questa è la proprietà del taglio. L'altra faccia della medaglia è la proprietà del ciclo: l'arco più lungo di un ciclo non serve mai. I due algoritmi qui sotto non fanno che applicare queste regole.
Un esempio
Prendi gli archi A–B di lunghezza 1, B–C 2, A–C 3, C–D 4 e B–D 5. L'algoritmo di Kruskal prende A–B, poi B–C, poi salta A–C, perché A e C sono già collegati e chiuderebbe un ciclo, poi prende C–D. L'albero ha tre archi per quattro nodi, quindi è finito, con lunghezza totale 7, e B–D non viene nemmeno esaminato. L'algoritmo di Prim da A aggiunge prima B con A–B; l'arco B–C (2) di B batte A–C (3) come via verso C, quindi C entra con B–C; l'arco C–D (4) di C batte B–D (5), quindi D entra con C–D. Lo stesso albero, lo stesso 7.
Kruskal, Prim e Borůvka
L'algoritmo di Kruskal, pubblicato da Joseph Kruskal nel 1956, ordina gli archi e usa una struttura union-find per saltare gli archi interni a un pezzo, quindi il suo lavoro cresce come E log E. L'algoritmo di Prim fu descritto per la prima volta da Vojtěch Jarník nel 1930 e riscoperto da Robert Prim nel 1957 e da Edsger Dijkstra nel 1959; con un heap binario il suo lavoro cresce come E log V, e con un semplice array come V², il che va bene per i grafi densi. L'algoritmo di Borůvka del 1926 fa prendere a ogni pezzo, nello stesso momento, il suo arco uscente più corto, e questo si presta ai computer paralleli.
Usi
Gli alberi ricoprenti minimi servono a progettare reti economiche di cavi, tubature e strade. Raggruppano i dati in cluster: togli gli archi più lunghi dell'albero, e i pezzi che restano sono i cluster. Danno in fretta un giro per il problema del commesso viaggiatore, lungo al massimo il doppio del migliore quando le distanze rispettano la disuguaglianza triangolare. E l'algoritmo di Kruskal o di Prim su una griglia con lunghezze casuali degli archi è un modo classico per generare un labirinto.
Provalo
Apri l'app, scegli Kruskal o Prim e premi Passo. Con Kruskal, gli archi ancora da provare sono elencati sotto il grafo dal più corto al più lungo; gli archi che chiuderebbero un ciclo sono tratteggiati in rosso. Con Prim, sono elencati i nodi in attesa con la lunghezza del loro arco migliore, che è tratteggiato. Esegui entrambi sullo stesso grafo e confronta: l'ordine è diverso, ma la lunghezza totale è sempre la stessa.
Domande frequenti
Quanti archi ha un albero ricoprente?
Esattamente uno in meno del numero di nodi. Con meno archi non si potrebbero collegare tutti i nodi, e uno in più creerebbe sempre un ciclo.
Qual è più veloce, Kruskal o Prim?
L'algoritmo di Kruskal, che ordina gli archi, di solito è più semplice e veloce sui grafi sparsi, con pochi archi. L'algoritmo di Prim con un heap va bene sui grafi densi, e con un semplice array gli servono circa V² passi, qualunque sia il numero di archi.
Che cos'è union-find?
Una struttura dati che tiene traccia di quali nodi sono nello stesso pezzo. Risponde a «questi due sono collegati?» e unisce due pezzi quasi all'istante, proprio ciò che serve all'algoritmo di Kruskal per ogni arco.
Un albero ricoprente minimo funziona per i grafi orientati?
Non così com'è. Per i grafi con archi a senso unico, il problema corrispondente è l'arborescenza ricoprente minima, risolto dall'algoritmo di Chu–Liu/Edmonds.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Costruisci un albero ricoprente minimo