A* e euristiche ammissibili

La ricerca smette di essere cieca: f = g + h, dove g è quanto sei costato finora e h è quanto credi costerà finire. Tre lettere bastano per spiegare metà degli agenti che ragionano.

Perché questo capitolo

Il capitolo precedente ha mostrato come BFS e DFS esplorino un grafo senza alcuna informazione su dove sia il goal. Si limitano a espandere la frontiera in un certo ordine — onda concentrica per BFS, filo di Arianna per DFS — e prima o poi inciampano nella soluzione. È un comportamento uninformed, ingenuo nel senso letterale: non hai una stima di quanto sei vicino, ti muovi alla cieca.

Pochi problemi reali si comportano così. Quando un essere umano cerca un libro in una libreria, non parte dallo scaffale A1 e procede in ordine alfabetico fino a trovarlo: stima la sezione, salta lì, restringe. Quando un sistema GPS calcola un percorso da Roma a Milano, non esplora simmetricamente in tutte le direzioni: spinge la frontiera verso nord. Quando un LLM genera un piano di ragionamento, non valuta tutti i pensieri intermedi con uguale priorità: ne sceglie alcuni come più promettenti. In ogni caso, c’è una euristica: una stima del costo residuo che orienta la ricerca.

A* è la formalizzazione canonica di questa idea. Il salto da uninformed a informed è il passaggio chiave per qualunque agente che usi una stima del valore residuo — incluso un LLM che valuta i propri pensieri intermedi, un robot che decide quale corridoio prendere, un code agent che decide quale file aprire prima. Lo stesso scheletro algoritmico di BFS, una volta che la frontiera diventa una priority queue ordinata su una funzione informata, copre Dijkstra, A*, weighted A*, IDA*, anytime A* e — sotto qualche maschera — anche le varianti più recenti di Tree-of-Thoughts.

C’è anche un motivo teorico: A* è uno dei pochi algoritmi della storia in cui la condizione “best practice” è esattamente la condizione formale di ottimalità. Se l’euristica è admissible — se non sopravvaluta mai il costo residuo — A* trova la soluzione ottima. Punto. È una garanzia rara, e capire da dove viene rende molto più chiare le ANALOGIE moderne (heuristic learned da rete neurale, scoring LLM, value function in RL): si vede subito perché perdono la garanzia, e quanto si stanno avvicinando o allontanando dal caso pulito.

Contesto

Il setting è lo stesso di search-bfs-dfs: grafo G = (V, E), nodo sorgente s, goal test, frontiera, visited set. La differenza è che ora gli archi possono essere pesati: ogni arco (n, n’) ha un costo c(n, n’) >= 0. Cercare il “cammino migliore” significa cercare quello a costo totale minimo. BFS uninformed era il caso speciale c = 1 ovunque.

Le funzioni che compaiono nel resto del capitolo sono tre. La prima è g(n): il costo del cammino accumulato da s fino a n lungo il percorso che A* sta esplorando. La seconda è h*(n): il costo del cammino ottimo da n al goal. h* è in genere ignoto — se lo conoscessimo non avremmo bisogno di cercare. La terza è h(n): la stima di h*(n), l’euristica. È l’unico ingrediente nuovo rispetto al capitolo precedente.

Sull’euristica si chiedono due proprietà.

Admissibility: h(n) <= h*(n) per ogni n. L’euristica non sopravvaluta mai. È un lower bound ottimistico sul costo residuo.

Consistency (anche detta monotonicità): h(n) <= c(n, n’) + h(n’) per ogni arco (n, n’). Una forma di disuguaglianza triangolare: la stima da n non può essere maggiore del costo per arrivare a n’ più la stima da n’. La consistency implica admissibility, non viceversa.

I nomi nel grafo della storia.

Edsger W. Dijkstra (1930-2002, olandese, Turing Award 1972), allora ricercatore al Mathematisch Centrum di Amsterdam, pubblica nel 1959 “A Note on Two Problems in Connexion with Graphs” su Numerische Mathematik. Risolve il problema del cammino minimo a costi non negativi con una procedura che oggi tutti i corsi di algoritmi insegnano. Dijkstra raccontò di averlo pensato in venti minuti, in un caffè di Amsterdam, mentre con la fidanzata sceglieva un percorso da Rotterdam a Groningen. È l’algoritmo che precede A*: stesso scheletro, ma senza euristica — equivalente, come vedremo, ad A* con h = 0.

Peter E. Hart, Nils J. Nilsson (1933-2019) e Bertram Raphael (1936-2014), tre ricercatori del Stanford Research Institute (SRI), pubblicano nel 1968 “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” su IEEE Transactions on Systems Science and Cybernetics. Il contesto è il progetto Shakey, primo robot mobile capace di percepire, pianificare e muoversi in un ambiente di stanze e corridoi. Il robot doveva calcolare percorsi tra ostacoli: Dijkstra funzionava ma era lento, perché esplorava simmetricamente. Hart, Nilsson e Raphael generalizzano l’algoritmo permettendo una funzione euristica che orienta l’espansione, e — questo è il contributo profondo — dimostrano sotto quali condizioni la generalizzazione resta ottima. Una correzione del 1972 chiarisce le condizioni precise per il caso graph-search. Nasce A*.

Judea Pearl (n. 1936, israeliano-americano, Turing Award 2011), professore a UCLA, pubblica nel 1984 Heuristics: Intelligent Search Strategies for Computer Problem Solving: il primo trattato unificato sulle euristiche di ricerca. Formalizza la dominanza euristica, introduce concetti come informed-ness e well-informed heuristic, prova varianti delle condizioni di ottimalità. Pearl è successivamente diventato celebre per i lavori sulle Bayesian networks e sulla causalità, ma il suo libro del 1984 resta il riferimento canonico per la teoria della ricerca informata.

Richard Korf (n. 1956), informatico AI a UCLA, pubblica nel 1985 — stesso anno del paper IDS citato nel capitolo precedente — “Iterative-Deepening-A*” su Artificial Intelligence. Risolve il problema della memoria di A*: A* mantiene in RAM tutta la frontiera e tutti i nodi visti, e su problemi grandi (15-puzzle, Rubik) esaurisce memoria. IDA* combina iterative deepening con un f-bound euristico, ottenendo memoria O(bd) come DFS al prezzo di rivisitare nodi.

Sven Koenig (n. 1967, tedesco-americano) e Maxim Likhachev, robotici a USC e Carnegie Mellon, pubblicano nel 2002 “D* Lite” su AAAI. Variante di A* per ambienti dinamici, dove gli ostacoli vengono scoperti mentre il robot si muove. Ricalcola incrementalmente solo la parte del piano che cambia. È l’algoritmo usato nei Mars rovers Spirit e Opportunity per la navigazione planetaria.

Shunyu Yao e collaboratori (Princeton, Google DeepMind) pubblicano nel 2023 “Tree of Thoughts: Deliberate Problem Solving with Large Language Models” (NeurIPS 2023). L’albero dei pensieri di un LLM viene esplorato con BFS o DFS, con un LLM-judge che valuta lo stato. Le varianti dove il giudizio è usato come priorità globale ricadono — come ANALOGIA, non come equivalenza formale — su uno schema A*-with-learned-heuristic.

Il grafo concettuale, in sintesi: BFS uniform-cost ↔ Dijkstra ↔ A* con h=0. A* è la generalizzazione informata. Weighted A*, anytime A*, IDA*, D*-Lite sono varianti pensate per vincoli specifici (velocità, memoria, dinamicità). Tree-of-Thoughts è la riproposizione moderna sul tessuto LLM.

L’intuizione

Tre angoli, prima di scrivere una riga di codice o una formula.

Angolo 1 — la promessa di vicinanza al goal

Dijkstra espande sempre il nodo con costo accumulato minimo. Pensa a un’onda che si espande dal punto di partenza, ma non più a velocità uniforme: dove gli archi costano poco si espande in fretta, dove costano tanto si espande lenta. Il fronte d’onda è una superficie di livello equipotenziale nel costo accumulato. Quando l’onda tocca il goal, hai trovato il cammino minimo.

Questa onda ha però un difetto: è simmetrica rispetto alla sorgente. Non sa dove sta andando. Se il goal è a est e tu parti da Roma, l’onda Dijkstra si espande anche a ovest verso il Tirreno, anche a sud verso la Calabria, anche a nord verso Firenze. Tutti questi nodi entreranno nella frontiera prima che l’onda raggiunga Milano. È esplorazione sprecata.

A* aggiunge un secondo termine. Non solo guarda quanto sei costato finora — g(n) — ma anche quanto credi costerà finire — h(n). Sceglie il nodo con f(n) = g(n) + h(n) minimo, cioè il nodo che, se tutto va come stimato, sarà su un cammino totale corto. L’onda diventa asimmetrica: si allunga verso il goal e si schiaccia sul lato opposto. I nodi a ovest del Tirreno hanno g basso ma h alto, quindi f alto, quindi vengono espansi tardi o mai. La promessa di vicinanza al goal sposta la priorità.

L’osservazione cruciale: se h non sopravvaluta mai (h <= h*), questa deformazione dell’onda non costa nulla in ottimalità. Trovi sempre la stessa soluzione ottima di Dijkstra. Trovi solo prima.

Angolo 2 — la stessa skeleton, nuova policy di selezione

Il capitolo precedente ha messo in chiaro un punto: BFS e DFS hanno lo stesso scheletro. La frontiera, l’estrazione, l’espansione, il marker visited. Cambia solo come prendi il prossimo nodo dalla frontiera. Queue FIFO → BFS. Stack LIFO → DFS.

A* è il prossimo passo della stessa idea. Cambia la struttura dati della frontiera: priority queue ordinata su f(n) = g(n) + h(n). Tutto il resto resta identico. Non è un nuovo algoritmo, è una nuova policy di selezione sul medesimo skeleton.

Questo è importante perché rende esplicito il pattern. La famiglia “graph search con frontiera” è parametrizzata sulla policy:

• queue FIFO → BFS,
• stack LIFO → DFS,
• priority queue su g(n) → Dijkstra (uniform-cost search),
• priority queue su f(n) = g(n) + h(n) → A*,
• priority queue su f(n) = g(n) + w·h(n), w > 1 → weighted A*,
• priority queue su h(n) sola → greedy best-first,
• priority queue su scoring LLM → varianti di Tree-of-Thoughts.

Una sola riga di codice cambia. Cambiano tutte le proprietà — completezza, ottimalità, complessità, comportamento sugli infiniti — ma lo skeleton è invariante. Una volta colti questi sette membri della famiglia non c’è praticamente altro da imparare sulla ricerca classica: tutto il resto sono varianti su misura.

Angolo 3 — f come bilancio costi-promesse

Un terzo modo di leggere f(n) è contabile. g(n) è ciò che hai già speso: una somma di costi reali, certificati dal cammino effettivamente percorso. h(n) è ciò che ti aspetti di spendere ancora: una stima, soggetta a errore. f(n) = g(n) + h(n) è il bilancio totale stimato del piano “passa per n e poi vai al goal”.

Espandere il nodo con f minimo significa lavorare sul piano che, secondo il bilancio attuale, costerà di meno. È una scelta razionale sotto due ipotesi: (1) la stima h è onesta — non spaccia per veloce un cammino lento — e (2) il costo già speso non torna indietro — sunk cost. La condizione (1) è esattamente l’admissibility. La condizione (2) vale automaticamente: g(n) è dato, non è negoziabile.

Quando l’euristica sopravvaluta — h > h* — il bilancio diventa pessimista: A* può scartare un cammino che era in realtà il migliore, perché la stima lo dipingeva caro. Questa è la rottura più importante e ricorrerà in tutta la sezione “dove si rompe”.

La meccanica

Lo pseudocodice di A*

A*(start, goal, h):
  open    ← priority_queue()
  open.push(start, priority = h(start))
  g[start]      ← 0
  parent[start] ← None
  closed  ← {}

  while open non vuota:
    n ← open.pop_min()        # nodo con f(n) = g(n) + h(n) minimo
    if goal(n): return reconstruct(parent, n)
    closed.add(n)

    for n' in neighbors(n):
      tentative_g ← g[n] + cost(n, n')
      if n' in closed and tentative_g >= g[n']:
        continue
      if n' not in open or tentative_g < g[n']:
        g[n']      ← tentative_g
        parent[n'] ← n
        open.push_or_update(n', priority = tentative_g + h(n'))

  return failure

Riga per riga.

open è la frontiera: una priority queue, tipicamente un binary heap. open.pop_min() è O(log |open|), open.push è O(log |open|).

Il loop estrae sempre il nodo con f minimo. Se è il goal, ricostruisce il cammino risalendo parent da goal a start. Altrimenti il nodo va in closed: lo abbiamo appena espanso, in linea di principio non lo riapriremo.

Per ogni vicino n’ calcoliamo il costo tentativo: g attuale di n più il costo dell’arco. Se n’ è già in closed con g <= tentative_g, non c’è motivo di toccarlo: il cammino corrente non è migliore. Se n’ non è ancora in open, o è in open con g maggiore, lo aggiorniamo: nuovo g, nuovo parent, nuova priorità.

Una sottigliezza implementativa. push_or_update formalmente richiede una decrease-key sull’heap, operazione che binary heap standard non supporta in O(log n) senza indicizzazione. Pratica comune: inserisci comunque la nuova entry, e quando estrai un nodo controlla se la sua priorità corrisponde al g attuale; se è una entry stale, scartala e continua. Si paga in memoria, si guadagna in semplicità.

Tre teoremi e tre prove sketch

TEOREMA 1 (ottimalità di A tree-search con h admissible, Hart-Nilsson-Raphael 1968).* Se h è admissible, A tree-search restituisce una soluzione ottima.*

Sketch della prova. Sia C* il costo del cammino ottimo da start a goal. Considera il cammino ottimo P*: ogni nodo n su P* ha g(n) = costo da start a n lungo P*, e h(n) <= h*(n) per admissibility. Quindi f(n) = g(n) + h(n) <= g(n) + h*(n) = C*. Lungo P*, ogni nodo ha f <= C*. Per induzione, in ogni momento esiste in open almeno un nodo di P* con f <= C*. Supponi per assurdo che A* restituisca una soluzione G’ con costo C’ > C*. Allora al momento dell’estrazione di G’ c’era ancora un nodo di P* in open con f <= C* < C’. Ma A* estrae il minimo: avrebbe estratto quello, non G’. Contraddizione.

TEOREMA 2 (ottimalità di A graph-search con h consistent).* Se h è consistent, A graph-search restituisce una soluzione ottima e ogni nodo viene espanso al più una volta.*

Sketch. La consistency h(n) <= c(n, n’) + h(n’) si riscrive come f(n) = g(n) + h(n) <= g(n) + c(n, n’) + h(n’) = g(n’) + h(n’) = f(n’). Quindi f è non-decrescente lungo qualsiasi cammino esplorato. Quando A* estrae n, ogni cammino futuro che riraggiunga n avrà f >= f(n) attuale, quindi g(n) all’estrazione è già ottimo. Mai bisogno di riaprire.

TEOREMA 3 (dominanza euristica, Pearl 1984). Siano h1, h2 due euristiche admissible tali che h2(n) >= h1(n) per ogni n non goal. Allora A con h2 espande un sottoinsieme dei nodi espansi da A* con h1 (a meno di tie-breaking).*

Sketch. A* con h espande tutti i nodi con f(n) = g(n) + h(n) < C* (e alcuni con f = C*). Con h2 >= h1, f2 >= f1 ovunque, quindi {f2 < C*} ⊆ {f1 < C*}. Meno nodi sotto soglia, meno nodi espansi.

Conseguenza pratica: tra euristiche admissible, più informata vince sempre. La caccia alle euristiche dominanti è la forma classica della ricerca informata.

Dijkstra come caso particolare

EQUIVALENZA argomentata: Dijkstra ↔ A* con h = 0.

L’argomento è immediato. Se h = 0, allora f(n) = g(n) e A* estrae sempre il nodo con costo accumulato minimo. È esattamente Dijkstra. h = 0 è admissible (0 <= h* sempre, dato che h* >= 0) e consistent (0 <= c(n, n’) + 0 vero per costi non negativi), quindi i due teoremi precedenti si specializzano e ritrovano la garanzia di ottimalità di Dijkstra.

Una catena più lunga di equivalenze, da maneggiare con cautela: BFS uniform-cost ↔ Dijkstra ↔ A* con h = 0. Le ultime due sono EQUIVALENZE argomentabili (stesso scheletro, h diverso). La prima — BFS uniform-cost ↔ Dijkstra — è EQUIVALENZA quando i costi degli archi sono tutti uguali: BFS che espande in ordine di distanza in numero di archi e Dijkstra che espande in ordine di costo accumulato coincidono. Quando i costi sono variabili, BFS smette di essere ottimo per costo totale e si comporta come “primo che arriva in profondità”, mentre Dijkstra resta ottimo. Sono due algoritmi distinti che coincidono sotto ipotesi forti.

Esempi di euristiche admissible

Per il puzzle 8 (3x3 con un buco e otto tessere):

• h_misplaced(n): numero di tessere fuori posto. Admissible perché ogni tessera fuori posto deve muoversi almeno una volta. Debole.
• h_manhattan(n): somma delle distanze L1 (somma di |Δx| + |Δy|) di ogni tessera dalla sua posizione goal. Admissible perché ogni tessera deve fare almeno questi passi. Domina h_misplaced — ed è la scelta standard nei testi.
• h_linear_conflict, walking-distance, pattern databases (Culberson-Schaeffer 1998): euristiche più forti per il 15-puzzle, costruite pre-computando soluzioni a sotto-problemi.

Per pathfinding su grid 2D:

• Manhattan: |x1 - x2| + |y1 - y2|. Admissible se mosse 4-direzioni con costo unitario.
• Octile: distanza permettendo mosse diagonali a costo √2. Admissible se mosse 8-direzioni.
• Euclidean: √((x1 - x2)² + (y1 - y2)²). Sempre admissible per qualunque metrica reale.

Per routing GPS:

• distanza in linea retta (great-circle). Admissible: la strada non può essere più corta della retta.
• ALT (Goldberg-Harrelson 2005): pre-computa distanze da landmark, sfrutta la disuguaglianza triangolare per ottenere stime più strette.

Weighted A*

Un compromesso pratico: f(n) = g(n) + w·h(n) con w > 1. Non più ottimo, ma molto più veloce. Garanzia residua: la soluzione ha costo <= w · C*. Trade-off configurabile: w = 1 ottimo, w → ∞ greedy best-first (ignora il costo accumulato), valori intermedi compromesso fra qualità e velocità.

Anytime e ARA*

Likhachev, Gordon, Thrun (2003) propongono ARA* (Anytime Repairing A*): parte con w grande — soluzione veloce ma sub-ottima — e raffina decrescendo w, riusando il lavoro precedente. Restituisce via via soluzioni migliori finché c’è tempo. Adatto a robotica real-time dove “una soluzione subito, anche imperfetta” batte “la soluzione perfetta dopo”.

IDA*

IDA*(start, goal, h):
  bound ← h(start)
  while True:
    t ← search(start, 0, bound)
    if t = FOUND: return path
    if t = inf:   return failure
    bound ← t

search(node, g, bound):
  f ← g + h(node)
  if f > bound:    return f
  if goal(node):   return FOUND
  min ← inf
  for n' in neighbors(node):
    t ← search(n', g + cost(node, n'), bound)
    if t = FOUND:  return FOUND
    if t < min:    min ← t
  return min

DFS con f-bound. Quando incontri un nodo con f > bound, lo tagli e restituisci il suo f come candidato per il prossimo bound. Se l’intera DFS finisce senza trovare goal, alza bound al minimo f scartato e ricomincia. Memoria O(bd), come DFS. Tempo: rivisita molti nodi, ma per problemi tipo 15-puzzle e Rubik è praticabile mentre A* esaurisce memoria. Korf 1985 mostra empiricamente che IDA* risolve istanze di 15-puzzle che A* non riesce a finire.

D*-Lite per ambienti dinamici

Quando il robot scopre ostacoli mentre si muove — un masso che non era sulla mappa, un corridoio chiuso — A* andrebbe ricalcolato da capo. D*-Lite (Koenig-Likhachev 2002) ricalcola incrementalmente solo i nodi influenzati dal cambiamento, riusando i g già calcolati. Fuori scope il dettaglio; importante sapere che esiste e perché.

Esempi

Esempio 1 — 8-puzzle a mano, due passi

Stato iniziale 3x3 (0 = casella vuota):

1 2 3
4 0 6
7 5 8

Goal:

1 2 3
4 5 6
7 8 0

Calcolo h_manhattan dello stato iniziale: tessera 5 è in (2, 1), goal (1, 1), distanza 1. Tessera 8 è in (2, 2), goal (2, 1), distanza 1. Tutte le altre tessere sono già a posto. h = 2. g = 0. f = 2.

Espansione del nodo iniziale. La casella vuota è in (1, 1); può scambiarsi con quattro vicini.

Mossa	Nuovo stato (sintesi)	g	h	f
up (sposta 2 in (1,1), vuoto sale)	1 0 3 / 4 2 6 / 7 5 8	1	4	5
down (sposta 5 in (1,1))	1 2 3 / 4 5 6 / 7 0 8	1	1	2
left (sposta 4 in (1,1))	1 2 3 / 0 4 6 / 7 5 8	1	3	4
right (sposta 6 in (1,1))	1 2 3 / 4 6 0 / 7 5 8	1	3	4

A* sceglie “down” (f = 2). Nuovo stato:

1 2 3
4 5 6
7 0 8

Solo la tessera 8 è fuori posto, h = 1. g = 1. f = 2.

Espansione del nodo “down”. La casella vuota è in (2, 1); vicini:

• up (riporta 5 indietro, ma 5 è già in closed con g migliore — scartato).
• down: out of grid.
• left (sposta 7 a destra): 1 2 3 / 4 5 6 / 0 7 8 — h = 2 (7 e 8 fuori posto), g = 2, f = 4.
• right (sposta 8 a sinistra): 1 2 3 / 4 5 6 / 7 8 0 — è il goal. h = 0, g = 2, f = 2.

A* trova goal in due espansioni e due passi di soluzione, espandendo in totale 5 nodi (lo stato iniziale, “down”, e i suoi 4 successori — ma tre di questi non vengono espansi perché si esce subito dal loop). Per confronto: BFS uninformed avrebbe espanso tutti i 4 successori al livello 1 e tutti i 12 al livello 2 prima di toccare il goal — circa 16 espansioni. Su problemi grandi questo rapporto esplode esponenzialmente.

Esempio 2 — gridworld 10x10 in Python

Una griglia 10x10 con alcuni ostacoli, partenza in alto a sinistra, goal in basso a destra. Mosse 4-direzioni a costo 1. Heuristic Manhattan.

import heapq

def astar(grid, start, goal):
    """grid: lista di liste, 0 = libero, 1 = ostacolo. start, goal: (r, c)."""
    rows, cols = len(grid), len(grid[0])

    def h(p):
        return abs(p[0] - goal[0]) + abs(p[1] - goal[1])

    def neighbors(p):
        r, c = p
        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:
                yield (nr, nc)

    open_heap = []
    heapq.heappush(open_heap, (h(start), 0, start))   # (f, g, node)
    g_score = {start: 0}
    parent  = {start: None}
    closed  = set()
    expanded = 0

    while open_heap:
        f, g, n = heapq.heappop(open_heap)
        if n in closed:                # entry stale: scarta
            continue
        if n == goal:
            # ricostruisci il cammino
            path = []
            while n is not None:
                path.append(n)
                n = parent[n]
            return list(reversed(path)), expanded
        closed.add(n)
        expanded += 1
        for n2 in neighbors(n):
            tentative_g = g + 1
            if n2 in closed and tentative_g >= g_score.get(n2, float('inf')):
                continue
            if tentative_g < g_score.get(n2, float('inf')):
                g_score[n2] = tentative_g
                parent[n2]  = n
                heapq.heappush(open_heap, (tentative_g + h(n2), tentative_g, n2))
    return None, expanded


# esempio d'uso
grid = [[0]*10 for _ in range(10)]
for r in range(2, 8):
    grid[r][5] = 1                    # un muro verticale con un varco in alto
path, expanded = astar(grid, (0, 0), (9, 9))
print(f"path length: {len(path)}, nodes expanded: {expanded}")
# tipicamente ~30 nodi espansi vs ~80 con Dijkstra (h=0) sulla stessa griglia

Cambiando h con lambda p: 0 il codice diventa Dijkstra. Sullo stesso input l’algoritmo trova la stessa soluzione ottima ma espande circa il doppio o triplo dei nodi, perché esplora simmetricamente in tutte le direzioni invece di puntare al goal.

Esempio 3 — Tree-of-Thoughts come A*-with-LLM-heuristic

Un task di ragionamento multi-step: un LLM deve risolvere un problema (es. “Game of 24”: dati quattro numeri, combinarli con +, -, *, / per ottenere 24). Yao 2023 propone questo schema.

ToT-Search(start_state, goal_test, generator_LLM, evaluator_LLM, k):
  open ← priority_queue()
  open.push(start_state, priority = -evaluator_LLM(start_state))
  while open non vuota:
    s ← open.pop_min()             # stato con score predetto più alto
    if goal_test(s): return s
    candidates ← generator_LLM(s, n=k)   # genera k thoughts successori
    for c in candidates:
      score ← evaluator_LLM(c)     # valutazione in [0, 1]
      open.push(c, priority = depth(c) - lambda * score)

La priorità è una combinazione fra profondità (analoga a g) e score dell’evaluator (analoga a -h, perché un buon stato ha score alto, costo residuo basso). È l’identica struttura di A* — frontiera ordinata su f = g + h — con due differenze chiave.

Prima differenza, di natura formale: l’evaluator LLM non è admissible. Un LLM-judge può essere troppo ottimista (sovrastimare uno stato) o troppo pessimista. Quando sovrastima, la priorità f attuale di un cammino sub-ottimo può essere più bassa di quella del cammino ottimo, e A* diventa weighted A* “all’incognito”: perde la garanzia di ottimalità.

Seconda differenza, di natura pratica: ogni espansione costa una chiamata API. Il branching factor effettivo è k (i k thoughts generati), e ogni nodo richiede k + 1 chiamate (k al generator, 1 all’evaluator). Il bilancio costo/qualità è dominato da queste chiamate, non dalla complessità algoritmica. Si traduce in beam search con beam k piccolo (Yao usa k = 5 nel paper), oppure in DFS con backtracking.

ANALOGIA marcata: ToT-with-priority è A*-with-learned-heuristic. La struttura è identica, le garanzie sono diverse, il costo computazionale è dominato da fattori esterni alla teoria classica. Capire ToT senza aver capito A* è possibile ma molto più lento; capirlo dopo aver capito A* è gratis.

flowchart LR
  S[Stato corrente s] --> G[Generator LLM]
  G --> T[k thoughts c_1..c_k]
  T --> E[Evaluator LLM]
  E --> P[Score in 0..1]
  P --> Q[Priority queue<br/>f = depth - λ·score]
  Q --> X[Pop min: stato successivo]
  X --> S
  X --> GOAL{Goal test}
  GOAL -->|sì| OUT[Restituisci path]
  GOAL -->|no| S

Figura 6 — Tree of Thoughts come A con euristica LLM — generator produce k thoughts, evaluator LLM li score, priority queue ordina per f = depth - λ·score, espansione selettiva fino al goal*

Applicazioni pratiche

Pathfinding in videogiochi. Standard industriale dagli anni ‘80. NPC navigation, RTS unit movement, navmesh, jump point search. La maggioranza dei game engine ha una variante di A* nel core. Heuristic = distanza octile o euclidean, typed grid o navmesh come grafo.

Robotics motion planning. Per robot mobili in ambienti noti, A* su grid o roadmap. Per ambienti dinamici, D*-Lite (Mars rovers Spirit, Opportunity, Curiosity hanno tutti varianti di D* nel software di navigazione). Per spazi ad alta dimensionalità (manipolatori), tecniche probabilistiche come RRT* — fuori dalla famiglia A* classica ma simili nello spirito.

Routing GPS e logistica. Su scala continentale i grafi sono troppo grandi per A* classico. Si usano tecniche industriali come Contraction Hierarchies (Geisberger 2008) e ALT (Goldberg-Harrelson 2005, l’acronimo sta per A*, Landmarks, Triangle inequality), entrambe varianti di A* con preprocessing pesante. Google Maps, OpenStreetMap routers, navigatori veicolari le usano.

LLM agent multi-step planning. Un agente che pianifica una sequenza di azioni — ricerca su web, lettura file, scrittura, verifica — può essere visto come ricerca in un grafo di stati di task. Le varianti recenti aggiungono uno scoring (LLM-judge, reward model, success rate predetto) e ricadono su A*-with-learned-heuristic. È ANALOGIA non equivalenza: l’heuristic non è admissible, le garanzie classiche cadono.

Code agent: navigazione del repository. Trovare il file giusto in cui modificare, dato un task. Stati = file path o segmenti di codice. Successori = aprire / cercare / leggere. Heuristic = similarità semantica fra task e contenuto, calcolata via embedding. Best-first guidato da embedding è un A* informale; “Cursor”, “Aider” e affini lo implementano sotto qualche maschera.

Tree-of-Thoughts e reasoning. Già visto in Esempio 3. ToT con priority è A*-with-LLM-heuristic. Adatto a problemi con goal ben definito e thought tree non troppo profondo.

Reverse engineering e disassembly. Trovare un cammino nel control-flow graph di un binario, da entry point a istruzione target. A* con h = numero di basic block tra n e target nella vista statica. Usato in tool come IDA Pro, Binary Ninja, angr.

Automated theorem proving. Provare un teorema = trovare un cammino da assiomi a teorema in un grafo di formule. Heuristic = distanza euristica fra formula corrente e target (numero di simboli, profondità sintattica, ecc.). E2/Vampire/Z3 usano varianti molto raffinate, ma l’ossatura concettuale è A*.

Dove si rompe

A* è solido nelle sue condizioni, ma le condizioni sono strette. Otto situazioni in cui rompe.

Heuristic non admissible. L’esempio canonico: euristica overshoot in 8-puzzle (es. somma dei quadrati delle distanze). Sopravvaluta sistematicamente, A* cerca prima cammini “che sembrano corti” e può scartare il vero ottimo. La soluzione restituita non è ottima, e in casi patologici A* può non trovarla affatto.

Heuristic costosa da calcolare. Se h(n) richiede tempo paragonabile a risolvere il sotto-problema (es. risolvere un sotto-puzzle), il guadagno in nodi espansi è annullato dal tempo per nodo. Pattern databases (Culberson-Schaeffer 1998) lavorano qui: pre-computi h offline su sotto-problemi, in runtime è una tabella lookup. Fuori da casi così curati, una heuristic costosa è un boomerang.

Branching factor enorme. Se ogni nodo ha 50 successori e profondità della soluzione è 20, la frontiera cresce a 50^20 prima di trovare il goal. In LLM Tree-of-Thoughts ogni espansione costa una chiamata API: non puoi permetterti k > 5 in pratica. A* tradizionale è impraticabile, si va su IDA* (memoria limitata), beam search (qualità sacrificata per velocità), o algoritmi specializzati.

Memoria. A* mantiene tutta la frontiera + closed in RAM. Su 15-puzzle è già al limite (~10^13 stati raggiungibili), su Rubik’s cube (4 · 10^19 stati) impossibile. IDA* è la risposta classica. Per problemi ancora più grandi, memory-bounded A* (SMA*, RBFS) rinunciano a frammenti di closed quando la memoria si esaurisce.

Ambienti dinamici. A* assume che il grafo sia statico durante la ricerca. Quando il robot scopre ostacoli muovendosi, ricalcolare A* da zero dopo ogni scoperta è proibitivo. D*-Lite ricalcola incrementalmente; Lifelong Planning A* generalizza l’idea.

Learned heuristic da rete neurale. Negli ultimi anni si sono provate heuristic apprese: una rete neurale prende in input lo stato e predice h. Trade-off: la rete può essere molto informata su distribuzioni viste, ma non è admissible per costruzione. Conseguenza: ottimalità persa, comportamento non riproducibile fra training run, possibile sovrafitting su benchmark. Lavori recenti vincolano la rete a produrre lower bound (heuristic monotone-by-construction), ma è ricerca aperta.

Goodhart su heuristic LLM. Caso particolare del precedente, ma con un twist: in Tree-of-Thoughts il generator e l’evaluator possono essere lo stesso LLM. Se valuti gli stati con lo stesso modello che li genera, il sistema massimizza il giudizio invece del task. È un caso di legge di Goodhart: “quando una misura diventa un target, smette di essere una buona misura”. Si mitiga usando evaluator diversi, o ground-truth oracoli quando disponibili.

Concorrenza. In agent system multi-thread la priority queue non è più totalmente ordinata: due thread possono pop quasi-contemporaneamente nodi con f vicini, e l’ordine effettivo di espansione dipende da dettagli dello scheduler. La garanzia di ottimalità di A* assume estrazione deterministica del minimo. Nei sistemi distribuiti (es. agent swarm) si recupera con priority queue concorrenti, ma il costo di sincronizzazione spesso annulla il guadagno in parallelismo.

Uncertainty nei costi. A* assume costi deterministici e noti. Per ambienti stocastici — costi che sono variabili aleatorie, transizioni con probabilità — si va sui Markov Decision Process e su algoritmi tipo value iteration. Vedi markov-decision-process e value-iteration-policy-iteration. Esiste un’ANALOGIA forte: la value function V(s) di un MDP è la versione stocastica di -h*(n), il costo-residuo-atteso. Heuristic in A* e value function in RL stimano lo stesso oggetto in mondi diversi (deterministico vs stocastico), e gli algoritmi che la apprendono (Q-learning, policy gradient) sono parenti lontani della “heuristic learning” in A*. Marcare con cura: ANALOGIA didattica forte, NON equivalenza formale completa. Le condizioni di ammissibilità in A* e di compatibilità reward-shaping in RL (Ng-Harada-Russell 1999, potential-based shaping) sono strutturalmente analoghe — entrambe richiedono che la stima preservi la struttura ottima — ma le forme specifiche differiscono.

Collegamenti

• search-bfs-dfs — la base uninformed. Lo skeleton è invariante; A* cambia solo la policy di selezione della frontiera.
• complessita-big-o — analisi di complessità di A*: tempo O(b^d) nel caso peggiore, ma esponenzialmente migliore in pratica con heuristic informata; spazio O(b^d), problema cardine.
• minimax — minimax esplora alberi di gioco con un meccanismo simile a DFS-con-bound, e l’alpha-beta pruning è ANALOGIA stretta della potatura f > bound di IDA*.
• markov-decision-process — il setting stocastico in cui l’ANALOGIA “h ↔ -V” diventa esplicita.
• equazione-bellman — la consistency h(n) <= c(n, n’) + h(n’) è la forma deterministica della condizione di Bellman sulla value function.
• value-iteration-policy-iteration — algoritmi che apprendono V iterativamente; la struttura iterativa è parente di IDA* con bound crescenti.
• q-learning — Q(s, a) come heuristic learned; ANALOGIA con A*-with-learned-heuristic.
• policy-gradient — un secondo modo di apprendere il “cosa fare dopo”, ortogonale all’apprendere V/h.
• monte-carlo-tree-search (in preparazione) — esplora alberi con UCB1 invece che con f = g + h; sostituisce determinismo con campionamento.
• search-ida-star (in preparazione) — il dettaglio specifico su IDA*, qui solo accennato.
• llm-agent-planning (in preparazione) — ToT, ReAct, Reflexion: agent che usano LLM come generator e/o evaluator nello stile A*-informale.

Per andare oltre

• Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach, 4a ed., Pearson. Capitolo 3 e 4 sulla ricerca, presentazione standard di A*, GBFS, weighted A*, IDA*. Il riferimento didattico più diffuso al mondo.
• Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley. Il trattato canonico sulle euristiche, formalizza dominanza e well-informed-ness.
• Hart, P. E., Nilsson, N. J., Raphael, B. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”. IEEE Transactions on Systems Science and Cybernetics, SSC-4(2), 100-107. Il paper originale, leggibile in un’ora, indispensabile per vedere come Hart-Nilsson-Raphael formularono la cosa.
• Korf, R. E. (1985). “Depth-first iterative-deepening: An optimal admissible tree search”. Artificial Intelligence, 27(1), 97-109. IDA* in originale, con esperimenti su 15-puzzle.
• Yao, S. et al. (2023). “Tree of Thoughts: Deliberate Problem Solving with Large Language Models”. arXiv:2305.10601. Per chi vuole vedere come BFS/DFS/A*-style si trasferiscano sull’albero di pensieri di un LLM.