Visita di un grafo

Posted by On Filed under Algoritmi e strutture dati

Visita in ampiezza

La visita in ampiezza si basa sull'assegnazione a ogni vertice di un colore tra bianco, grigio e nero: il bianco indica che il vertice non è ancora stato visitato, il grigio indica che è stato visitato, ma non sono stati visitati tutti i suoi vertici adiacenti, il nero indica che è stato visitato il vertice e tutti i vertici adiacenti.

La visita in ampiezza sfrutta alcune strutture dati di appoggio:

  • il colore di un vertice è memorizzato in una lista in cui la chiave è il vertice e il valore è il colore: color[v]
  • il predecessore di un vertice è memorizzato in una lista in cui la chiave è il vertice e il valore è il predecessore: π[v]
  • la distanza dal vertice sorgente è memorizzata in una lista in cui la chiave è il vertice e il valore è un numero naturale: d[v]
  • l'elenco di vertici grigi è una coda FIFO: Q

L'algoritmo opera così:

  1. for each v in G inizializzazione dei vertici (tranne il sorgente)
    1. color[v] = white; imposto il colore bianco
    2. π[v] = NIL; il predecessore del vertice è vuoto
    3. d[v] = ∞; la distanza dalla sorgente è infinita
  2. inizializzazione del vertice sorgente
    1. color[s] = grey; imposto il colore grigio
    2. π[s] = NIL; il predecessore della sorgente è NIL (resterà così)
    3. d[s] = 0; la distanza dalla sorgente è zero (resterà così)
  3. Q ↞ s; aggiungo alla FIFO l'elemento sorgente
  4. while Q ≠ ∅, Q ↠ v; finché la coda Q non è vuota estraggo l'elemento in coda
      1. for each u = adj(v); per ogni vertice u adiacente a v
        1. if color[u] == white; se il colore di u è bianco
          1. color[u] = grey; imposta il colore grigio a u
          2. d[u] = d[v] + 1; la distanza di u è uno più di v
          3. π[u]= v; il predecessore di u è v
          4. Q ↞ u; accoda u all'elenco di vertici grigi
      2. color[v] = black; imposta il colore di v a nero

Il tempo di esecuzione di questo algoritmo è O(V+E), poiché ogni vertice e "toccato" una sola volta e ogni arco è "toccato" al massimo una volta.

Siccome se un nodo è già stato visitato non si visitano più i suoi archi, la visita in ampiezza crea, di fatto, un albero.

Visita in profondità

La visita in profondità inizia dal nodo sorgente e lo marca in grigio, poi non lo marca in nero finché non sono neri tutti i suoi successori, e così via ricorsivamente.

L'algoritmo ricorda il modo per uscire sempre da un labirinto (senza isole), che consiste nel procedere con una mano sempre appoggiata al lato (es. mano destra tocca sempre la parete destra).

L'algoritmo è composto da una parte di inizializzazione e lancio della parte ricorsiva e una seconda parte che richiama se stessa nei suoi sotto-vertici:

function DFS

  1. for each v in G inizializzazione dei vertici (tranne il sorgente)
    1. color[v] = white; imposto il colore bianco
    2. π[v] = NIL; il predecessore del vertice è vuoto
    3. time = 0; informazione sull'ordine di esecuzione
  2. for each v in adj(s) richiama la visita su ogni nodo adiacente
    1. if color[v] == white, DFG-visit(v)

function DFS-visit(v)

  1. color[v] = grey;
  2. time = time + 1;
  3. d[v] = time;
  4. for each u in adj(v)
    1. if color[u] == white
      1. π[u] = v;
      2. DFS-visit(u)
  5. color[v] = black;
  6. time = time + 1
  7. f[v] = time

Il tempo di esecuzione di questa funzione è Θ(V+E).

Una proprietà importante di questa visita è che l'ordine dei vertici visitati potrebbe ricalcare uno schema "a parentesi", cioè se apriamo una parentesi ogni volta che visitiamo un vertice e la chiudiamo ogni volta che finsice la visita, otteniamo una struttura a parentesi "ben formato".

Un'altra proprietà è che a seconda del colore che troviamo possiamo classificare gli archi:

  • se l'arco è collegato a un vertice white, abbiamo un arco dell'albero
  • se l'arco è collegato a un vertice grey, abbiamo un arco all'indietro
  • se l'arco(u, v) è collegato a un vertice black, abbiamo un arco in avanti (se d[u] < d[v]) o di attraversamento (se d[u] > d[v])

Topological sort

Utilizzando la DFS è possibile ordinare i vertici di un grafo in base all'ordine in cui sono disposti.

Grafici aciclici

Se una visita in profondità non incontra mai vertici grey, il grafo è aciclico.

 

I Grafi / introduzione

Posted by On Filed under Algoritmi e strutture dati

Grafi

Grafi e rappresentazioni

I grafi sono strutture dati caratterizzate dalla presenza di vertici e archi e sono solitamente rappresentati da G(V, E), in cui G è il grafico, V è l'insieme dei vertici e E - senza troppa fantasia - l'insieme degli archi.

I grafi solitamente sono rappresentati o da matrici o da liste. Se sono rappresentati da matrici, la memoria utilizzata è Θ(V2), perché ogni possibile arco è rappresentato, e il valore all'incrocio tra i due vertici è 1 se l'arco esiste, 0 altrimenti.

V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 1 0 0 0
V3 1 0 0 1 1
V4 0 0 1 0 0
V5 0 0 1 0 0

In questo esempio i vertici sono (V1, V2, V3, V4, V5) e gli archi sono ((V1, V2), (V2, V2), (V1, V3), (V3, V4), (V3, V5)).

Se il grafo è semplice, la matrice deve essere trasponibile senza che il risultato cambi; in altre parole, l'informazione di un "triangolo" di dati pari a V*(V-1)/2 è ridondante, perché l'arco (V1, V2) e (V2, V1) sono la stessa cosa:

V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 1 0 0
V3 1 0 0 1 1
V4 0 0 1 0 0
V5 0 0 1 0 0

Se invece gli archi hanno una direzione - come ad esempio le strade a senso unico, che vanno da V1 a V2 ma non viceversa - tutti gli archi sono importanti perché rappresentano un'informazione univoca.

La rappresentazione tramite liste di adiacenza invece contengono una lista di vertici, a ciascuno dei quali corrisponde una lista di altri vertici a cui sono collegati.
Il grafo riportato sopra sarebbe:

  • V1 → V2 → V3
  • V2 → V1 → V2
  • V3 → V1 → V4 → V5
  • V4 → V3
  • V5 → V3

Anche in questo caso, se il grafo non è orientato, alcune informazioni sono ridondanti (es. il collegamento tra V1 e V2 è rappresentato sia nella lista V1 sia nella V2), mentre nel caso di grafi orientati i due collegamenti rappresenterebbero entità diverse e non ci sarebbe ridondanza.

Visita del grafo

La visita del grafo permette, partendo da un vertice, di "toccare" tutti gli altri vertici collegati direttamente o indirettamente.

Si comincia da una sorgente, come nel problema dei flussi di Ricerca Operativa, e si visitano tutti i nodi collegati. Per fare questo, si colorano i nodi dapprima di bianco, poi in grigio, se sono stati visitati, e in nero se tutti i nodi adiacenti sono a loro volta stati visitati (sono in grigio o in nero).

Il seguito nel post Visita di un grafo.

 

Riflessioni sulla distribuzione normale

Posted by On Filed under Probabilità & statistica

fx=12πσe-12x-μσ2

Per oggi sono riuscito a scriverla. Riuscirò mai a capirla?

Distribuzione normale

Il senso sottostante a questa formula è che la distribuzione normale dipende dal valore medio e dalla varianza.

σ2 rappresenta la varianza. Più σ è grande e più c'è varianza, e quindi è più probabile trovare valori fuori dalla norma: la curva è quindi più piatta. Se invece σ è piccolo, la maggior parte dei valori sarà molto vicino alla media, e quindi la curva sarà più "appuntita". ±σ infatti sono i valori in cui stanno i due flessi della curva.

μ rappresenta il valore medio.

Il punto di partenza per comprendere questa funzione è e-x2 e il punto di partenza per questa è -x2: una parabola con il vertice in alto, che vale sempre meno di zero (tranne in 0,0). Elevare un valore per -x2 significa avere verso -∞ e +∞ valori sempre più piccoli in modo esponenziale, e avere 1 quando x=0. Abbiamo una curva a campana.

12πσ

è "solo" un fattore che riporta l'integrale improprio da -∞ e +∞ sempre a 1, sulla base della varianza: in pratica se la curva è più "piatta" per avere un integrale = 1 bisogna che sia più "alta".