Algoritmo di Kruskal
Da Wikipedia, l'enciclopedia libera.
In ricerca operativa, l'algoritmo di Kruskal è un algoritmo utilizzato per calcolare gli alberi ricoprenti di peso totale minimo.
Si consideri un grafo non orientato dove V rappresenta il numero di vertici (o nodi) ed E il numero di spigoli (o archi). Ad ogni spigolo è associato un peso (o distanza): lo scopo dell'algoritmo è quello di trovare un albero ricoprente di peso minimo, cioè quello in cui la somma dei pesi sia minima. L'algoritmo può essere applicato solo se si dispone di due o più vertici.
L'algoritmo di Kruskal (1956) si basa sulla seguente semplice idea: ordiniamo gli archi per costi e poi li esaminiamo in questo ordine e li inseriamo man mano nella soluzione che stiamo costruendo, se non formiamo cicli con archi precedentemente selezionati. Notiamo che ad ogni passo, se abbiamo più archi con lo stesso costo, è indifferente quale viene scelto.
Indice |
[modifica] Esempio pratico risolto
Lo scopo di questi tipi di problemi è trovare un percorso minimo che copra tutti i nodi (A; B; C; …) della rete indipendentemente dall'ordine. Bisogna schematizzare il problema come nella figura qui sotto indicando con delle lettere i nodi (ovvero i punti della rete che dobbiamo collegare) e con dei segmenti i possibili collegamenti tra i nodi, ad ognuno dei quali deve essere assegnato un numero che può indicare un costo, una distanza o comunque un valore da minimizzare).
Un esempio pratico potrebbe essere il progetto di una rete locale di computer dove ogni PC deve essere collegato alla rete ma utilizzando il minor numero possibile di cavi per il collegamento.
Impostiamo quindi un grafico in cui indichiamo con le lettere maiuscole dell'alfabeto i computer (nodi) e con dei segmenti (che si chiamano archi) a cui è associata una certa distanza, ovvero la lunghezza di cavo necessaria per collegarli.
In questo caso si sta considerando una rete composta da quattro nodi (A; B; C; D) e 6 archi che rappresentano i possibili collegamenti. Prima di proseguire vanno precisate due cose: L'arco AD e l'arco BC non si toccano e, in generale, non è necessario che ogni nodo sia collegato a tutti gli altri.
Per trovare il minimo albero coprente si procede elencando tutti gli archi in ordine crescente di costo (in questo caso distanza). Si ottiene quindi il seguente elenco:
- AB 1
- BC 2
- AC 3
- BD 3
- CD 4
- AD 5
Nel caso ci fossero due archi (in questo caso BD e AC) con uno stesso costo si possono indicare in un ordine a piacere lasciando inalterato il risultato. Convenzionalmente si usa disporli in ordine alfabetico.
Ora, per trovare il minimo albero coprente dobbiamo considerare nuovamente il grafico iniziale andando ad evidenziare gli archi, procedendo nell'ordine dell'elenco appena descritto, in modo da non creare circoli chiusi. Vediamo in pratica come si procede: Evidenziamo l'arco AB (costo 1) e lo segnaliamo nell'elenco:
 |
Elenco degli archi
|
Procediamo considerando l'arco BC (costo 2) e, analogamente a quanto appena fatto, lo evidenziamo nel grafico e lo segnamo nell'elenco:
 |
Elenco degli archi
|
Il prossimo arco dell'elenco sarebbe AC (costo 3) ma lo saltiamo perché creerebbe un circolo chiuso in quanto collegherebbe insieme il nodo A e il nodo C che sono già collegati attraverso B e lo scopo del problema è creare una rete in cui tutti i nodi sono collegati ma utilizzando il minor cavo possibile.
Si procede dunque con BD (costo 3) colorando l'arco di rosso ed evidenziandolo nell'elenco:
 |
Elenco degli archi
|
Ora tutti i nodi sono collegati alla rete quindi il problema è concluso. Procedendo con l'elenco, infatti, si potrebbe verificare che gli altri archi rimanenti creerebbero solamente circoli chiusi.
Per concludere si può facilmente calcolare il costo totale della rete facendo la somma dei costi degli archi segnati (quelli che sono stati evidenziati durante l'esercizio). Il costo totale della rete è
AB + BC + BD = 1 + 2 + 3 = 6.
Se avessimo espresso i costi (ovvero le distanze) tra i nodi in metri (es. per collegare il nodo A al nodo B serve 1 metro di cavo di rete) avremmo ottenuto che per realizzare la rete (al minor costo riguardante il cavo) servirebbero 6 metri di cavo.
[modifica] L'Algoritmo
L'algoritmo di Kruskal si basa essenzialmente sull'algoritmo generico per la creazione di un MST, di cui sfrutta il corollario collegato al teorema di ricerca degli archi sicuri.
L'idea di base di Kruskal è la seguente:
Gestire una foresta di alberi disgiunti tra loro in modo tale da selezionare solo gli archi, di peso minimo, che collegano tra loro questi alberi. Tutti gli alberi della foresta devono essere aciclici.
Proprietà dell'algoritmo
L'algoritmo gestisce una foresta di alberi, ognuno dei quali durante tutta l'esecuzione rimane acicliclo. La foresta durante tutta l'esecuzione è sottoinsieme di qualche MST del grafo che si sta considerando. Quando inizia l'algoritmo la foresta è formata dai soli vertici del grafo, senza archi definiti.
Formalmente:
Consideriamo G=(V,E) il grafo connesso, non orientato e pesato.
Consideriamo X sottoinsieme degli archi E. Inizialmente X è vuoto. X è sottoinsieme di qualche MST
Consideriamo Gx=(V,X) contenente tutti i vertici di G. Inzialmente il grafo Gx non contiene archi. La foresta quindi
è formata da |V| alberi disgiunti.
Durante l'esecuzione l'algoritmo ricerca un arco sicuro da aggiungere alla foresta. Ricerca, fra tutti gli archi che collegano due alberi qualsiasi nella foresta, un arco (u,v) di peso minimo.
Quindi esiste una invariante di ciclo :
Finché Gx non sarà composta da un solo albero, ogni albero contenuto in Gx sarà aciclico e Gx sarà un sottoinsieme di qualche MST
Implementazione dell'algoritmo
Una possibile implementazione dell'algoritmo di Kruskal potrebbe essere la seguente:
* Creare la foresta di grafi.
* Ordinare tutti gli archi del grafo in ordine crescente.
* Scandire gli archi ordinati, uno per volta, inserendoli se opportuno nella foresta
- L'arco per essere aggiunto alla foresta deve collegare due alberi disgiunti
- L'arco deve essere sicuro
- L'arco non deve generare cicli
L'implementazione che viene descritta utilizza il TDA Partition e il TDA PriorityQueue. Il TDA Partition viene utilizzato per mantenere un insieme di oggetti disgiunti. (insiemi disgiunti) Il TDA PriorityQueue invece viene utilizzato per mantenere la lista degli archi ordinati dal più piccolo al più grande.
Consideriamo G=(V,E) il grafo connesso,non orientato e pesato. Consideriamo X sottoinsieme di E. Quindi Gx conterrà la foresta. Gx=(V,X)
(attenzione: è presente un abuso di notazione dopo i commenti sotto l'istruzione q.add(p....)
Q sarà la PriorityQueue P sarà la Partizione
X = Ø per ogni v vertice di V[G] P.MAKE-SET(v) // all'interno della partizione vengono inseriti i vari alberi disgiunti per ogni (u,v) arco di E[G] Q.ADD(P,(u,v)) // gli archi vengono ordinati dal più piccolo al più grande // Arrivati a questo punto abbiamo la foresta memorizzata nella partizione // e tutti gli archi in ordine crescente nella coda a priorità.
finché la coda Q non è vuota
(u,v) = EXTRACT-MIN(Q)
if P.FIND-SET(u) != FIND-SET(v)
X = X UNION {(u,v)}
P.UNION(u,v)
La partizione viene utilizzata per capire se due vertici fanno parte dello stesso albero, quindi per mantenere valida l'invariante di ciclo.
Analizziamo due casi che potrebbero verificarsi durante l'esecuzione del ciclo finché:
* Se l'arco (u,v) estratto dalla coda Q ha insiemi SET disgiunti vuol dire che è sicuro per X infatti l'arco unirebbe due alberi distinti nella foresta. (u,v) viene quindi aggiunto all'insieme X in modo tale che X mantenga l'invariante di ciclo. I due SET vengono poi uniti insieme in modo da identificare un solo albero.
* Se l'arco (u,v) estratto da Q collega due vertici che fanno già parte dello stesso albero significa che l'arco non è sicuro per X. Infatti se venisse aggiunto a X si verebbe a creare un ciclo in X. L'arco viene quindi scartato.
[modifica] Complessità computazionale dell'algoritmo
Il costo computazionale dell'algoritmo è nel caso peggiore O(mn) dove m è il numero di archi ed n il numero di vertici. È possibile diminuire il costo computazionale dell'algoritmo sino ad ottenere O(m log(n)) solo utilizzando strutture UnionFind.
[modifica] Voci correlate
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
