Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni

Le basi dell’intelligenza artificiale in modo visivo: cos’è lo spazio degli stati, come funzionano BFS, DFS, UCS, la ricerca greedy e A*, cos’è un’euristica e che cosa c’entra l’apprendimento automatico.

14 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 21 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Quando oggi si parla di intelligenza artificiale, la maggior parte delle persone pensa alle reti neurali e ai grandi modelli linguistici. Eppure, molto prima che le macchine imparassero dai dati, sapevano già cercare. La navigazione su una mappa, una mossa a scacchi, il piano di un robot in un magazzino — tutto questo è la ricerca di un percorso in uno spazio di possibilità. La ricerca nello spazio degli stati è il primo capitolo di ogni manuale di intelligenza artificiale, e le sue idee le ritroverai anche nell’apprendimento automatico: euristiche, ottimizzazione, ricerca della soluzione migliore.

Qui trovi ogni concetto due volte: prima una definizione matematica precisa, subito sotto la stessa cosa in parole semplici. Tutte le animazioni sono l’esecuzione reale dell’algoritmo — niente è disegnato a mano.

1. Che cos’è lo spazio degli stati

Prima di cercare qualsiasi cosa, dobbiamo descrivere il problema in modo che un computer lo capisca. A questo serve il problema di ricerca:

Definizione — problema di ricerca

Un problema di ricerca è una sestupla P = (S, s₀, A, T, G, c), dove

• S è l’insieme degli stati,
• s₀ ∈ S è lo stato iniziale,
• A(s) è l’insieme delle azioni applicabili nello stato s,
• T : S × A → S è la funzione di transizione; lo stato s′ = T(s, a) è un successore dello stato s,
• G ⊆ S è l’insieme degli stati obiettivo,
• c : S × A → ℝ⁺ è il costo di un’azione, sempre positivo.

Definizione — percorso, soluzione, ottimo

Un percorso di lunghezza k è una sequenza s₀, a₁, s₁, …, a_k, s_k, dove s_i = T(s_i−1, a_i).

Il costo del percorso è la somma dei costi delle azioni: g = ∑_i=1^k c(s_i−1, a_i).

Una soluzione è un percorso che termina in un obiettivo: s_k ∈ G. Una soluzione ottima è una soluzione di costo minimo; tale costo si indica con C*.

Gli stati collegati dalle azioni formano un grafo orientato: gli stati sono i vertici, le azioni archi con peso c. Cercare una soluzione significa quindi trovare nel grafo un percorso da s₀ a uno dei vertici di G. L’esempio classico è il gioco dell’8: tessere da 1 a 8 in una cornice 3 × 3 e una casella vuota. Uno stato è la disposizione delle tessere, un’azione lo spostamento della casella vuota e l’obiettivo le tessere in ordine:

Sembra innocuo, ma il gioco dell’8 ha 181 440 stati raggiungibili e il suo fratello maggiore, il gioco del 15, più di diecimila miliardi. Per questo il grafo non lo costruiamo mai tutto in anticipo. L’algoritmo lo scopre man mano — dalla funzione di transizione calcola soltanto i successori dello stato in cui si trova.

2. Il problema: attraversare un labirinto

Vedremo tutti gli algoritmi sullo stesso problema. Abbiamo un labirinto di 9 × 14 caselle e vogliamo andare dalla partenza all’arrivo spendendo il meno possibile. Prima di tutto, cosa significa ogni casella:

• Casella libera — entrarci costa 1
• Fango — si può attraversare, ma entrarci costa 5
• Muro — non ci si può entrare
• S Partenza (start) — lo stato iniziale, la casella (0, 0)
• G Arrivo (goal) — la casella (8, 13)
• Casella esplorata — l’algoritmo l’ha espansa
• Percorso trovato — il risultato dell’algoritmo

Formulazione formale

Scriviamo una casella come coppia (r, s) — riga r ∈ {0, …, 8}, colonna s ∈ {0, …, 13}. Indichiamo con Z l’insieme dei muri e con B l’insieme delle caselle di fango.

• Stati: S = {(r, s) : (r, s) ∉ Z} — tutte le caselle tranne i muri.
• Stato iniziale: s₀ = (0, 0). Obiettivo: G = {(8, 13)}.
• Azioni: A = {↑, →, ↓, ←}. Un’azione è applicabile in uno stato solo se porta a una casella dentro la griglia che non sia un muro.
• Transizione: T((r, s), →) = (r, s + 1), e analogamente per le altre direzioni.
• Costo: c(x, a) = 5 se T(x, a) ∈ B, altrimenti 1 — si paga per la casella in cui si entra.
• Compito: trovare una soluzione di costo minimo C*.

Il fango è messo apposta sul tragitto più diretto. Vedremo che non tutti gli algoritmi se ne accorgono: alcuni contano solo i passi, altri il costo reale.

3. Lo scheletro comune a tutti gli algoritmi

Tutti gli algoritmi dell’articolo hanno lo stesso scheletro. Si differenziano solo per una decisione.

Definizione — frontiera, stati chiusi, espansione

La frontiera (frontier) F ⊆ S è l’insieme degli stati che l’algoritmo ha già scoperto ma non ancora espanso.

Gli stati chiusi E ⊆ S sono gli stati già espansi.

Espandere uno stato s significa calcolare tutti i suoi successori {T(s, a) : a ∈ A(s)} e aggiungere a F quelli che non sono in E.

frontier = [start]
closed = {}
finché frontier non è vuota:
    state = choose_from(frontier)  # ← è qui che gli algoritmi si differenziano
    se state è l’obiettivo: fatto
    aggiungi state a closed
    per ogni successore di state:
        se non è ancora chiuso: aggiungilo a frontier

Tutta la differenza tra gli algoritmi sta in una sola riga: quale stato della frontiera scegliamo come prossimo. Una coda, una pila o una coda di priorità in base a un certo numero. Tutto il resto si regge su questo.

4. Ricerca in ampiezza (BFS)

Definizione — BFS

La frontiera F è una coda (FIFO): si espande lo stato entrato in F per primo.

Conseguenza: gli stati vengono espansi in ordine di profondità d(s) — il numero di azioni da s₀. Per questo BFS trova la soluzione con il minor numero di azioni.

Se b è il fattore di ramificazione (il numero massimo di successori di uno stato) e d la profondità della soluzione meno profonda, BFS genera al massimo b + b² + … + b^d = O(b^d) stati e ne tiene altrettanti in memoria.

Nel labirinto l’onda si vede bene — si allarga in tutte le direzioni finché non incontra l’arrivo:

Nota però che il percorso passa dritto nel fango. BFS conta le azioni, non il costo — per lui un passo nel fango vale quanto un passo sull’asciutto. Il percorso più corto è risultato di 25 passi, ma con costo 37. BFS è ottimo solo quando tutte le azioni hanno lo stesso costo.

from collections import deque

def bfs(start, goal, successors):
    frontier = deque([start])
    parent = {start: None}
    while frontier:
        state = frontier.popleft()          # coda: il primo a entrare è il primo a uscire
        if state == goal:
            return path(parent, goal)
        for nxt in successors(state):
            if nxt not in parent:
                parent[nxt] = state
                frontier.append(nxt)
    return None

def path(parent, state):
    result = []
    while state is not None:
        result.append(state)
        state = parent[state]
    return result[::-1]

5. Ricerca in profondità (DFS)

Definizione — DFS

La frontiera F è una pila (LIFO): si espande lo stato entrato in F per ultimo.

Se m è la profondità massima dello spazio degli stati, DFS tiene in memoria solo il ramo corrente e i suoi fratelli: O(b · m) stati. Il tempo nel caso peggiore è O(b^m).

DFS non è ottimo e in uno spazio infinito non è nemmeno completo — può scendere all’infinito.

Nell’albero si vede dall’ordine: A, B, D, H, I — e solo dopo E. Nel labirinto:

Qui DFS è stato fortunato ed è arrivato all’obiettivo senza esplorare molte caselle. Il percorso però è inutilmente lungo — 31 passi invece di 25 e costo 59.

Definizione — approfondimento iterativo (IDDFS)

Per ℓ = 0, 1, 2, … esegui un DFS che non espande stati più profondi di ℓ. Fermati alla prima soluzione trovata.

Gli stati a profondità i vengono generati (d − i + 1) volte, in totale ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) — come BFS, ma con una memoria di soli O(b · d).

6. Ricerca a costo uniforme (UCS)

Definizione — UCS

Per uno stato n, indichiamo con g(n) il costo del percorso più economico trovato finora da s₀ a n.

La frontiera è una coda di priorità ordinata per g: si espande lo stato con il g(n) minimo.

Se tutti i costi delle azioni sono ≥ ε > 0, UCS espande gli stati in ordine non decrescente di g, ed è quindi completo e ottimo. Il numero di stati espansi è O(b^{1 + ⌊C*/ε⌋}).

UCS ha aggirato il fango. Ha trovato un percorso con lo stesso numero di passi di BFS, ma con costo 25 invece di 37 — ed è garantito il più economico, cioè C* = 25. Il prezzo è che cerca alla cieca in tutte le direzioni: non sa dove si trovi l’obiettivo, quindi si allarga anche nella direzione opposta.

7. Euristica: stimare la strada verso l’obiettivo

Gli algoritmi visti finora sono non informati — dell’obiettivo sanno solo che lo riconosceranno quando ci metteranno piede. Gli algoritmi informati ricevono in più una stima di quanto manca.

Definizione — euristica

Indichiamo con h*(n) il costo del percorso ottimo dallo stato n all’obiettivo più vicino. Un’euristica è una funzione h : S → ℝ_≥0 che stima h*(n), con h(n) = 0 per n ∈ G.

h è ammissibile (admissible) se non sovrastima mai: ∀n ∈ S : h(n) ≤ h*(n).

h è consistente se per ogni stato n, azione a e successore n′ = T(n, a) vale h(n) ≤ c(n, a) + h(n′). Ogni euristica consistente è ammissibile.

Nel nostro labirinto viene naturale la distanza di Manhattan — il numero di caselle in orizzontale più in verticale, come quando cammini per le strade ad angolo retto di Manhattan:

8. Ricerca greedy

Definizione — ricerca greedy

La frontiera è una coda di priorità secondo f(n) = h(n): si espande lo stato che secondo la stima è più vicino all’obiettivo. Il costo accumulato g(n) non viene considerato.

La ricerca greedy non è ottima; con il controllo degli stati ripetuti è completa in uno spazio finito.

La ricerca greedy esplora poche caselle, ma va dove sembra più vicino e finisce su un percorso lungo e costoso — 31 passi, costo 59.

9. A*: il meglio dei due mondi

Definizione — A*

La frontiera è una coda di priorità secondo f(n) = g(n) + h(n) — la stima del costo dell’intero percorso dalla partenza all’obiettivo passando per n.

Teorema. Se h è consistente, i valori di f lungo ogni percorso non decrescono, A* espande gli stati in ordine non decrescente di f e il primo stato obiettivo espanso si trova su un percorso ottimo di costo C*. Nel farlo espande ogni stato con f(n) < C* e nessuno con f(n) > C*.

Per h ≡ 0, A* coincide con UCS; senza g sarebbe la ricerca greedy.

Stesso costo 25 di UCS, ma A* ha esplorato 37 caselle invece di 49. In un piccolo labirinto è una differenza di poche caselle; su una mappa con milioni di incroci è la differenza tra una risposta immediata e un minuto di attesa. Per questo A* (e le sue varianti) lo trovi nei navigatori, nei videogiochi e nella pianificazione del movimento dei robot.

import heapq

def a_star(start, goal, successors, h):
    frontier = [(h(start), 0, start)]        # (f, g, stato)
    g = {start: 0}
    parent = {start: None}
    while frontier:
        _, cost, state = heapq.heappop(frontier)
        if state == goal:
            return path(parent, goal), cost
        if cost > g[state]:
            continue                       # voce obsoleta, ne conosciamo già una più economica
        for nxt, step in successors(state):
            new = cost + step
            if new < g.get(nxt, float("inf")):
                g[nxt] = new
                parent[nxt] = state
                heapq.heappush(frontier, (new + h(nxt), new, nxt))
    return None

10. Confronto tra gli algoritmi

Definizione — proprietà di un algoritmo

Un algoritmo è completo se, per ogni problema che ha soluzione, restituisce una soluzione.

Un algoritmo è ottimo se la soluzione restituita ha costo C*.

b — fattore di ramificazione, d — profondità della soluzione meno profonda, m — profondità massima dello spazio. O(·) indica come crescono il tempo o la memoria con questi parametri.

* In uno spazio finito con il controllo degli stati ripetuti trovano sempre una soluzione. ** Con un’euristica consistente.

11. Ricerca locale: quando il percorso non conta

In alcuni problemi il percorso non ci interessa — vogliamo solo un buon stato finale. Un orario scolastico, la disposizione dei componenti su una scheda, la regolazione dei parametri.

Definizione — ricerca locale

Sono date una funzione obiettivo f : S → ℝ e un intorno N(s) ⊆ S di ogni stato. Cerchiamo s* = argmax_{s ∈ S} f(s).

Uno stato s è un massimo locale se f(s) ≥ f(s′) per ogni s′ ∈ N(s), e un massimo globale se ciò vale per ogni s′ ∈ S.

Hill climbing: ripeti s ← argmax_{s′ ∈ N(s)} f(s′) finché f cresce.

Per non restare bloccati si usano il riavvio casuale (far partire lo scalatore da punti diversi), gli algoritmi genetici, che incrociano e fanno mutare un’intera popolazione di soluzioni, oppure la ricottura simulata:

Ricottura simulata

Scegli un vicino casuale s′ ∈ N(s) e calcola Δ = f(s′) − f(s). Se Δ > 0, passa a s′; altrimenti passaci con probabilità e^Δ/T, dove la «temperatura» T scende gradualmente verso zero.

Ed è qui che il cerchio si chiude con l’apprendimento automatico. Addestrare una rete neurale è una ricerca locale nello spazio dei suoi pesi θ: la discesa del gradiente ripete θ ← θ − η ∇L(θ) — un passo di ampiezza η nella direzione in cui la funzione di errore L scende più rapidamente. È uno scalatore a testa in giù che, invece della vetta più alta, cerca la valle più bassa — e si scontra con gli stessi problemi: minimi locali e plateau.

12. Riepilogo

• Un problema di ricerca è una sestupla (S, s₀, A, T, G, c). Una soluzione è un percorso nel grafo degli stati, la soluzione ottima quella più economica.
• Gli algoritmi differiscono solo per quale stato scelgono dalla frontiera: coda (BFS), pila (DFS), g minimo (UCS), h minimo (greedy), g + h minimo (A*).
• BFS trova il minor numero di passi, UCS il costo più basso, A* il costo più basso esplorando il meno possibile — purché abbia un’euristica consistente.
• Quando non conta il percorso ma il risultato, entra in gioco la ricerca locale — e da lì è solo un passo verso la discesa del gradiente e l’apprendimento automatico.

Vuoi mettere le mani sugli algoritmi? Fai scrivere a un agente IA la tua visualizzazione — e poi cerca nel codice quell’unica riga in cui si differenziano.

La vedi diversamente? Scrivi a support@coden-app.com.