IDA*: la ricerca informata che non chiede memoria

A* trova il path ottimo ma esige memoria proporzionale al numero di nodi visti. IDA* lo trova con la stessa qualità e memoria lineare nella profondità, al prezzo di rivedere alcuni nodi più volte.

Perché questo capitolo

A* (visto in search-a-star) è lo standard per ricerca informata su grafi: ottimo, completo, sorprendentemente efficiente in pratica. Ha un solo difetto, ma è grosso: tiene in RAM la frontiera (open list) e l’insieme dei nodi già espansi (closed list). Su problemi seri queste due strutture esplodono. Il 15-puzzle ha circa $10^{13}$ stati raggiungibili; il cubo di Rubik 3x3 ne ha $4{,}3 \times 10^{19}$. Nessuna macchina ragionevole tiene quei numeri in memoria. Eppure entrambi i problemi sono stati risolti ottimamente da decenni. Il responsabile si chiama IDA*.

L’idea è una furbata che tradisce la semplicità di chi cerca davvero soluzioni: rifare DFS più volte, con un budget di costo crescente, partendo dal minimo. Si paga in tempo (rivisitazione) ciò che si risparmia in spazio (niente closed list). E si paga poco, perché l’ultima iterazione domina asintoticamente le precedenti.

Capire IDA* serve per tre ragioni concrete. Primo, è lo strumento di scelta quando lo spazio è grande e la memoria stretta: chess engine, Rubik solver ottimi, planner classici. Secondo, lo schema “iterative deepening” si trova ovunque dove serve allocare un budget: motori di scacchi (iterative-deepening alpha-beta), agent LLM (Tree-of-Thoughts con budget crescente), proof search nei theorem prover. Terzo, espone un trade-off importante fra spazio e tempo che ricorre in ogni algoritmo serio di search: memorizzare i sotto-risultati, oppure rifarli.

Contesto

Richard Korf (n. 1956), informatico AI a UCLA, pubblica nel 1985 Depth-first iterative-deepening: An optimal admissible tree search su Artificial Intelligence 27(1):97-109. Lo stesso paper introduce due algoritmi: IDDFS (iterative-deepening DFS, già visto in search-bfs-dfs) come variante uninformed, e IDA* come variante informata che usa una heuristic ammissibile. Il manoscritto dimostra ottimalità, completezza e mostra empiricamente che IDA* risolve istanze del 15-puzzle che A* non finisce per esaurimento memoria.

Korf torna sul tema nel 1993 con Linear-space best-first search (Artificial Intelligence 62(1):41-78), dove introduce RBFS (Recursive Best-First Search): una variante a memoria lineare che evita di rifare DFS da zero, riprocessando solo i sotto-alberi quando il valore $f$ del miglior alternativo cresce. RBFS si comporta meglio di IDA* su grafi a costo reale; peggio sui puzzle a costo unitario.

Nel 1992 Stuart Russell (n. 1962, britannico, allora a UC Berkeley, oggi noto per Artificial Intelligence: A Modern Approach con Norvig) presenta a ECAI 1992 Efficient memory-bounded search methods introducendo SMA*: A* che, quando la memoria si riempie, scarta dalla frontiera il nodo con $f$ più alto e propaga il suo $f$-value al genitore. Trade-off complementare a IDA*: usa tutta la memoria disponibile, droppa solo se costretto.

Joseph Culberson e Jonathan Schaeffer, informatici alla University of Alberta, pubblicano nel 1998 Pattern Databases su Computational Intelligence 14(3):318-334. La pattern database (PDB) è una tabella precalcolata di costi ottimi per sotto-problemi: ignori parte dello stato, calcoli all’indietro dal goal con BFS, memorizzi. La heuristic risultante è ammissibile e tipicamente molto più tight di Manhattan distance. PDB + IDA* è la combinazione che permette a Korf nel 1997 (Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases, AAAI 1997) di risolvere ottimamente istanze del cubo di Rubik 3x3.

Il grafo concettuale, esplicitamente:

• IDDFS sta a BFS come IDA* sta ad A* (analogia stretta sullo schema, equivalenza sull’output con bound che cresce).
• IDA* sta ad A* come DFS-bounded sta a best-first: lo skeleton è lo stesso, cambia la struttura dati e quindi la memoria.
• RBFS, SMA*, IDA*-CR sono tutte risposte al medesimo problema: fare best-first senza una frontiera enorme.
• Pattern database è ortogonale: migliora $h$, indipendentemente dall’algoritmo che la usa.

Differenziazione esplicita rispetto ai capitoli vicini. In search-bfs-dfs IDDFS appare come variante uninformed di DFS depth-limited: bound = profondità, niente heuristic. In search-a-star IDA* è menzionato come “soluzione classica al problema memoria di A*”, senza dettagli. Qui IDA* è il protagonista: pseudocodice riga per riga, analisi di complessità, casi in cui batte A*, casi in cui perde, estensioni.

L’intuizione

Due angoli distinti, prima del formalismo.

Angolo 1: DFS che si rifà con un budget crescente

DFS non è ottima: prende il primo path che trova, anche se sub-ottimo. Si possono mettere paletti: “DFS, ma non oltre profondità $d$”. Se non trovi il goal, alzi $d$. È IDDFS, e già lo conosciamo: tempo $O(b^d)$, spazio $O(bd)$, ottimalità con costi unitari.

Cambiamo il paletto. Invece di “non oltre profondità $d$”, diciamo “non oltre f-cost = $b$”. Dove $f(n) = g(n) + h(n)$, come in A*: $g$ è il costo accumulato, $h$ è la stima del costo restante. La DFS espande solo nodi con $f \le b$. Quando ne incontra uno con $f > b$, lo scarta e ricorda il suo $f$. Se l’intera DFS finisce senza goal, il nuovo $b$ è il minimo $f$ scartato. Si rifà.

Questa è IDA*. Le iterazioni precedenti sembrano spreco — le rifai sempre dall’inizio. Ma non lo sono: nel caso peggiore (tree con costi uniformi) il lavoro totale è dominato dall’ultima iterazione, esattamente come per IDDFS. Si paga al massimo un fattore costante $b/(b-1)$ sul numero di nodi espansi; per $b=10$ è 1.11x, per $b=100$ è 1.01x. Trascurabile in pratica.

Si potrebbe obiettare: “rifare DFS sembra spreco”. L’obiezione è naturale e va affrontata di petto. Considera un albero binario di profondità 20 con $2^{20} \approx 10^6$ foglie. L’iterazione 20 espande $2^{20}$ nodi. L’iterazione 19 ne espande $2^{19}$. L’iterazione 18, $2^{18}$. Sommando tutte le iterazioni precedenti: $2^{20} + 2^{19} + \dots + 2^0 = 2^{21} - 1 \approx 2 \times 10^6$. Solo il doppio dell’iterazione finale, non 20 volte. Le iterazioni piccole sono piccole; pesano poco asintoticamente. L’overhead converge a un fattore costante che dipende solo dal branching factor.

Angolo 2: A* in cui la frontiera diventa lo stack

A* tiene una priority queue (open list) e un hash table (closed list). La memoria è dominata dalla frontiera, che cresce esponenzialmente con la profondità. IDA* sostituisce queste due strutture con: lo stack della DFS, una variabile threshold e una variabile min_excess. Tre numeri e una pila profonda al massimo $bd$.

Vista così, IDA* è A* costretto a vivere nello spazio di una funzione ricorsiva. Non può ricordarsi di aver visto un nodo: rivisita. Non può prendere il prossimo nodo in ordine globale: prende il prossimo figlio. Ma compensa con un budget crescente: se a budget $b$ non trova il goal, lo aumenta. Così garantisce di esplorare in ordine di f-cost crescente, come A*, senza pagare il costo di tenerlo in memoria.

La differenza pratica è enorme: A* su 15-puzzle può esaurire RAM dopo qualche minuto, IDA* lavora per ore con un megabyte di stack. Per problemi grandi non è questione di velocità, è questione di feasibility.

La meccanica

Pseudocodice riga per riga

IDA_STAR(start, h, is_goal, expand):
  bound <- h(start)
  path  <- [start]
  loop:
    t <- DFS_BOUNDED(path, g=0, bound, h, is_goal, expand)
    if t == FOUND:        return path
    if t == infinity:     return FAILURE   # nessuna soluzione
    bound <- t

DFS_BOUNDED(path, g, bound, h, is_goal, expand):
  node <- path.last()
  f    <- g + h(node)
  if f > bound:           return f          # taglio, restituisci f per il prossimo bound
  if is_goal(node):       return FOUND
  min_excess <- infinity
  for next, cost in expand(node):
    if next in path:      continue          # path checking, NON closed list
    path.push(next)
    t <- DFS_BOUNDED(path, g + cost, bound, h, is_goal, expand)
    if t == FOUND:        return FOUND
    if t < min_excess:    min_excess <- t
    path.pop()
  return min_excess

flowchart TD
  A[Start: state, h, expand] --> B[bound = h(start)]
  B --> C[DFS_BOUNDED con bound]
  C --> D{Goal trovato?}
  D -- sì --> E[Restituisci path]
  D -- no --> F{min_excess == ∞?}
  F -- sì --> G[Restituisci FAILURE]
  F -- no --> H[bound = min_excess]
  H --> C

Figura 6 — IDA control flow (mermaid) — bound iniziale, DFS bounded, goal check, failure check, aggiornamento bound al min_excess*

Riga per riga.

• $bound \leftarrow h(start)$: il bound iniziale è la stima euristica del goal dallo start. Con $h$ ammissibile è il minimo possibile. Non si parte da zero perché la prima iterazione finirebbe subito senza espandere niente di utile.
• loop: si rifà la DFS con bound crescenti finché si trova il goal o si esaurisce lo spazio (min_excess = infinito).
• DFS_BOUNDED: ritorna FOUND se trova il goal, altrimenti il minimo $f$ eccesso visto in questa chiamata.
• f > bound: il taglio. Non si espande, ma si restituisce $f$ così il chiamante può calcolare il prossimo bound.
• next in path: path checking. Si evita di tornare sui propri passi all’interno del path corrente, per non avvitarsi su un ciclo. Non è una closed list: si dimentica tutto ciò che è fuori dallo stack corrente.
• min_excess: il minimo $f$ superato in questa iterazione. Sarà il prossimo bound.
• path.pop(): ritorno al genitore. Lo stack ha al massimo profondità pari alla profondità della soluzione.

Aggiornamento del threshold: il punto sottile

Il prossimo bound è il minimo $f$ effettivamente scartato in questa iterazione, non un incremento fisso. È il dettaglio che rende IDA* praticabile: salti al successivo valore di $f$ presente nello spazio, non perdi tempo in iterazioni con bound intermedi che non aggiungono nodi. Se incrementassi di 1 (o di un quantum scelto a priori), in regime di costi reali densi faresti decine o centinaia di iterazioni vuote.

Complessità

Spazio. $O(bd)$ dove $b$ è il branching factor effettivo e $d$ la profondità della soluzione. Solo lo stack della DFS corrente. Confronto con A*: $O(b^d)$. Per il 15-puzzle ($d \approx 50$, $b \approx 3$) IDA* sta in qualche kilobyte; A* esige terabyte se non si rinuncia a tenere closed list completa.

Tempo. $O(b^d)$ come A*. Nel caso peggiore tree con costi uniformi e $h$ uniforme, il numero di nodi espansi totali su tutte le iterazioni è:

$$N_{\text{tot}} \approx N_d \cdot \left(1 + \frac{1}{c} + \frac{1}{c^2} + \dots\right) = N_d \cdot \frac{c}{c-1}$$

dove $c$ è il rapporto fra il numero di nodi all’iterazione $k$ e all’iterazione $k-1$. Per branching uniforme $c \approx b$. L’overhead asintotico è $b/(b-1)$: trascurabile per $b$ grande. Su tree con costi reali densi (molti valori $f$ distinti), ogni iterazione aggiunge pochi nodi e l’overhead esplode: in casi patologici IDA* può fare ordini di grandezza più lavoro di A*. RBFS si comporta meglio in quel regime.

Ottimalità

TEOREMA (Korf 1985). Se $h$ è ammissibile ($h(n) \le h^*(n)$ per ogni $n$, dove $h^*$ è il costo ottimo da $n$ al goal), IDA* trova un goal con costo ottimo.

Dimostrazione (sketch). Sia $C^*$ il costo ottimo. Mostriamo che IDA* termina alla prima iterazione con bound $\ge C^*$ trovando un goal di costo $C^*$. Per induzione sui bound visti: ogni bound è il minimo $f$ scartato all’iterazione precedente. Ammissibilità implica $f(n) \le C^*$ per ogni $n$ su un path ottimo. Quindi all’iterazione con bound $= C^*$, tutti i nodi di un path ottimo soddisfano $f \le \text{bound}$; la DFS li raggiunge. Il primo goal trovato in quella iterazione ha costo $\le C^*$; per ammissibilità è esattamente $C^*$.

La condizione richiesta è ammissibilità, non consistency (la “monotonicity” che A* usa per avere ottimalità anche con riapertura dei nodi). IDA* non riapre nulla e non ha closed list; questo cancella il problema della consistency, ma introduce il problema della rivisitazione su grafi non-tree.

Estensioni in pillole

RBFS (Korf 1993). Memoria lineare ma niente “rifai da capo”. Esplora ricorsivamente il miglior figlio finché il suo $f$-value sale sopra l’alternativa migliore; allora torna indietro e propaga il valore aggiornato. Migliore di IDA* sui grafi a costo reale (poche iterazioni più lunghe); peggiore sui puzzle integer (overhead di ricorsione).

SMA* (Russell 1992). A* che usa tutta la RAM disponibile, scartando dalla frontiera il nodo con $f$ più alto quando la memoria è piena. Propaga $f$ scartato al genitore: se quel ramo torna a essere il più promettente, lo riespande. Trade-off opposto a IDA*: paga più memoria, paga meno rivisitazione.

IDA*-CR (Sarkar et al. 1991). Controlled re-expansion: invece di portare bound al minimo $f$ scartato, lo porta a un valore stimato per espandere un numero target di nodi nella prossima iterazione. Utile su f-cost continuo dove min_excess sarebbe infinitesimale.

Bidirectional IDA*. IDA* simultaneo da start e da goal; quando i fronti si incontrano, si ha la soluzione. Riduzione esponenziale nei casi favorevoli; complica la gestione del meeting point.

Transposition table. Variante pratica: aggiungi a IDA* una tabella di dimensione fissa (es. 100 MB) che memorizza i nodi più recentemente espansi e il loro $f$-value. Quando si rivisita uno stato già nella tabella, si riusa il valore invece di ricalcolarlo. Non ripristina l’ottimalità asintotica di A*, ma riduce di un ordine di grandezza la rivisitazione su grafi con molte transposizioni. È lo schema standard nei chess engine: la transposition table di Stockfish è centinaia di MB.

Variante storica: depth-bounded planners

Prima di Korf 1985, il pattern “DFS con bound crescente” esisteva nel mondo del planning simbolico. Earl Sacerdoti nel 1974 con NOAH e poi David Wilkins con SIPE (1984) usavano forme di iterative-deepening su piani gerarchici, con bound che era il numero di azioni piuttosto che f-cost. Korf 1985 unifica e formalizza: IDDFS come variante uninformed, IDA* come variante informata. La filiazione storica è documentata nel paper originale, che cita esplicitamente Sacerdoti e il proprio precedente lavoro su 8-puzzle con DFS depth-bounded come precursori dell’idea.

Questa è una FILIAZIONE, non un’analogia: c’è lineage diretto dal planning gerarchico anni ‘70 a IDDFS/IDA* del 1985.

Esempi

Esempio 1: piccolo grafo numerico

Cinque nodi, costi e heuristic dichiarati:

nodi: A, B, C, D, E   (E e' il goal)
archi:
  A -> B, costo 1
  A -> C, costo 4
  B -> D, costo 2
  C -> E, costo 1
  D -> E, costo 3
heuristic ammissibile:
  h(A)=3, h(B)=2, h(C)=1, h(D)=1, h(E)=0

Il path ottimo è A -> C -> E con costo 5. (A -> B -> D -> E è costo 6.)

Iterazione 1, bound = h(A) = 3.

• Espandi A: $f(A) = 0 + 3 = 3$, OK.
• Provo B: $f(B) = 1 + 2 = 3$, OK.
• Provo D da B: $f(D) = 3 + 1 = 4 > 3$, scarto, registro 4.
• Provo C da A: $f(C) = 4 + 1 = 5 > 3$, scarto, registro 5.
• min_excess = 4. Bound nuovo = 4.

Iterazione 2, bound = 4.

• A ($f=3$), B ($f=3$), D ($f=4$), provo E da D: $f(E) = 6 + 0 = 6 > 4$, scarto, registro 6.
• C ($f=5 > 4$, scarto, registro 5).
• min_excess = 5. Bound nuovo = 5.

Iterazione 3, bound = 5.

• A ($f=3$), B ($f=3$), D ($f=4$), E da D ($f=6 > 5$, scarto), torno su.
• C ($f=5$), E da C ($f = 4+1+0 = 5 = \text{bound}$, OK è il goal). FOUND.

Path: A -> C -> E, costo 5. Ottimo.

Tre iterazioni, ognuna espande qualche nodo in più della precedente. La rivisitazione di A, B, D nelle tre iterazioni è il costo che IDA* paga in cambio della memoria $O(bd)$.

Esempio 2: 8-puzzle in Python

Risolvi una configurazione del 8-puzzle (3x3) usando IDA* con Manhattan heuristic.

GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)

# adjacency su griglia 3x3: index -> indici vicini
ADJ = {
    0: (1, 3),       1: (0, 2, 4),    2: (1, 5),
    3: (0, 4, 6),    4: (1, 3, 5, 7), 5: (2, 4, 8),
    6: (3, 7),       7: (4, 6, 8),    8: (5, 7),
}

def manhattan(state, goal=GOAL):
    h = 0
    for i, t in enumerate(state):
        if t == 0:
            continue
        gi = goal.index(t)
        h += abs(i // 3 - gi // 3) + abs(i % 3 - gi % 3)
    return h

def neighbors(state):
    z = state.index(0)
    for nz in ADJ[z]:
        s = list(state)
        s[z], s[nz] = s[nz], s[z]
        yield tuple(s)

def ida_star(start):
    bound = manhattan(start)
    path = [start]
    while True:
        t = _dfs(path, 0, bound)
        if t == "FOUND":
            return path
        if t == float("inf"):
            return None
        bound = t

def _dfs(path, g, bound):
    node = path[-1]
    f = g + manhattan(node)
    if f > bound:
        return f
    if node == GOAL:
        return "FOUND"
    min_t = float("inf")
    for s in neighbors(node):
        if s in path:        # path checking
            continue
        path.append(s)
        t = _dfs(path, g + 1, bound)
        if t == "FOUND":
            return "FOUND"
        if t < min_t:
            min_t = t
        path.pop()
    return min_t

# test
START = (1, 2, 3, 4, 0, 5, 7, 8, 6)  # 5 mosse dal goal
solution = ida_star(START)
print(f"steps: {len(solution)-1}")

L’esecuzione su questa istanza termina in millisecondi e produce 5 mosse: l’ottimo. Il path checking (if s in path) evita di girare in tondo all’interno della stessa DFS, ma non memorizza nulla globalmente: stati visti in iterazioni precedenti vengono rivisitati. Su istanze più difficili (profondità 20-30 mosse) si vede l’overhead della rivisitazione, ma la memoria resta lineare.

Il limite di Manhattan: per il 15-puzzle (4x4, $d=50\text{-}80$) Manhattan diventa troppo lasca e IDA* esplode. Si passa a pattern database, che restano ammissibili e sono molto più tight: vedi pattern-databases (in preparazione).

Una numerologia rapida sul 15-puzzle, perché aiuta a tarare l’aspettativa: con Manhattan distance, IDA* genera mediamente $\sim 10^9$ nodi su istanze di profondità 50, qualche minuto su CPU moderna. Con PDB 7-8 (Korf-Felner 2002) si scende a $\sim 10^6$ nodi, secondi. Lo stesso algoritmo, stessa garanzia di ottimalità: cambia solo $h$. Su 24-puzzle (5x5, $d \sim 100$) Manhattan è impraticabile; PDB disjoint risolvono ottimamente in giorni di calcolo. Il messaggio operativo: IDA* è solo metà della storia, l’altra metà è la qualità di $h$.

Pattern Databases come compagno naturale di IDA*

Le PDB meritano una vista a sé. Idea: prendi un sotto-problema (es. “muovi solo 7 caselle delle 15, ignora le altre”), risolvilo all’indietro dal goal con BFS uniform-cost (memorizzando la distanza per ogni configurazione delle 7 caselle), salva la tabella su disco. Al runtime, $h(\text{stato})$ è un lookup nella tabella, $O(1)$.

Tre proprietà.

1. Ammissibilità: il sotto-problema costa al massimo quanto il problema completo (rilassamento). Quindi $h$ da PDB è ammissibile.
2. Tightness: per i puzzle, $h$ da PDB è tipicamente 2-3 volte più grande di Manhattan, e Manhattan è già il punto di riferimento “ragionevole”.
3. Disjoint additivity: se due PDB coprono insiemi disgiunti di caselle, le loro $h$ si sommano e restano ammissibili. Korf-Felner 2002 sfruttano questo per il 24-puzzle.

Costo: tempo di precomputo (ore-giorni) e spazio su disco (10-500 MB). Trade-off vincente quando il problema viene risolto migliaia di volte (esempio: solver di Rubik distribuito a milioni di utenti).

Esempio 3: chess engine con iterative-deepening alpha-beta

Scenario reale: il cuore di un chess engine moderno (Stockfish, Leela in modalità search, Komodo) usa iterative deepening, non IDA* in senso stretto. EQUIVALENZA argomentabile sul pattern, non sull’algoritmo: il bound è la depth e l’algoritmo interno è alpha-beta minimax.

def search_best_move(root, time_budget_ms):
    best_move = None
    pv = []  # principal variation: sequenza di mosse migliori dell'iterazione precedente
    start = now_ms()
    depth = 1
    while now_ms() - start < time_budget_ms:
        score, new_pv = alpha_beta(
            node=root,
            depth=depth,
            alpha=-INF,
            beta=+INF,
            move_order_hint=pv,    # prova prima la PV
        )
        if not timed_out():
            best_move = new_pv[0]
            pv = new_pv
        depth += 1
    return best_move

Tre proprietà derivano da questo schema, tutte tipiche di IDA* e tutte sfruttate in produzione:

1. Anytime. A ogni iterazione si ha una mossa pronta. Se il time control taglia, si restituisce l’ultima completata. Senza iterative deepening si dovrebbe scegliere a priori una depth e rischiare di non finirla.

2. Move ordering tramite PV. La principal variation a depth $d$ viene provata per prima a depth $d+1$. Alpha-beta pota meglio quando la mossa migliore è esaminata per prima: passa da $O(b^d)$ (caso peggiore) a $O(b^{d/2})$ (caso ideale). Questo è il motivo per cui ID-Alpha-Beta non solo è anytime, ma è più veloce di alpha-beta a depth fissa: il riuso della PV è un guadagno netto.

3. Time management. Si stima se la prossima depth entra nel tempo restante. Nei chess engine reali la stima è raffinata (tipicamente la depth $d+1$ costa $\sim 5\text{x}$ quella $d$), e si fanno scelte come “fai una depth in più se il punteggio della PV è calato fra $d-1$ e $d$, sospetta che ci sia un problema da scoprire più in profondità”.

L’EQUIVALENZA con IDA* è sullo schema “rifai DFS con bound crescente, riusa l’output precedente come hint”. Le differenze strutturali contano: il bound qui è depth (intero), in IDA* è f-cost (intero o reale); il “riuso” qui è il move ordering, in IDA* è implicito nel taglio per f-bound. Ma il pattern è lo stesso, ed è il motivo per cui chiunque legga sia il paper di Korf 1985 sia un manuale di chess programming riconosce subito la famiglia.

Applicazioni pratiche

15-puzzle e 24-puzzle ottimi. Korf 1985 dimostra IDA* su 15-puzzle con Manhattan; risolve istanze tipiche in minuti. Korf-Felner 2002 con pattern database disjoint risolvono il 24-puzzle (5x5, $\sim 10^{25}$ stati) ottimamente in giorni di calcolo. Non è una curiosità: i puzzle a sliding tile sono benchmark canonici per ricerca informata e ogni nuovo algoritmo si misura lì.

Rubik’s cube ottimo. Korf 1997 risolve istanze del cubo 3x3 ottimamente con IDA* + tre PDB (corner, edge meta-1, edge meta-2). La heuristic è il massimo dei tre lookup. Soluzioni in 18-28 mosse. Da non confondere con God’s number = 20, dimostrato nel 2010 da Tomas Rokicki e collaboratori (The Diameter of the Rubik’s Cube Group is Twenty, SIAM J. Discrete Math.) con coset enumeration su milioni di CPU-ore: quello è il diametro del gruppo, non un singolo solver.

Chess engine e game tree search. Iterative-deepening alpha-beta è lo standard de facto da decenni. Stockfish (open source, da Marco Costalba 2008, evoluto in progetto comunitario e oggi fra i motori più forti al mondo), Leela Chess Zero (re-implementazione open di AlphaZero, dal 2018), Komodo: tutti usano questo schema. Anche AlphaZero/MuZero, che per il neural-network move evaluation usano MCTS, implementano la chiamata a budget incrementale come schema esterno.

Symbolic planning (PDDL, STRIPS). I planner classici cercano sequenze di azioni che portano lo stato iniziale a soddisfare il goal. IDA* su stati di mondo era il metodo standard prima dell’ascesa di SAT/SMT-based planner. Il pianificatore Fast Downward (Helmert 2006) supporta IDA* come back-end fra altri.

Theorem prover e proof search. Iterative deepening sulle profondità di prova (in resolution prover, in tableaux, in proof search del lambda-cube) è una scelta classica quando lo spazio è infinito ma le dimostrazioni interessanti sono shallow. Otter (William McCune, anni ‘90) e i suoi successori avevano ID come opzione.

LLM agent budget-bounded planning. Sistemi di code-agent (Devin di Cognition 2024, Cursor agent, Claude Code 2024-2025) lavorano con un budget di token e chiamate tool. Una strategia comune: genera un plan a profondità limitata, se non chiude aumenta il budget e riespandi. ANALOGIA strutturale con IDA*: il budget è il bound, l’incremento sostituisce il “minimo $f$ scartato”. Le differenze sono profonde (il budget è un’astrazione composita, niente garanzia di ottimalità, di solito si riusa il prefisso del plan precedente invece di rifarlo) e portano questo schema più vicino a SMA*/RBFS che a IDA* puro.

Tree-of-Thoughts iterative deepening. Yao et al. 2023 (Tree of Thoughts: Deliberate Problem Solving with Large Language Models, NeurIPS 2023) esplorano alberi di pensieri di un LLM con BFS/DFS e value-as-priority. Una variante naturale è budget-bounded: esplora finché il budget di chiamate finisce, poi se il problema non è risolto allarga il budget e ripeti. ANALOGIA con IDA*: il LLM-judge sostituisce $h$, il budget sostituisce il bound. Importante: il LLM-judge non è ammissibile (può sovrastimare), quindi l’ottimalità di Korf 1985 non si applica. Si ottiene “best effort”, non “best”.

Robotics planning con memoria limitata. Pianificatori in robotica embedded (rover, UAV con CPU di bassa potenza) hanno vincoli di RAM stringenti. IDA* e SMA* sono lo standard quando A* esce dalla RAM disponibile.

SAT solver e CSP backtracking. I solver SAT moderni (CDCL, conflict-driven clause learning) non sono IDA* in senso stretto, ma il pattern “esplora con un budget di conflitti, se non risolvi alza il budget” (restart strategies) ha la stessa anatomia. Luby restart sequence e Geometric restart sono iterative-deepening sul numero di conflitti consentiti; lo schema deriva direttamente dall’osservazione di Korf 1985 sul ratio asintotico fra iterazioni successive.

Code-search agent in IDE. Quando un agent di coding (es. Claude Code, Cursor) cerca dove un sintomo originato in modulo X possa derivare in codebase grande, una strategia ragionevole è: ricerca a profondità 2 (file imports diretti); se non trova root cause, allarga a profondità 3 (transitivi); avanti finché il budget di token regge. ANALOGIA con IDA*: il bound è la profondità di ricerca semantica, $h$ è una valutazione di rilevanza fatta dal LLM. Marcata come ANALOGIA: il LLM-judge non è ammissibile e non c’è teorema di ottimalità.

Dove si rompe

Grafi non-tree con molti path verso lo stesso stato. IDA* non ha closed list. Se due path da start a un nodo $n$ esistono, $n$ viene espanso due volte. Se i path sono molti (transposition graph denso, tipico di puzzle con simmetrie e di planning con sub-goal indipendenti), il numero di rivisitazioni esplode. A* con closed list ha $O(\text{stati})$ espansioni; IDA* in casi patologici $O(\text{stati} \cdot \text{media-path-da-start})$. Soluzione parziale: transposition table di dimensione fissa che mantiene gli ultimi $N$ nodi visti e i loro $f$-value, con politica di replacement; non ripristina l’ottimalità in tempo ma riduce la rivisitazione.

f-cost reale con molti valori distinti. Se $f$ assume migliaia di valori reali distinti, ogni iterazione di IDA* finisce dopo poche espansioni perché emerge un $f$ leggermente più piccolo da scartare. Il numero di iterazioni esplode. RBFS gestisce meglio: invece di rifare DFS da capo, riprocessa solo il sotto-albero del miglior figlio. IDA*-CR è un’altra risposta: alza il bound non al minimo $f$ scartato ma a un valore stimato per espandere un numero target di nodi.

Costi a zero. Se un arco ha costo 0, si possono creare cicli a costo accumulato 0. La DFS bounded ci entra. Path checking risolve cicli puri (un nodo non può apparire due volte sullo stesso path), ma cicli logici a costo 0 sul grafo (path diversi ma conseguenze ripetute) restano un problema. La regola pratica: scarta archi a costo 0 dal modello, oppure aggiungi un epsilon al costo per garantire monotonicità stretta.

Heuristic non sufficientemente tight. Manhattan distance per il 15-puzzle è al limite; per il 24-puzzle è disastrosa. Per Rubik’s cube è inutilizzabile. Pattern database (Culberson-Schaeffer 1998) sono la cura: ammissibili, calcolate offline, lookup $O(1)$ al runtime. Ma anche loro hanno costi: 50-500 MB di tabella per dominio non banale, e tempo di precomputo (ore-giorni). Senza buona heuristic, IDA* gira ma non finisce in tempi umani.

Heuristic non ammissibile (LLM-judge, value network apprese). Se $h$ sovrastima, la teoria di Korf 1985 cade: il primo goal trovato può non essere ottimo. In agent LLM con LLM-judge questo è il regime tipico. Si parla di “best-effort search”, non di “optimal search”. Per molti task agent va benissimo (la soluzione perfetta non esiste o non è verificabile); per task con criterio di ottimalità chiaro (es. trovare il path più corto in un grafo) è una rinuncia esplicita.

Branching factor enorme con poca eredità fra iterazioni. Se ogni iterazione aggiunge un sotto-albero quasi del tutto nuovo (poche similarità con l’iterazione precedente), l’overhead della rifrazione è lineare nel numero di iterazioni. Esempio: graph search con archi pesati uniform-distribuiti su un range continuo. Ogni iterazione di IDA* potrebbe aggiungere un solo nodo. A* paga in memoria ma fa lavoro lineare. RBFS o weighted A* sono alternative.

Budget di iterazioni mal calibrato in agent system. L’analogo agent di IDA* aumenta il budget di token o di chiamate. Se l’incremento è troppo piccolo (es. +100 token) la prossima iterazione spesso non aggiunge nulla; se troppo grande (es. raddoppia) si rischia overshooting. Scheduler adattivi (raddoppia se la previous expansion non ha trovato nuovi path; mantieni uguale se ha trovato candidate parziali) sono ricerca attiva (cfr. ToT, LATS, Reflexion).

Concurrent search. IDA* sequenziale è monolitico: una sola DFS bounded alla volta. Parallelizzarla richiede partizionare il sotto-albero fra worker e gestire min_excess globale; non è banale. Edelkamp-Schroedl 2012 cap. 17 dedica spazio a parallel-IDA*. In agent system con $K$ worker concorrenti che esplorano rami distinti, lo schema più simile è SMA*/MCTS che IDA*.

Reward hacking se la heuristic è learned. Se $h$ è una rete neurale appresa (value network), IDA* la usa fiduciosamente. Se la rete è stata addestrata su una distribuzione e il problema corrente esce dalla distribuzione (out-of-distribution), $h$ può dare valori sistematicamente sbagliati (sottovalutare goal-distance, sovravalutarla). In agent system con LLM-judge questo è il regime di default; serve calibrazione e human-in-the-loop, non IDA* puro.

Long-tailed problem instances. Su domini come PDDL planning, la distribuzione del numero di nodi espansi per istanza ha coda pesante: il 90% delle istanze è facile, il 10% è brutalmente difficile. IDA* non ha modo di “rinunciare” a un’istanza dopo $k$ iterazioni: continua. Si aggiungono cap di tempo o di iterazioni esterne, ma non sono parte dell’algoritmo originale.

Cost ratio fra archi piccolo. Se i costi degli archi variano poco (es. tutti fra 1 e 1.001), il numero di valori $f$ distinti è enorme e ogni iterazione di IDA* aggiunge pochi nodi prima di emettere un nuovo min_excess. La quasi-unitarietà dei costi, paradossalmente, fa lavorare male IDA*: meglio costi integer puri (poche iterazioni grosse) o costi reali ben separati (RBFS).

Debugging difficile. A* ha lo stato esplicito: la frontiera è un oggetto ispezionabile, ci si può fermare e guardarci dentro. IDA* è una ricorsione profonda con stato sullo stack: per debug serve instrumentare la DFS bounded con tracing, oppure rieseguire con bound fissi e registrare nodi visitati. Su problemi reali (chess engine in produzione) il debug di iterative deepening richiede tooling dedicato.

Stack overflow su profondità grande. La ricorsione di IDA* arriva a profondità $d$. Su Python con default recursion limit di 1000 e un 24-puzzle di profondità 100, basta. Su 50-puzzle (ipotetico, $d \sim 500$) o su grafi a profondità migliaia, lo stack della VM esplode. Soluzione: trasformare la ricorsione in loop esplicito con stack manuale. Cambia poco la logica, ma evita il limite della VM.

Path checking non basta su grafi diretti con cicli economici. Il path checking elimina cicli in cui un nodo appare due volte sullo stesso path. Su grafi diretti dove un sotto-grafo “sink” ha cicli di costo cumulato basso, IDA* può entrare e uscire dal sink molte volte da path diversi senza mai chiudersi: ogni visita aumenta $f$ gradualmente, ma non in modo da uscire dal bound. La cura è una closed list almeno parziale, sacrificando memoria pura.

Heuristic dipendenti dal contesto. Se $h(n)$ richiede di osservare anche il path che ha portato a $n$ (es. heuristic learned su LSTM che vede la storia), si perde la proprietà di Markov necessaria per ammissibilità. IDA* tecnicamente funziona, ma le garanzie di ottimalità si rompono. Comune negli agent LLM con state summarization basato su conversation history.

Confronto sintetico A* vs IDA* vs RBFS vs SMA*

Una tabella mentale per scegliere l’algoritmo, riassumendo i trade-off discussi:

Algoritmo	Memoria	Ottimalità	Quando usarlo
A*	$O(b^d)$	Sì (h ammissibile)	RAM abbondante, grafo denso, h tight
IDA*	$O(bd)$	Sì (h ammissibile)	RAM stretta, tree-like space, costi integer
RBFS	$O(bd)$	Sì (h ammissibile)	RAM stretta, costi reali, f-cost denso
SMA*	RAM disponibile	Sì se RAM > albero soluzione	Vincolo memoria fisso, riempi tutto
Weighted A*	$O(b^d)$	No (sub-ottimale a fattore $w$)	Velocità prima della perfezione
Anytime A* (ARA*)	$O(b^d)$	Convergente all’ottimo	Real-time, soluzione progressiva

La scelta in pratica: parti da A* (più semplice, debug facile). Quando esaurisce RAM, passa a IDA* se i costi sono integer (puzzle, planning unitario), a RBFS se sono reali (pathfinding geografico con distanze euclidee). SMA* se si ha un budget di RAM fisso da sfruttare. Pattern database come heuristic se il dominio lo permette.

Collegamenti

• search-bfs-dfs — IDDFS è la versione uninformed del medesimo schema. IDA* sta a IDDFS come A* sta a BFS uniform-cost.
• search-a-star — IDA* è A* con vincolo di memoria. Lo stesso teorema di ottimalità (Hart-Nilsson-Raphael 1968) si trasferisce con $h$ ammissibile.
• complessita-big-o — il trade-off centrale di IDA* è spazio $O(bd)$ vs tempo con costante $b/(b-1)$. Senza confidenza nel ragionamento asintotico, sembra una pessima idea rifare DFS dall’inizio.
• minimax — alpha-beta minimax con iterative deepening (chess engine pattern) è EQUIVALENZA argomentabile con IDA* sul pattern “DFS con bound crescente, riuso fra iterazioni”; il bound è depth invece che f-cost.
• markov-decision-process — il setting stocastico: ANALOGIA fra $h$ ammissibile e value function ottimale $-V$. In MDP non si parla di IDA*; si parla di value/policy iteration.
• value-iteration-policy-iteration — algoritmi che apprendono $V$ in modo iterativo. La struttura “rifai-loop-finché-converge” è ANALOGIA con IDA*-loop sul bound.
• monte-carlo-tree-search (in preparazione) — alternativa a IDA* per game tree e per planning su large state space; usa campionamento invece di bound deterministico.
• programmazione-dinamica (in preparazione) — DP memorizza tutti i sotto-risultati; IDA* li ricalcola. Estremi opposti dello stesso trade-off spazio-tempo.
• pattern-databases (in preparazione) — il modo standard di costruire heuristic ammissibili tight per IDA*. Senza PDB, IDA* su Rubik’s cube e su 24-puzzle non chiude.
• branch-bound (in preparazione) — IDA* è un caso particolare di branch-and-bound dove il bound è $f = g + h$ e si itera. Generalizzazione che apre a optimization (TSP, knapsack, ILP).
• beam-search (in preparazione) — beam search trade ottimalità per memoria fissa (k path migliori), trade-off opposto a IDA* che mantiene ottimalità rinunciando a memoria.
• q-learning — $Q(s, a)$ come heuristic learned: se la rete è ammissibile, IDA* usa $Q$ come $h$. ANALOGIA con l’apprendimento di euristiche tight da esperienza.
• llm-agent-planning (in preparazione) — ToT, ReAct, Reflexion, LATS: gli agent system che usano lo schema iterative deepening sul budget di token sono il riflesso operativo dell’idea di Korf 1985 nel mondo LLM 2023-2025.

Per andare oltre

• Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97-109. Il paper originale, leggibile in un’ora; pseudocodice in mezza pagina, esperimenti su 15-puzzle, dimostrazione di ottimalità e analisi asintotica.
• Korf, R. E. (1997). Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases. AAAI 1997. La dimostrazione pratica che IDA* + PDB risolve un problema con $4 \times 10^{19}$ stati. Mostra come si costruisce una PDB e come si combinano PDB multiple.
• Russell, S., Norvig, P. (2020). Artificial Intelligence: A Modern Approach, 4a ed., Pearson. Capitoli 3-4. Riferimento didattico standard per A*, IDA*, RBFS, SMA*, weighted A*. Tabelle di confronto, esempi, esercizi.
• Edelkamp, S., Schroedl, S. (2012). Heuristic Search: Theory and Applications. Morgan Kaufmann. Trattato avanzato: IDA*-CR, IDA*-bidirezionale, external-memory IDA*, parallel IDA*. Stato dell’arte oltre Korf 1985.
• Culberson, J. C., Schaeffer, J. (1998). Pattern Databases. Computational Intelligence, 14(3), 318-334. Il paper che rende IDA* praticabile sui puzzle grandi e su Rubik. Si legge in due ore, è il prerequisito per chiunque voglia implementare un solver ottimo serio.
• Korf, R. E., Felner, A. (2002). Disjoint pattern database heuristics. Artificial Intelligence, 134(1-2), 9-22. Estende PDB con pattern disgiunti e additività; risolve ottimamente il 24-puzzle. Da leggere subito dopo Korf 1985 per capire come si scala IDA* a state space grandi.
• Russell, S. (1992). Efficient memory-bounded search methods. ECAI 1992, 1-5. Introduzione di SMA*, riferimento per chi vuole capire l’altro lato del trade-off memoria-tempo.
• Rokicki, T., Kociemba, H., Davidson, M., Dethridge, J. (2010). The Diameter of the Rubik’s Cube Group is Twenty. SIAM J. Discrete Math. La dimostrazione che God’s number = 20: non IDA*, ma il punto di arrivo del filone aperto da Korf 1997 sulla risoluzione ottima del cubo.