Menu Chiudi

Visita in AMPIEZZA – Coda FIFO

Condividi questo articolo:

Come sapete ScuolaX è un blog contenitore a supporto del lavoro di un folto gruppo di docenti. Durante questo periodo di contingenza abbiamo creato diversi video didattici tra cui quello presente qui sotto, stavolta reso pubblico sul web. Il seguente articolo serve di supporto per un corso specifico e sarà di volta in volta ampliato con testi ed esercizi man mano che il suddetto corso che lo utilizza andrà avanti. In questa pagina descriviamo dunque, per scopi didattici, l’algoritmo di ricerca in ampiezza in un albero.

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

Ecco lo pseudocodice che troviamo nel video:

1  Inizializza la frontiera con lo stato iniziale
2  Prendi il nodo della frontiera e rimuovilo
3  IF è uno stato goal THEN RETURN soluzione
4  Espandi il nodo scelto, 
5  aggiungi i nodi risultanti in frontiera.

Sotto uno pseudocodice più completo per un grafo:

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

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *