Si vuole costruire una rete stradale che colleghi cinque città (A-E), minimizzando i costi complessivi di realizzazione. I costi per la costruzione di una strada tra due città sono sintetizzati nella seguente tabella (dove +∞ significa che la strada è irrealizzabile):
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 3 | 5 | 11 | 9 |
| B | 3 | 0 | 3 | 9 | 8 |
| C | 5 | 3 | 0 | +∞ | 10 |
| D | 11 | 9 | +∞ | 0 | 7 |
| E | 9 | 8 | 10 | 7 | 0 |
Si formuli il problema dato in termini di un problema di ottimizzazione su grafi, e si descriva un algoritmo per la sua soluzione discutendone correttezza e complessità. Infine, si simuli accuratamente l’algoritmo presentato per determinare una soluzione del problema.
Svolgimento
Il grafo è non orientato, poiché la matrice di adiacenza è simmetrica.
Si può utilizzare l'algoritmo di Kruskal, che è corretto, poiché è composto da
- un'inizializzazione con tempo O(n) che termina sicuramente, in quanto è un ciclo
- un ordinamento degli archi con costo O(m log(m)), che termina sicuramente, utilizzando un algoritmo di ordinamento che termina (es. mergesort o quicksort)
- un ciclo per ciascun arco O(m) per ciascuno dei quali è necessario verificare se i due vertici appartengono allo stesso insieme O(log(n)) ⇒ O(m log(n)), operazione che termina sicuramente
- l'aggiunta dell'arco e l'unione (eventuale) dei due sottoinsiemi, con costo O(log(m)), che termina sicuramente.
e che ha un costo complessivo di esecuzione O(m log(m))
- gli archi ordinati sono AB(3), BC(3), AC(5), DE(7), BE(8), AE(9), BD(9), CE(10), AD(11), CD(+∞)
- AB costituisce il primo arco aggiunto all'albero U, e A, B i primi due vertici (nota: sarebbe stato indifferente iniziare con BC, con un esito diverso ma costi uguali). Ora U = {A, B, (AB)}
- BC è aggiunto, in quanto C non appartiene a U. Ora U = {A, B, C, (AB), (BC)}
- AC non è aggiunto, in quanto sia A sia C appartengono a U
- DE è aggiunto - pur non essendo ancora connesso. Ora U = {A, B, C, D, E, (AB), (BC), (DE)}
- BE è aggiunto, perché B ed E appartengono a due set diversi. Ora U = {A, B, C, D, E, (AB), (BC), (DE), (BE)}
- Per brevità riportiamo in un solo passaggio AE, BD, CE, AD, CD, che non sono inclusi.
Le strade da realizzare sono quelle evidenziate in neretto:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 3 | 5 | 11 | 9 |
| B | 3 | 0 | 3 | 9 | 8 |
| C | 5 | 3 | 0 | +∞ | 10 |
| D | 11 | 9 | +∞ | 0 | 7 |
| E | 9 | 8 | 10 | 7 | 0 |