Ricerca non informata: BFS e DFS

Due algoritmi nati per uscire dai labirinti che oggi guidano web crawler, code agent e alberi di ragionamento di un LLM.

Perché questo capitolo

BFS (breadth-first search) e DFS (depth-first search) sono i due algoritmi di esplorazione di grafi più antichi e più riutilizzati dell’informatica. Materiale da primo anno, in apparenza. Eppure ogni agente che esplora qualcosa — un filesystem in cerca di un file, una pagina web in cerca di link, un albero di mosse in cerca di una vittoria, un albero di pensieri intermedi in cerca di una soluzione — fa BFS o DFS sotto qualche maschera.

Capirli bene non è nostalgia accademica. È capire perché un crawler ranka la frontiera anziché trattarla come una coda, perché Tree-of-Thoughts valuta i nodi al livello, perché un code agent decide se entrare o meno in una directory, perché un planner simbolico esaurisce memoria su un dominio piccolo. Ognuno di questi sistemi è BFS o DFS con qualcosa in più: una priority, un ranker, un’euristica, un valutatore neurale. Per capire cosa quel “qualcosa in più” porta, serve prima vedere chiaro cosa BFS e DFS già fanno e dove si rompono.

C’è anche un motivo pedagogico più sottile. BFS e DFS sono i due algoritmi uninformed: non sanno dove sia il goal, esplorano solo basandosi sulla struttura del grafo. È esattamente questa ingenuità che li rende il punto di partenza giusto per parlare di tutto il resto. A* aggiunge un’euristica, MCTS aggiunge campionamento, beam search aggiunge un fattore massimo, ToT aggiunge uno scoring LLM. Sono varianti, raffinamenti, non rivoluzioni. Lo scheletro resta quello che Moore disegnò nel 1959 e che Tarjan formalizzò nel 1972.

Contesto

Un grafo G = (V, E) è un insieme di vertici V e un insieme di archi E che li collegano. Può essere diretto (gli archi hanno verso) o non diretto, pesato (gli archi hanno costo) o non pesato. Per BFS e DFS uninformed assumiamo non pesato — o, equivalentemente, costo uniforme su ogni arco.

Una ricerca parte da un nodo sorgente s e cerca un nodo che soddisfi un goal test: una funzione boolean che dice “questo nodo è una soluzione?”. Il goal test può essere “sei al nodo target t” oppure “soddisfi un predicato P”. Durante la ricerca l’algoritmo mantiene due strutture:

• Frontiera (in inglese frontier o open list): l’insieme dei nodi scoperti ma non ancora espansi. La struttura dati che la implementa decide la strategia: queue FIFO porta a BFS, stack LIFO porta a DFS, priority queue porta a uniform-cost o A*.
• Visited (in inglese closed list o explored set): l’insieme dei nodi già espansi, cioè quelli per cui abbiamo già generato i successori. Necessario su grafi (non solo alberi) per non riespandere e non ciclare.

I nomi nel grafo della storia di questi due algoritmi:

Charles Pierre Trémaux, ingegnere francese del XIX secolo, descrive una strategia per uscire dai labirinti: marca i corridoi che hai già percorso, segna i bivi quando li attraversi per la prima volta, torna indietro quando arrivi a un vicolo cieco o a un bivio già completamente esplorato. Édouard Lucas, matematico francese, riporta la strategia nel 1882 in Récréations mathématiques. È DFS in forma narrativa, senza ancora il vocabolario dei grafi.

Edward F. Moore, matematico americano ai Bell Labs, pubblica nel 1959 “The shortest path through a maze” come parte degli atti del symposium di Harvard sulla switching theory, la teoria dei circuiti di commutazione. Il problema concreto è: dato un labirinto rettangolare, cioè un grafo a griglia, trovare il cammino minimo da A a B. La soluzione di Moore è BFS: marca tutte le celle a distanza 1 da A, poi tutte quelle a distanza 2, e così via, finché non raggiungi B. È la prima formalizzazione algoritmica esplicita di BFS, motivata dal routing di filo nei circuiti telefonici. C.Y. Lee nel 1961 estenderà il metodo per il VLSI, tanto che in alcuni testi di elettronica BFS su griglia è chiamata “Lee algorithm”.

Robert Tarjan, informatico americano, pubblica nel 1972 “Depth-First Search and Linear Graph Algorithms” su SIAM Journal on Computing. È il paper che trasforma DFS da curiosità da labirinto in framework: classifica gli archi visitati durante DFS in tree edges, back edges, forward edges, cross edges, e mostra come questa classificazione permetta algoritmi lineari, cioè in tempo O(V+E), per problemi che prima ne richiedevano molto più: strongly connected components, biconnected components, articulation points, topological sort. Per questo lavoro Tarjan riceverà il Turing Award nel 1986 (condiviso con John Hopcroft).

Richard Korf, informatico AI a UCLA, pubblica nel 1985 “Depth-first iterative-deepening: An optimal admissible tree search” su Artificial Intelligence. Mostra che si può combinare la memoria O(bd) di DFS con l’ottimalità di BFS facendo DFS ripetuti con limite di profondità crescente. È l’algoritmo di scelta quando la memoria è stretta e la profondità della soluzione è sconosciuta.

Shunyu Yao e collaboratori (Princeton, Google DeepMind) pubblicano nel 2023 “Tree of Thoughts: Deliberate Problem Solving with Large Language Models”, un paper che applica BFS e DFS sull’albero di pensieri intermedi generati da un LLM, con un LLM-judge che valuta lo stato. È la riscoperta esplicita di BFS/DFS come scaffold per il reasoning di sistemi neurali — dimostrazione che gli algoritmi degli anni ‘50 e ‘70 non sono diventati obsoleti, sono diventati l’ossatura su cui si appoggia il nuovo.

L’intuizione

Due angoli, prima di scrivere una riga di codice.

Angolo 1 — l’onda e il filo di Arianna

BFS è un’onda che si espande dal centro. Lasci cadere un sasso in uno stagno: al tempo 1 hai un cerchio di raggio 1, al tempo 2 un cerchio di raggio 2, al tempo 3 un cerchio di raggio 3. Tutti i punti del cerchio di raggio k sono raggiunti contemporaneamente, e nessun punto fuori dal cerchio è raggiunto prima. Se cerchi il punto X, lo trovi appena il fronte d’onda lo tocca, e lo trovi necessariamente alla minima distanza da te — perché il fronte d’onda è equidistante.

DFS è un filo di Arianna in un labirinto. Tieni il filo svolto in una mano, entri in un corridoio, tieni la destra. Se arrivi a un bivio prendi una direzione qualunque, marca quella scelta, vai avanti. Se arrivi a un vicolo cieco, riavvolgi il filo finché torni all’ultimo bivio, e prendi un’altra strada. Trovi prima o poi tutto, ma in un ordine bizzarro: rami lontanissimi prima di nodi a due passi da te, perché DFS non si interessa della distanza, si interessa solo di andare il più a fondo possibile prima di tornare indietro.

L’asimmetria tra i due determina tutto il resto: complessità di tempo, complessità di spazio, ottimalità, completezza, comportamento su grafi infiniti, fragilità sui cicli.

Angolo 2 — la coda e la pila

C’è un altro modo, più strutturale, di vedere la differenza. BFS e DFS hanno lo stesso scheletro algoritmico. Mantieni una collezione di nodi “da visitare”, la frontiera. Ad ogni passo prendi un nodo dalla frontiera, lo espandi (cioè generi i suoi vicini), aggiungi i vicini non visitati alla frontiera, marchi il nodo come visitato. Ripeti finché la frontiera è vuota o trovi il goal.

L’unica differenza: come prendi il nodo dalla frontiera.

• Frontiera = queue FIFO (first in, first out): prendi sempre il nodo più vecchio. → BFS.
• Frontiera = stack LIFO (last in, first out): prendi sempre il nodo più recente. → DFS.

Cambiando una sola riga di codice — la struttura dati della frontiera — passi da onda a filo di Arianna. Questa è una delle astrazioni più belle dell’informatica classica: la stessa procedura, parametrizzata sulla strategia di selezione della frontiera, genera una famiglia di algoritmi. Sostituisci queue con priority queue (nodo con costo minimo) e ottieni Dijkstra. Sostituisci con priority queue su f(n) = g(n) + h(n) e ottieni A*. Sostituisci con scoring LLM e ottieni Tree-of-Thoughts. Lo skeleton è invariante, la policy di selezione è il parametro.

La meccanica

BFS in pseudocodice

BFS(G, s):
  frontier ← queue([s])
  visited  ← {s}
  parent[s] ← None
  while frontier non vuota:
    u ← frontier.dequeue()
    if goal(u): return reconstruct(parent, u)
    for v in neighbors(u):
      if v not in visited:
        visited.add(v)
        parent[v] ← u
        frontier.enqueue(v)
  return failure

Riga per riga. La frontiera parte con il solo nodo sorgente. Il visited set è inizializzato con la sorgente per non riprenderla mai più. Il dizionario parent permetterà di ricostruire il cammino quando troveremo il goal: si risale da goal a s seguendo i puntatori. Il loop prende il nodo più vecchio dalla frontiera (dequeue su una FIFO), controlla il goal, espande i vicini.

Il dettaglio cruciale è quando marchi un nodo come visitato. Lo marchi al momento dell’inserimento in frontiera (visited.add(v) prima di enqueue), non al momento dell’estrazione. Se aspettassi l’estrazione, lo stesso nodo potrebbe entrare in frontiera più volte attraverso vicini diversi, gonfiando la memoria.

TEOREMA (BFS è completo). Se il branching factor b è finito e una soluzione esiste a distanza finita, BFS la trova in tempo finito. Idea della prova: BFS visita tutti i nodi a distanza k prima di passare a distanza k+1. Se il goal è a distanza d, BFS lo raggiunge entro b + b² + … + b^d passi.

TEOREMA (BFS è ottimo per costi uniformi). Se ogni arco ha lo stesso costo, il primo cammino che BFS scopre verso il goal è il cammino con minimo numero di archi, quindi minimo costo. Idea della prova: il fronte d’onda è equidistante; quando il goal entra in frontiera, ci entra alla sua minima distanza dalla sorgente.

Complessità di BFS (assumendo b finito, soluzione a distanza d):

• Tempo: O(b^d) nel caso pessimo, O(V + E) se si visita tutto il grafo.
• Spazio: O(b^d) — la frontiera al livello d può contenere tutti i nodi a distanza d. Questo è il tallone d’Achille.

DFS in pseudocodice

Versione ricorsiva, la più naturale:

DFS(G, u):
  visited.add(u)
  if goal(u): return u
  for v in neighbors(u):
    if v not in visited:
      parent[v] ← u
      result ← DFS(G, v)
      if result is not None: return result
  return None

Versione iterativa con stack esplicito, utile quando la profondità rischia stack overflow ricorsivo:

DFS_iter(G, s):
  stack ← [s]
  visited ← {}
  while stack non vuota:
    u ← stack.pop()
    if u in visited: continue
    visited.add(u)
    if goal(u): return u
    for v in neighbors(u):
      if v not in visited:
        stack.push(v)

Una sottigliezza: nella versione iterativa con stack i vicini vengono visitati in ordine inverso rispetto alla versione ricorsiva (lo stack è LIFO, quindi l’ultimo inserito è il primo estratto). Per replicare l’ordine ricorsivo si pushano in ordine inverso, oppure si accetta la differenza.

Proprietà di DFS:

• Completezza: solo su grafi/alberi finiti con visited set. Su alberi infiniti DFS può non terminare mai (entra in un ramo infinito e non ne esce).
• Non ottimo: trova una soluzione, non la più corta. Può trovare un cammino di lunghezza 100 quando ne esiste uno di lunghezza 3.
• Tempo: O(b^m) dove m è la profondità massima dell’albero (può essere ≫ d, profondità della soluzione).
• Spazio: O(bm). Lineare nella profondità. È il vantaggio chiave di DFS.

Classificazione degli archi (Tarjan 1972)

Durante una DFS su grafo si possono classificare gli archi (u,v) in base alla relazione tra u e v nell’albero DFS:

• Tree edge: v è scoperto per la prima volta da u. È un arco dell’albero DFS.
• Back edge: v è antenato di u nell’albero DFS. Rivela un ciclo.
• Forward edge: v è discendente di u ma non figlio diretto (solo grafi diretti).
• Cross edge: v non è né antenato né discendente di u (solo grafi diretti).

Conseguenze immediate:

• Cycle detection: un grafo è aciclico se e solo se DFS non produce alcun back edge.
• Topological sort (su DAG): ordinare i nodi per finish time decrescente di DFS dà un ordinamento topologico, in tempo O(V+E).
• Strongly Connected Components: l’algoritmo di Tarjan e quello di Kosaraju identificano le SCC in O(V+E) usando due passaggi DFS.

Questa classificazione è la ragione per cui DFS è il pilastro degli algoritmi su grafo: non è solo un modo di esplorare, è una macchina di analisi strutturale.

Iterative deepening DFS (IDDFS)

IDDFS(G, s, max_depth):
  for limit in 0, 1, 2, ..., max_depth:
    result ← DLS(G, s, limit)   # depth-limited DFS
    if result is not None: return result
  return failure

Si fa DFS con limite di profondità 0, poi 1, poi 2, e così via. Sembra spreco — ogni livello rifa tutto il lavoro dei precedenti. Ma il calcolo dice altro.

A profondità d, IDDFS espande nodi per ciascuna depth limit da 0 a d. Il livello d ha b^d nodi (li espande una volta), il livello d-1 ha b^(d-1) nodi (li espande due volte: limit d-1 e limit d), il livello d-2 ha b^(d-2) nodi (li espande tre volte), ecc. Totale espansioni:

$$b^d + 2·b^(d-1) + 3·b^(d-2) + ... + d·b$$

Asintoticamente, per b > 1, questa somma è O(b^d). Cioè uguale a BFS in tempo. Lo spazio è O(bd), uguale a una singola DFS depth-limited.

TEOREMA (Korf 1985). IDDFS è asintoticamente ottimale fra gli algoritmi di ricerca uninformed che girano in spazio lineare nella profondità. È completo (se b finito), ottimo (per costi uniformi), tempo O(b^d), spazio O(bd).

L’overhead rispetto a BFS è il fattore b/(b-1) sul numero di espansioni. Per b=2 è 2x, per b=10 è 1.11x, per b=100 è 1.01x. Trascurabile in pratica per branching factor realistici.

Bidirectional search

Un’idea elegante: lancia due BFS, una da s, una da goal. Quando i due fronti si incontrano, hai un cammino. Se b è la branching factor in entrambe le direzioni e d la distanza, complessità O(b^(d/2)) anziché O(b^d). Per d=10 e b=10 si passa da 10^10 a 2·10^5: cinque ordini di grandezza. Spettacolare quando applicabile, ma serve sapere il goal a priori e poter espandere all’indietro (predecessor function), che spesso non si ha.

Stati versus nodi

Distinzione fondamentale (Russell-Norvig, Artificial Intelligence: A Modern Approach, 4th ed., capitolo 3): un nodo nell’albero di ricerca rappresenta un cammino dalla sorgente, non solo uno stato. Due nodi possono corrispondere allo stesso stato se il grafo ha cicli o se cammini diversi convergono. Il visited set deduplica per stato, non per nodo. In ricerca su alberi (no cicli, no convergenze) non serve visited; in ricerca su grafo serve. Confondere stati e nodi è una delle fonti più frequenti di bug nei planner.

Lo scheletro comune in una funzione parametrizzata

Per fissare definitivamente l’idea che BFS e DFS sono la stessa cosa parametrizzata sulla strategia di selezione, ecco una funzione Python unica che esegue l’una o l’altra a seconda del parametro strategy:

from collections import deque

def graph_search(graph, start, goal, strategy="bfs"):
    if strategy == "bfs":
        frontier = deque([start]); pop = frontier.popleft
    elif strategy == "dfs":
        frontier = [start]; pop = frontier.pop
    else:
        raise ValueError(strategy)
    visited = {start}; parent = {start: None}
    while frontier:
        u = pop()
        if u == goal:
            path = []
            cur = u
            while cur is not None:
                path.append(cur); cur = parent[cur]
            return list(reversed(path))
        for v in graph.get(u, []):
            if v not in visited:
                visited.add(v); parent[v] = u
                frontier.append(v)
    return None

Cambiando la stringa "bfs" in "dfs" cambia il comportamento, perché cambia come si pesca dalla frontiera: popleft (FIFO, BFS) versus pop (LIFO, DFS). Il resto della funzione è identico. È esattamente questa simmetria che permette di vedere A*, Dijkstra, beam search, ToT come ulteriori sostituzioni della politica di pop. La base concettuale di tutta la famiglia di algoritmi di ricerca è qui, in una decina di righe.

Esempi

Esempio 1 — numerico, a mano

Grafo non diretto su 6 nodi, archi: A-B, A-C, B-D, C-D, C-E, D-F, E-F. Sorgente A.

Vicini in ordine alfabetico per riproducibilità.

BFS:

• frontier = [A], visited = {A}.
• estrai A, vicini B C → frontier = [B, C], visited = {A, B, C}.
• estrai B, vicini A D (A già visto) → aggiungi D, frontier = [C, D].
• estrai C, vicini A D E (A,D già visti o pendenti) → aggiungi E, frontier = [D, E].
• estrai D, vicini B C F → aggiungi F, frontier = [E, F].
• estrai E, vicini C F → F già pendente.
• estrai F. Ordine BFS: A, B, C, D, E, F. Livelli: 0, 1, 1, 2, 2, 3.

DFS ricorsivo:

• visito A, vicini B C, scendo in B.
• visito B, vicini A D, scendo in D.
• visito D, vicini B C F, scendo in C (B già visto).
• visito C, vicini A D E, scendo in E (A, D già visti).
• visito E, vicini C F, scendo in F.
• visito F. Ordine DFS: A, B, D, C, E, F.

Stesso grafo, ordini diversi. BFS è “ampio prima”, DFS è “profondo prima”.

Esempio 2 — codice Python, gridworld 5×5

Trovare shortest path in una griglia 5×5 con muri da (0,0) a (4,4). Movimento ortogonale (4-connected). BFS è la scelta naturale perché tutti i passi costano 1.

from collections import deque

def bfs_grid(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    frontier = deque([start])
    parent = {start: None}
    while frontier:
        r, c = frontier.popleft()
        if (r, c) == goal:
            # ricostruisci il path
            path = []
            cur = goal
            while cur is not None:
                path.append(cur)
                cur = parent[cur]
            return list(reversed(path))
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols \
               and grid[nr][nc] == 0 \
               and (nr, nc) not in parent:
                parent[(nr, nc)] = (r, c)
                frontier.append((nr, nc))
    return None

grid = [
    [0,0,0,0,0],
    [1,1,0,1,0],
    [0,0,0,1,0],
    [0,1,1,1,0],
    [0,0,0,0,0],
]
print(bfs_grid(grid, (0,0), (4,4)))
# [(0,0),(0,1),(0,2),(1,2),(2,2),(2,1),(2,0),(3,0),(4,0),(4,1),(4,2),(4,3),(4,4)]

Complessità: O(R·C) celle visitate, O(R·C) memoria nel caso pessimo (frontiera può contenere un’intera “diagonale” di celle). Per griglia 1000×1000 = 10^6 celle, gestibile.

DFS sulla stessa griglia per maze solving (trova un cammino, non necessariamente il più corto):

def dfs_grid(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    visited = set()
    parent = {start: None}
    stack = [start]
    while stack:
        r, c = stack.pop()
        if (r, c) in visited: continue
        visited.add((r, c))
        if (r, c) == goal:
            path = []
            cur = goal
            while cur is not None:
                path.append(cur); cur = parent[cur]
            return list(reversed(path))
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols \
               and grid[nr][nc] == 0 \
               and (nr, nc) not in visited:
                parent[(nr, nc)] = (r, c)
                stack.append((nr, nc))
    return None

Stessa griglia, l’output di DFS sarà tipicamente un cammino più lungo del BFS — DFS non si preoccupa della lunghezza, segue il primo ramo che lo porta al goal.

Esempio 3 — Tree of Thoughts su Game of 24

Game of 24: dati 4 numeri (es. 4, 9, 10, 13), trovare un’espressione con +, -, ×, / e parentesi che valga 24. Per (4, 9, 10, 13): (10 - 4) × (13 - 9) = 24.

Yao et al. 2023 propongono ToT-BFS come segue. Lo stato è un set di numeri rimanenti più la storia delle operazioni. La radice è (4, 9, 10, 13), gli stati a profondità 1 sono i risultati delle operazioni a 2 numeri, ecc. A profondità 3 hai un singolo numero: se è 24, soluzione.

L’LLM agisce come generator (produce 5-10 candidate operations per stato) e come valutatore (per ogni stato dice “sure” / “maybe” / “impossible” — cioè “questo stato porta a 24?”). ToT-BFS:

ToT-BFS(root, breadth_limit b, depth_limit d):
  frontier ← [root]
  for level in 0..d:
    candidates ← []
    for state in frontier:
      next_states ← LLM_propose(state, k=5)  # genera 5 mosse
      candidates += next_states
    scored ← [(s, LLM_evaluate(s)) for s in candidates]
    frontier ← top_b(scored, key=score)
  return any goal in frontier

ToT-DFS sullo stesso problema scende lungo un singolo branch, valuta, se il valutatore dice “impossible” backtracka. Sui benchmark di Yao 2023:

Metodo	Game of 24	Crosswords
Chain-of-Thought (1 sample)	4%	16%
CoT-self-consistency (k=100)	9%	—
ToT-BFS (b=5, d=3)	74%	60%
ToT-DFS (b=5)	—	65%

Cosa è BFS qui e cosa è in più? Lo scheletro è BFS classico: livelli, frontiera, espansione per livello. Cosa cambia: la frontiera non è FIFO ma ranked (top-b per score), il costo per nodo non è 1 ma una chiamata LLM (decine di token, latenza). EQUIVALENZA argomentabile: la struttura per livelli di ToT-BFS è la stessa di BFS classico applicato all’albero di pensieri. ANALOGIA, non equivalenza, sul management della frontiera: rankata, non FIFO.

Applicazioni pratiche

Web crawler (Google, 1998). Il crawler descritto da Brin e Page nel paper fondante di Google parte da seed URL e segue link in BFS, gestendo politeness (non martellare un dominio singolo), dedup (URL canonicalization, hash su contenuto), priority (PageRank parziale + freschezza). In pratica la “queue” è una priority queue e quindi è uniform-cost search (preludio a Dijkstra) più che BFS pura. Ma l’ossatura è BFS e il vocabolario operativo (frontier, seed, fetch, parse, enqueue) è BFS. ANALOGIA pratica forte: web crawler ↔ BFS su grafo internet.

flowchart LR
  Seed[URL seed] --> Frontier[Priority Queue / Frontier]
  Frontier --> Fetcher[Fetcher worker]
  Fetcher -->|HTML| Parser[Parser / Estrattore link]
  Parser --> Dedup{Canonicalizzazione URL + dedup hash}
  Dedup -- nuovo --> Frontier
  Dedup -- visto --> Drop[Scartato]
  Fetcher --> Politeness[Gate di politeness per dominio]
  Politeness --> Frontier
  Parser --> Index[Indice / storage]

Figura 5 — pipeline di un web crawler — seed URL, frontier come priority queue, fetcher worker, parser/estrattore link, canonicalization e dedup hash, politeness gate per dominio, indice/storage

Code agent file traversal. Un agente che cerca un simbolo o un pattern in un repo fa DFS o BFS sul filesystem. Strategie tipiche:

• DFS su directory tree con os.walk: economico in memoria, va in profondità, può perdersi in node_modules/ o .git/ se non si filtra.
• BFS con priority basata su signal (filename match, file recency, README presence): più “intelligente”, più memoria, comportamento simile a un dev che apre prima i file più probabili.
• AST traversal in compiler e linter: classicamente DFS con visitor pattern (la radice è il programma, i figli sono espressioni, statement, ecc.).

LangGraph e agent graph navigation (LangGraph: framework Python per orchestrare workflow agent come grafi orientati, sviluppato da LangChain Inc., 2023). LangGraph rappresenta workflow agent come grafo con nodi (funzioni o LLM call) e archi condizionali. L’execution è una traversal — non BFS/DFS pura, ma il modello mentale è quello.

Symbolic planners (STRIPS, PDDL). Forward state-space planners cercano sequenze di azioni che portano dallo stato iniziale al goal. BFS, IDDFS o A* su stati di mondo. Il planner classico Fast Forward (Hoffmann-Nebel 2001) è una BFS guidata da un’euristica relaxed-graphplan.

LATS (Language Agent Tree Search), Zhou et al. 2023. Applica MCTS (preludio del prossimo capitolo) a sequenze di azioni di un agente ReAct, ma la spina dorsale dell’esplorazione è BFS-like nel senso che mantiene rami multipli aperti e li espande progressivamente.

Dependency resolution. npm, pip, cargo risolvono i dipendenze con DFS o BFS sul grafo di dipendenze, gestendo cicli (back edges → conflitti) e versioni multiple. Topological sort per determinare l’ordine di build è applicazione diretta di DFS classificato à la Tarjan.

Tree-of-Thoughts e successori (Yao 2023, LATS 2023, RAP, ToolGen). Vedere esempio 3. Lo schema “albero di stati intermedi + valutatore esterno + frontiera per livelli” è BFS al primo ordine, con scoring sopra.

Dove si rompe

BFS e DFS sono potenti perché semplici, ma la semplicità ha un prezzo. Vale la pena vedere chiaro dove cedono, perché ogni cedimento corrisponde a una variante più sofisticata che incontreremo nei capitoli successivi.

Memoria di BFS esplode. O(b^d) sulla frontiera. Per il 8-puzzle (b ≈ 3, d ≈ 22) si arriva a 3^22 ≈ 31 miliardi di stati. Non gestibile in RAM. Per il 15-puzzle è impossibile senza euristica. Soluzioni: IDDFS, A*, IDA*. Il successore A* (capitolo search-a-star in preparazione) usa un’euristica per focalizzare la frontiera, e IDA* combina A* con la memoria O(bd) di IDDFS.

Cicli rompono DFS senza visited. Senza visited set, DFS su grafo con cicli loopa per sempre. Con visited set DFS perde il vantaggio di memoria O(bd) e diventa O(V) per il visited. Su grafi enormi (web), il visited set diventa il collo di bottiglia, gestito con bloom filter o hash distribuiti.

Costo non uniforme rompe ottimalità di BFS. Se gli archi hanno costi diversi (es. distanze stradali), il primo cammino scoperto da BFS non è il più corto in costo. Servono Dijkstra (uniform-cost search) o A*. Esempio classico: BFS su una mappa stradale dove autostrade hanno costo 1 per km e strade locali costo 2 per km — BFS troverebbe il cammino con meno archi, non quello con tempo minimo.

Branching factor enorme satura BFS. Per ToT con LLM che genera 100 thoughts per nodo, b=100 e BFS con d=3 ha 100^3 = un milione di chiamate LLM. Costo proibitivo. Soluzioni: pruning aggressivo (top-k), beam search (mantieni solo b più promettenti), MCTS (campionamento).

Algoritmi uninformed scartano informazione del goal. È la limitazione strutturale di BFS/DFS: non sanno che il goal è “in quella direzione”. Questo motiva tutto il filone dei informed search (capitolo search-a-star in preparazione, e MCTS in monte-carlo-tree-search in preparazione).

Depth limit di IDDFS arbitrario. Va deciso a priori. Troppo basso: missa la soluzione. Troppo alto: spreco di tempo nelle iterazioni profonde. Su problemi come planning STRIPS la profondità della soluzione è ignota.

Concorrenza. BFS sequenziale assume che la frontiera sia gestita da un singolo loop. In sistemi multi-agent paralleli (più worker che pescano dalla frontiera) servono lock-free queue, attenzione a race condition sul visited set, gestione di duplicati. La parallelizzazione di BFS è un campo a sé (parallel BFS su GPU, multi-thread BFS).

Tree-of-Thoughts non è BFS pura. Il management della frontiera con scoring rompe l’invariante FIFO. Inoltre il valutatore LLM è rumoroso: può dire “impossible” su uno stato che invece porta al goal, e BFS classica non recupera (non riesplora rami scartati). ToT in pratica richiede tuning empirico di b, d, e prompt del valutatore.

Web crawler “BFS” è in realtà priority queue. Un crawler vero non è BFS pura: vuole frequenza diversa per pagine diverse (frontpage news ogni minuto, archivi di rado), politeness (max N richieste/dominio/sec), focus topicali (crawl più aggressivo su domini di alto rank). La struttura è una priority queue con cost composito, più vicina a uniform-cost search che a BFS. Marca questa come ANALOGIA pratica: è realizzato come BFS al primo ordine, ma in produzione è una variante con scoring.

Cycle detection costoso su grafi giganti. Su filesystem con symlink, su web con redirect chain, il visited set è enorme. Si ricorre a hash truncati, bloom filter, partizionamento. Falsi positivi sono accettabili (un nodo non rivisitato per errore è un costo, non un bug catastrofico).

Stati vs nodi: bug ricorrenti. Se il visited set deduplica per nodo (cammino) anziché per stato, il consumo di memoria esplode. Se deduplica per stato ma il parent punta al primo cammino trovato (potenzialmente non ottimo se i pesi non sono uniformi), si introducono errori sottili. È una sorgente classica di bug nei planner.

Branching factor variabile. Nei grafi reali b non è costante: alcuni nodi hanno 2 vicini, altri ne hanno 200. La complessità O(b^d) è una semplificazione. Per analisi accurate si usa il effective branching factor, definito da Russell-Norvig come la b che, su un albero uniforme di profondità d, produrrebbe lo stesso numero di espansioni osservate. È un indicatore empirico, non a priori.

Ordine dei vicini. L’output di DFS dipende dall’ordine in cui si enumerano i vicini. Su grafi rappresentati come dizionari Python in versioni recenti (3.7+) l’ordine di inserimento è preservato, ma su set non lo è. Risultati riproducibili richiedono un ordine deterministico — alfabetico, per ID, per qualche signal — altrimenti due run dello stesso DFS producono cammini diversi. Per BFS lo stesso problema vale ma è meno visibile perché l’ottimalità (per costi uniformi) è preservata: cambia il quale cammino di lunghezza minima, non che ne troviamo uno.

Ricerca su alberi infiniti. Se il grafo è di fatto un albero infinito (tipico dei sistemi simbolici di reasoning, dove gli stati sono tutti distinti perché hanno cronologia diversa), DFS senza depth limit non termina mai. BFS termina se il goal esiste a profondità finita, ma esaurisce memoria. IDDFS è la scelta sensata in questo regime. Tree-of-Thoughts taglia l’albero artificialmente con un depth limit hard (tipicamente 3-5 livelli) più scoring per pruning.

Costi diversi nello stesso problema. Nei grafi reali archi diversi possono avere costi molto diversi. Per esempio in un crawler una pagina di 10 KB e una di 10 MB hanno costo di fetch molto diverso; in un planner un’azione “spostati di un metro” e una “vola in elicottero a Tokyo” hanno costo diverso. BFS ignora questo. Dijkstra (uniform-cost search) è la generalizzazione necessaria; A* la versione informata.

LLM-evaluator nel ToT. Il valutatore “sure/maybe/impossible” usato da Yao 2023 è un LLM, non un oracolo. È rumoroso, sensibile al prompt, costoso. Se il valutatore sbaglia “impossible” su uno stato sub-ottimo ma valido, ToT-BFS prune un ramo che conteneva la soluzione e fallisce. ToT-DFS aggrava il problema perché non riesplora rami già scartati. La robustezza di ToT richiede un valutatore calibrato — open problem aperto.

Collegamenti

• complessità Big-O: analisi O(b^d), O(bm) per i due algoritmi presuppone il vocabolario asintotico.
• giochi e definizione: un gioco a informazione perfetta ha un albero di stati, esplorabile con BFS/DFS prima di passare a minimax.
• minimax e alpha-beta: minimax è DFS sull’albero di gioco con backup di valore. Alpha-beta è DFS con potatura.
• multi-armed bandit: UCB sostituisce la coda FIFO con una scelta basata su upper confidence bound, preludio a UCT.
• UCB e Thompson sampling: la generalizzazione probabilistica della scelta della frontiera, base di MCTS.
• Markov Decision Process: MDP estende il grafo con stati stocastici e ricompense; BFS/DFS su MDP non basta, servono value/policy iteration.
• value iteration e policy iteration: forme di “search by relaxation” che maturano l’idea di esplorazione su grafo orientato.
• search-a-star (in preparazione): aggiunge un’euristica alla frontiera per renderla informata.
• monte-carlo-tree-search (in preparazione): combina BFS sui rami visitati e simulazione su quelli non visitati, con UCB per la selezione.
• tot-got (in preparazione): Tree of Thoughts e Graph of Thoughts; BFS/DFS con scoring LLM.
• graph-algorithms-base (in preparazione): trattazione algoritmica completa con Dijkstra, topological sort, SCC.

Per andare oltre

• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (4th ed., MIT Press, 2022), capitolo 22 “Elementary Graph Algorithms”. Trattazione standard con prove e analisi formale.
• Russell, Norvig, Artificial Intelligence: A Modern Approach (4th ed., Pearson, 2021), capitolo 3 “Solving Problems by Searching”. Il framework AIMA per state-space search, problem formulation, frontier, explored set, uninformed vs informed.
• Sedgewick, Wayne, Algorithms (4th ed., Addison-Wesley, 2011), capitolo 4 “Graphs”. Implementazioni didattiche, intuizione visiva, applicazioni pratiche (six degrees, web crawler, kevin-bacon).
• Korf, R.E. (1985), “Depth-first iterative-deepening: An optimal admissible tree search”, Artificial Intelligence 27(1):97-109. Il paper canonico su IDDFS.
• Yao, S. et al. (2023), “Tree of Thoughts: Deliberate Problem Solving with Large Language Models”, arXiv:2305.10601. BFS/DFS applicate ad alberi di pensieri.