data una relazione binaria simmetricaR,
specificata da
un insieme finito di coppie, e una coppia in input,
decidere se la coppia appartiene a
R*,
la chiusura riflessiva e transitiva di R,
ossia se,
nel grafo non orientato che rappresenta R,
esiste un cammino che connette
gli elementi della coppia data
il problema ha molte applicazioni pratiche,
ad es.:
costruzione di reti
(di calcolatori, elettriche, etc.)
problemi di unificazione
(nella deduzione automatica, implementazione di linguaggi dichiarativi, etc.)
il problema proposto in (Sedgewick, 2003, Cap. 1) è un po' diverso:
input: una sequenza di coppie
si vuole un algoritmo che, per ogni coppia
cn,
decida se i suoi elementi sono
connessi da un cammino
nel grafo (non orientato) costruito dalle coppie precedenti
{cm | m<n}:
se lo sono, si passa alla coppia successiva
altrimenti si produce in
output cn
(e si passa alla coppia successiva)
varianti
del problema proposto in (Sedgewick, 2003):
più complessa: se la coppia p-q è connessa,
produrre in output uno dei (o tutti i) modi in cui è connessa
esempio:
4o,
5o,
7o
input del precedente
esempio
in
out
1-0
(1-3-0)
4-2
(2-4)
2-1
(1-3-0-2)
più "semplice" (secondo (Sedgewick, 2003)):
date M connessioni su
N oggetti,
dire se tutte le coppie di oggetti sono connesse
N.B. è più "semplice" l'output,
ma si richiede pur sempre un algoritmo per il problema di decisione
enunciato sopra!
idea per la soluzione:
output = albero di copertura?
tutte le coppie degli N oggetti sono connesse
sse l'output dell'algoritmo per il problema di connettività come posto
in (Sedgewick, 2003) consta di N-1 coppie
#include <iostream.h>
static const int N = 10000;
int main()
{ int i, p, q, id[N];
for (i = 0; i < N; i++) id[i] = i ;
while (cin >> p >> q)
{
if (id[p] == id[q]) continue;
int t = id[p];
for (i = 0; i < N; i++)
if (id[i] == t) id[i] = id[q];
cout << " " << p << " " << q << endl;
}
}
#include <iostream.h>
static const int N = 10000;
int main()
{ int i, j, p, q, id[N], sz[N];
for (i = 0; i < N; i++) { id[i] = i ; sz[i] = 1; }
while (cin >> p >> q)
{
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
if (sz[i] > sz[j])
{ id[j] = i; sz[i] += sz[j]; }
else { id[i] = j; sz[j] += sz[i]; }
cout << " " << p << " " << q << endl;
}
}
ci si può attendere che ulteriori miglioramenti dell'efficienza
si possano ottenere riducendo la lunghezza dei cammini
compressione dei cammini:
si modificano puntatori visitati durante una
find, con varie tecniche:
completa:
ogni nodo visitato viene fatto puntare alla radice
del suo albero, al termine della union
per dimezzamento:
nei cammini visitati, si considerano
due connessioni per volta, e si assegna al puntatore
sottostante il valore di quello soprastante
prestazioni:
quanto sono vantaggiose queste tecniche?
ripagano il loro costo computazionale ?
come possiamo valutarne la convenienza
nel caso medio e
nel caso peggiore ?
