Algoritmo di pesata rapida con algoritmo di compressione del percorso

Question

Esiste un algoritmo "Unione rapida con compressione".

il codice:

public class WeightedQU 
{ 
    private int[] id; 
    private int[] iz; 

    public WeightedQU(int N) 
    { 
     id = new int[N]; 
     iz = new int[N]; 
     for(int i = 0; i < id.length; i++) 
     { 
      iz[i] = i; 
      id[i] = i; 
     } 
    } 

    public int root(int i) 
    { 
     while(i != id[i]) 
     { 
      id[i] = id[id[i]]; // this line represents "path compression" 
      i = id[i]; 
     } 
     return i; 
    } 

    public boolean connected(int p, int q) 
    { 
     return root(p) == root(q); 
    } 

    public void union(int p, int q) // here iz[] is used to "weighting" 
    { 
     int i = root(p); 
     int j = root(q); 
     if(iz[i] < iz[j]) 
     { 
      id[i] = j; 
      iz[j] += iz[i]; 
     } 
     else 
     { 
      id[j] = i; 
      iz[i] += iz[j]; 
     } 
    } 
} 

Domande:

1. Come funziona il lavoro di compressione percorso? id[i] = id[id[i]] significa che raggiungiamo solo il secondo antenato del nostro nodo, non la radice.

2. iz[] contiene numeri interi da 0 a N-1. In che modo iz[] ci aiuta a conoscere il numero di elementi nel set?

Qualcuno può chiarire questo per me?

Answer 1

prima capire che id è un foresta. id[i] è l'elemento principale di i. Se id[i] == i significa che i è una radice.

Per qualche radice i (dove id[i] == i) allora iz[i] è il numero di elementi nella albero radice in i.

public int root(int i) 
{ 
    while(i != id[i]) 
    { 
     id[i] = id[id[i]]; // this line represents "path compression" 
     i = id[i]; 
    } 
    return i; 
} 

Come funziona il lavoro di compressione percorso? id[i] = id[id[i]] significa che raggiungiamo solo il secondo antenato del nostro nodo, non la radice.

Mentre stiamo salendo sull'albero per trovare la radice, spostiamo i nodi dai loro genitori ai loro nonni. Questo parzialmente appiattisce l'albero. Si noti che questa operazione non cambia in quale albero il nodo è membro, questo è tutto ciò a cui siamo interessati. Questa è la tecnica di compressione del percorso.

(hai notato il diritto ciclo? while(i == id[i]) termina una volta i è un nodo radice)

iz[] contiene numeri interi da 0 a N-1. In che modo iz[] ci aiuta a conoscere il numero di elementi nel set?

C'è un errore di trascrizione in codice:

Questa è la versione corretta:

for(int i = 0; i < id.length; i++) 
{ 
    iz[i] = 1; // RIGHT 
    id[i] = i; 
} 

iz[i] è il numero di elementi per un albero radicato a i (o se i non è una radice, quindi iz[i] non è definito). Quindi dovrebbe essere inizializzato a 1, non i. Inizialmente ogni elemento è un albero "singleton" separato di dimensione 1.

Answer 2

Domanda 1. Non è corretto affermare che la riga id [i] = id [id [i]]; raggiunge solo il secondo antenato della radice. Ti renderai conto che while while while (i! = id [i]) si arresta solo quando il nodo i punta alla radice cioè quando io == id [i] .Per questa volta noi deve aver indirizzato il nodo alla radice usando la riga id [i] = id [id [i]]; dove l'id interno [i] è la radice.

Domanda 2.

Vi sbagliate inizializzare iz [i] = i; in realtà dovrebbe essere iz [i] = 1; il significato, ogni dimensione del nodo è inizializzata di 1 all'inizio poiché sono di dimensione 1. Nella funzione unione ti rendi conto che abbiamo le linee iz [j] + = iz [i]; e iz [i] + = iz [j]; che aggiorna la dimensione del nodo radice in modo che sia la somma delle dimensioni dei due componenti unite insieme. Questo aggiorna in modo efficiente le dimensioni dei nodi.

Answer 3

id [i] = id [id [i]]; // questa riga rappresenta "compressione del percorso"

Il codice precedente è "Più semplice variante one-pass" come menzionato nella diapositiva di Union Find (Algorithms, Parte I di Kevin Wayne e Robert Sedgewick). Quindi la tua ipotesi per la domanda 1 è corretta. Ogni nodo esaminato punta al nonno.

per rendere ogni punti nodali esaminati alla radice avremo bisogno di implementazione a due passaggi:

/** 
* Returns the component identifier for the component containing site <tt>p</tt>. 
* @param p the integer representing one site 
* @return the component identifier for the component containing site <tt>p</tt> 
* @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N 
*/ 
public int find(int p) { 
    int root = p; 
    while (root != id[root]) 
     root = id[root]; 
    while (p != root) { 
     int newp = id[p]; 
     id[p] = root; 
     p = newp; 
    } 
    return root; 
} 

Riferimento: http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html

Answer 4

Una cosa da notare qui:

Mentre trovare la radice quando stiamo creando id[i]=id[id[i]] ie; rendendo i sotto il suo nonno

-allora dimensioni id[i] diminuirà in base alle dimensioni della i i, e; iz[id[i]]-=iz[i]

Ora questo codice è perfettamente corretto.

Non sono sicuro di questo, ma intuitivamente mi sento, La sua assenza non causa problemi perché stiamo sempre confrontando le dimensioni delle radici.