Ricerca in ampiezza

Da Wikipedia, l'enciclopedia libera.
Ricerca in ampiezza
Ordine di esplorazione dei nodi

Ordine di esplorazione dei nodi
Classe Algoritmo di ricerca
Struttura dati Grafo
Caso peggiore temporalmente O(|V|+|E|) = O(b^d)
Caso peggiore spazialmente O(|V|+|E|) = O(b^d)
Ottimale Si (per grafi non ordinati)
Completo Si
Algoritmi di ricerca su grafi ed alberi.
Ricerca
Altro
Correlato

Nella teoria dei grafi, la ricerca in ampiezza (in inglese breadth-first search, BFS) è un algoritmo di ricerca per grafi che partendo da un vertice (o nodo) detto sorgente permette di cercare il cammino fino ad un altro nodo scelto e connesso al nodo sorgente.

Algoritmo[modifica | modifica sorgente]

BFS è un metodo di ricerca non informato, ed ha il suo obiettivo quello di espandere il raggio d'azione al fine di esaminare tutti i nodi del grafo sistematicamente, fino a trovare il nodo cercato. In altre parole, se il nodo cercato non viene trovato, la ricerca procede in maniera esaustiva su tutti i nodi del grafo. Questo algoritmo non è di tipo euristico.

Il procedimento da seguire per metterlo in pratica è sintetizzato come segue:

1. Mettere in coda il nodo sorgente.

2. Togliere dalla coda un nodo (nella prima iterazione il nodo sorgente) ed esaminarlo.

  • Se l'elemento cercato è trovato in questo nodo viene restituito il risultato e la ricerca si interrompe.
  • Se l'elemento cercato non era in questo nodo mettere in coda tutti i successori non ancora visitati del nodo in analisi.

3. Se la coda è vuota, ogni nodo nel grafo è stato visitato e l'elemento non è stato trovato perché non presente e quindi la ricerca si interrompe.

4. Se la coda non è vuota si ripete il passo 2.

Se si volesse restituire l'albero breadth-first sarebbe necessario tenere nota di tutti i nodi visitati e del predecessore tramite il quale si è arrivati a loro. A tale scopo, a seconda dello stadio di elaborazione, sarebbe utile marcare i nodi con delle etichette quali "visitato", "in corso di visita" e "non visitato".

Implementazione[modifica | modifica sorgente]

L'algoritmo segue il procedimento descritto nella sezione "Algoritmo" e per poter essere eseguito e restituire dei risultati necessità dell'uso di alcune strutture dati qui di seguito elencate:

  • Lista di adiacenza adj[u] che contiene la lista dei nodi adiacenti al generico nodo 'u'.
  • Array stato stato[u] che contiene lo stato ("visitato", "non visitato", "in corso di visita") del generico nodo 'u'.
  • Distanza d[u] che contiene la distanza del generico nodo u dal nodo "sorgente".
  • Array p[u] che contiene il predecessore del nodo 'u' nell'albero BFS.
  • Coda Q che contiene i nodi "in corso di visita".

È da notare che, nel caso in cui il grafo sia un albero, esiste un solo percorso per arrivare ad ogni vertice, per cui non è necessario utilizzare p[u] e si può semplificare l'implementazione. Per quanto riguarda le strutture dati restanti è da segnalare che sono indispensabili per un corretto funzionamento dell'algoritmo e che se nelle implementazioni non vengono utilizzate direttamente diventa necessario emularle tramite altre metodiche (es. Nell'implementazione python proposta, il campo "vertice.visitato = TRUE" nel tipo di dato "vertice" equivale ad avere la struttura dati stato[u]).

Dal punto di vista dell'algoritmo, tutti i nodi adiacenti ad un nodo, sono aggiunti ad una coda di tipo FIFO. In una tipica implementazione, i nodi che ancora non sono stati esaminati, sono posti in un contenitore (come una coda oppure una lista) etichettati come "non visitato", ed una volta esaminati, saranno collocati in un'altra struttura dati ed etichettati come "visitato".

Pseudocodice[modifica | modifica sorgente]

Input: un grafo G e un nodo radice v appartenente a G

1  funzione BFS(G,v):
2      crea coda Q
3      inserisci v in Q
4      marca v
5      while Q non è vuota:
6          t ← Q.toglidallacoda()
7          if t è quello che stavamo cercando:
8              return t
9          for all lati e in G.latiincidenti(t) do
12             u ← G.nodiadiacenti(t,e)
13             if u non è marcato:
14                  marca u
15                  inserisci u in Q
16     return none

Python[modifica | modifica sorgente]

Per grafi[modifica | modifica sorgente]

# R è il vertice da cui partiamo
coda = [R]
 
while coda:
    # operazione di dequeue
    vertice = coda.pop(0)
    vertice.visitato = True
    for adiacente in vertice.adiacenti:
        if not adiacente.visitato:
            # operazione di enqueue
            coda.append(adiacente)

Per alberi[modifica | modifica sorgente]

# R è la radice
coda = [R]
 
while coda:
    # operazione di dequeue
    vertice = coda.pop(0)
    # operazione di enqueue su ogni figlio
    coda.extend(vertice.figli)

Complessità[modifica | modifica sorgente]

Il tempo di esecuzione totale di questo algoritmo è O(V+E) dove V è l'insieme dei vertici del grafo ed E è l'insieme degli archi che collegano i vertici.

Applicazioni pratiche[modifica | modifica sorgente]

Testare grafi bipartiti[modifica | modifica sorgente]

Il metodo BFS può essere utilizzato per testare se un grafo è bipartito. La tecnica consiste nell'etichettare in maniera alternata con degli 0 e degli 1 i vertici visitati durante una ricerca. Partendo dal nodo sorgente ed etichettandolo con 0 si procede etichettando con 1 tutti i nodi adiacenti e viceversa per i nodi adiacenti. Se ad ogni passo un vertice ha nodi adiacenti già visitati e marcati con la sua stessa etichetta allora il grafo non è bipartito altrimenti il grafo è bipartito.

Crawler[modifica | modifica sorgente]

Tipicamente i crawler, che navigano la rete per indicizzare le pagine, visitano l'enorme grafo che essa rappresenta (dove ogni pagina viene vista come un vertice ed ogni link come un arco) con una visita in ampiezza, dato che essa comporta alcuni vantaggi:

  • quando un sito (le cui pagine si suppone siano strettamente interconnesse) viene visitato, viene probabilmente visitato nella sua interezza prima di allontanarsene
  • se si incontra una pagina già visitata, è abbastanza probabile che essa sia stata visitata di recente (e che quindi sia memorizzata in qualche sistema di cache)

Fa eccezione il caso di un crawler il cui scopo non sia navigare tutte le pagine del web, ma cercare pagine che si trovano solo in determinati siti, oppure che abbia dei criteri per preferire alcuni link ad altri; allora si preferirà una visita in profondità.

Note[modifica | modifica sorgente]

  • Diversamente dalla visita in profondità per i grafi e dalle sue varianti (pre-ordine, ordine, post-ordine) sugli alberi, la visita in ampiezza è difficilmente implementabile come algoritmo puramente ricorsivo, ma è piuttosto un esempio di programmazione dinamica.
  • È da notare che se si usasse uno stack invece di una coda si andrebbe a costituire un algoritmo DFS detto anche di "ricerca in profondità".

Voci correlate[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]