Algoritmo di Edmonds: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Scritto da Daniela Mevi |
Nessun oggetto della modifica |
||
Riga 2:
Questo algoritmo è stato sviluppato in modo indipendente da Chu e Liu nel 1965 e da [[Jack Edmonds]] nel 1967. Edmonds ha fornito una prova della sua correttezza utilizzando procedimenti della [[programmazione lineare]]. Si tratta di una dimostrazione piuttosto macchinosa e complessa.
== Descrizione ==
L'algoritmo accetta in ingresso un grafo orientato e pesato ''G'' = ''(V,A,w,a)'', dove ''V'' è l'insieme dei nodi, ''A'' l'insieme degli archi, ''w: A'' → ''R<sup>+</sup>'' una funzione dall’insieme degli archi all’insieme dei numeri reali e ''a'' il nodo che si richiede sia radice dell'albero. In uscita restituisce l'albero orientato di supporto a costo minimo ''T = (V,A*,w)'', dove ''A*'' è un sottoinsieme di ''A'' formato da ''card(V ) - 1'' archi. Durante l’esecuzione l’algoritmo opera su un grafo intermedio ''H = (V<sup>#</sup>, A<sup>#</sup>,w)'' che viene man mano modificato. Dopo aver eliminato gli archi entranti nella radice l'algoritmo opera in due fasi, dette rispettivamente di contrazione e di espansione: durante la prima fase si contrae il grafo originario ''G = (V,A,w,a)'' per eliminare gli eventuali cicli; durante la seconda fase si espande l’albero ''H = (V<sup>#</sup>, A<sup>#</sup>,w)'' ottenuto come risultato della prima fase per liberare i nodi dei cicli che erano stati contratti. Sia durante la contrazione che durante l’espansione avviene la scelta degli archi presenti nella soluzione finale ''T = (V,A*,w)''.
Consideriamo i passi della contrazione:
;passo 1.:Per ogni nodo del grafo in ingresso ''G = (V,A,w,a)'' si seleziona l'arco entrante di peso inferiore. Dal momento che la radice non ha archi entranti abbiamo ''card(V ) - 1'' archi. Se non ci sono cicli termina la contrazione e si restituisce l’albero ''H = (V<sup>#</sup>, A<sup>#</sup>,w)'' ottenuto.
;passo 2.:Se ci sono cicli se ne considera uno qualsiasi:
:::'''a.''' Ulteriori eventuali archi del grafo di partenza che congiungono i nodi del ciclo sono eliminati dall’insieme degli archi.
:::'''b.''' Tutti gli archi che entrano in uno dei nodi del ciclo vanno rietichettati secondo il seguente criterio: siano ''j'' ed ''i'' rispettivamente un nodo del ciclo e un nodo che non vi appartiene tali che esista l'arco ''(i,j)'' con peso ''w<sub>i,j</sub>''; sia inoltre ''(k,j)'' l'arco del ciclo che termina in ''j'' (avente peso ''w<sub>k,j</sub>''); allora il peso rietichettato associato all'arco ''(i,j)'' sarà:
::::::::::''w<sub>i,j</sub>'' = ''w<sub>i,j</sub> - w<sub>k,j</sub>''
:::cioè dal peso di ogni arco entrante nel ciclo si sottrae il peso dell'arco del ciclo diretto allo stesso nodo in cui entra l'arco che si sta rietichettando.
:::'''c.''' Si fanno collassare i nodi del ciclo in un super-nodo.
:::'''d.''' Tra tutti gli archi rietichettati e paralleli che entrano in un super-nodo si conserva quello di peso inferiore e si eliminano tutti gli altri.
:::'''e.''' Ripetiamo questo procedimento per ogni ciclo.
;passo 3.:Torniamo al passo 1 e applichiamo la contrazione sul grafo ridotto che abbiamo ottenuto. Quando non ci sono più cicli la contrazione termina.
Consideriamo ora i passi dell'espansione che accetta in ingresso l’albero ''H = (V<sup>#</sup>, A<sup>#</sup>,w)'' ottenuto al termine della contrazione:
;passo 1.:Consideriamo un super-nodo e l'arco entrante, l'arco entrante appartiene alla soluzione finale ''T = (V,A*,w)'' e viene etichettato come era in origine.
;passo 2.:Il super-nodo viene espanso nei nodi originali e tra gli archi del ciclo bisogna eliminarne uno; tra i nodi del ciclo uno ha due archi entranti: l'arco appena aggiunto alla soluzione e l'arco del ciclo, quest'ultimo viene eliminato, gli altri archi del ciclo vengono aggiunti alla soluzione.
;passo 3.:Si torna al passo 1 finché abbiamo espanso tutti i super-nodi.
Alla contrazione di ogni ciclo in un supernodo durante la prima fase corrisponde l’espansione del supernodo nel ciclo di partenza durante la seconda fase.
== Esempio 1 ==
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
! Immagine !! Descrizione
|-
|[[Image:]]
|Grafo d’ingresso ''G = (V,A,w,a)''
|-
|[[Image:|200px]]
|Prima contrazione: passo 1
|-
|[[Image:|200px]]
|Prima contrazione: passo 2.a
|-
|[[Image:Kruskal Algorithm 3.svg|200px]]
|Prima contrazione: passo 2.b
|-
|[[Image:|200px]]
|Prima contrazione: passo 2.c
|-
|[[Image:|200px]]
|Seconda contrazione: passo 1
|-
|[[Image:|200px]]
|Seconda contrazione: passo 2.a
|-
|[[Image:|200px]]
|Seconda contrazione: passo 2.b
|-
|[[Image:|200px]]
|Seconda contrazione: passo 2.c
|-
|[[Image:|200px]]
|Seconda contrazione: passo 2.d
Fine fase di contrazione
|-
|[[Image:|200px]]
|Prima espansione: passo 1
|-
|[[Image:|200px]]
|Prima espansione: passo 2
|-
|[[Image:|200px]]
|Seconda espansione: passo 2
Fine
Si ottiene ''T = (V,A*,w)''.
|}
== Esempio 2 ==
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
! Immagine !! Descrizione
|-
|[[Image:]]
|Grafo d’ingresso ''G = (V,A,w,a)''
|-
|[[Image:|200px]]
|Prima contrazione: passo 1
|-
|[[Image:|200px]]
|Prima contrazione: passo 2.a
|-
|[[Image:|200px]]
|Prima contrazione: passo 2.b
|-
|[[Image:|200px]]
|Prima contrazione: passo 2.c
|-
|[[Image:|200px]]
|Prima contrazione: passo 2.d
|-
|[[Image:|200px]]
|Seconda contrazione: passo 1
Gli archi selezionati non formano cicli: abbiamo trovato un albero.
Fine contrazione
|-
|[[Image:|200px]]
|Prima espansione: passo 1
|-
|[[Image:|200px]]
|Prima espansione: passo 2
|-
|[[Image:|200px]]
|Seconda espansione: passo 1
|-
|[[Image:|200px]]
|Seconda espansione: passo 2
|-
|[[Image:|200px]]
|Fine
Si ottiene ''T = (V,A*,w)''.
|}
== Bibliografia ==
| |||