Risoluzione delle relazioni di equivalenza

Question

Risoluzione delle relazioni di equivalenza

#1 da (2 voti)

2

Sto scrivendo una funzione per etichettare il componente connesso in un'immagine (So che ci sono diverse librerie al di fuori, volevo solo giocare con l'algoritmo).

Per fare questo etichetto le regioni collegate con etichette diverse e creo una tabella di equivalenza che contiene informazioni sulle etichette appartenenti allo stesso componente connesso.

Ad esempio se la mia tabella di equivalenza (vettore del vettore) assomiglia a qualcosa di simile:

1:    1,3
2:    2,3
3:    1,2,3
4:    4

Significa che nell'immagine ci sono 2 diverse regioni, una fatta di elementi che sono etichettati come 1,2,3 e altri fatti di elementi con l'etichetta 4.

Che cosa è un modo semplice ed efficace per risolvere le equivalenze e finire con qualcosa che assomiglia a:

1: 1,2,3
2: 4

che posso usare per "unire" le diverse regioni connesse appartenenti allo stesso componente connesso?

Grazie mille per l'aiuto!

c++ algorithms

posta lucacerone 20.09.2012 - 21:29

fonte

1 risposta

Leggi altre domande sui tag c++ algorithms

Dove posizionare il codice R per il flusso di lavoro R + Sweave + LaTeX qual è la differenza nella sezione e nel sottoreport, dove utilizzare più sezioni?

score 2 · Accepted Answer

Probabilmente vorrai una struttura dati set disgiunti . Questo produce prestazioni ammortizzate quasi costanti per operazione e può essere reso molto efficiente per il tipo di attività che descrivi.

In breve, ogni classe di equivalenza è memorizzata come "albero invertito": ogni nodo ha un link parent , ma nessun collegamento figlio. Una "query" segue i collegamenti parent finché non raggiungono la radice (che può essere contrassegnata dall'avere se stessa come genitore). Nota che ogni nodo nello stesso albero produrrà la stessa radice, che è "l'esempio" che rappresenta quella classe di equivalenza.

I nodi tipicamente iniziano come una propria classe di equivalenza (cioè, sono inizializzati come una struttura composta solo dalla radice). Per unire due classi di equivalenza, trova la radice di ciascuna e creane una l'altra dell'altra.

Aggiungendo due semplici ottimizzazioni (sempre "comprimi" i percorsi di query per puntare direttamente alla radice e scegli sempre la radice dell'albero più profondo come unione padre), guadagni prestazioni peggiori "quasi-costanti" per le tue operazioni .