Iterative deepening A*
# Iterative deepening A*

Iterative deepening A* (noto anche con l'acronimo IDA*) è un algoritmo euristico proposto da Richard Korf nel 1985. È in grado di trovare il cammino minimo fra un nodo indicato come iniziale e ciascun membro di un insieme di "nodi soluzione" in un grafo pesato.

L'algoritmo è una variante dell'iterative deepening depth-first search usata per migliorare le prestazioni di A*. Il vantaggio principale di IDA* è infatti l'uso lineare della memoria, al contrario di A* che ha bisogno, nel caso peggiore, di uno spazio esponenziale. D'altro canto, questo algoritmo usa fin troppa poca memoria, che potrebbe essere invece sfruttata per migliorare le prestazioni in termini di tempo (cfr. memoizzazione).

## Descrizione

Esattamente come nell'iterative deepening depth-first search, l'algoritmo viene ripetuto più volte con una soglia sempre più grande, finché non verrà raggiunta una soluzione. Tuttavia, in questo caso la soglia non dipenderà più dalla profondità rispetto al nodo radice, ma dal valore assunto dalla funzione di valutazione. Come in A* ed altri algoritmi euristici, viene usata come funzione di valutazione $f(n)=g(n)+h(n)$, dove $g$ è il costo accumulato per raggiungere il nodo $n$, mentre $h$ è una stima euristica del costo necessario per arrivare alla soluzione partendo da $n$.

L'algoritmo inizia impostando la soglia (threshold) $T\leftarrow f(s)$ dove $s$ è il nodo iniziale, e mette i figli di $s$ in una coda (detta fringe). Successivamente, espande i nodi nel fringe per i quali $f(n)=T$, finché non raggiunge una soluzione. Se nel fringe non è presente nessun $n$ tale che $f(n)=T$, allora l'algoritmo imposta $T\leftarrow \min _{n\in fringe}(g(n)+h(n))$, ovvero aggiorna la soglia in base al minimo valore assunto dalla funzione di valutazione fra tutti i nodi del fringe.

A causa del numero di volte che l'algoritmo può espandere lo stesso nodo, la sua esecuzione rimane, nel peggiore dei casi, esponenziale in termini di tempo. Questo problema è in parte attenuato in altri algoritmi, quali RBFS e le varie implementazioni di MA*.

## Proprietà

Come per A*, IDA* garantisce una soluzione ottimale per il problema del cammino minimo quando la funzione euristica $h$ è ammissibile, ovvero tale che

    $h(n)\leq c(n)$

per tutti i nodi $n$ del grafo, dove $c(n)$ è il costo effettivo per raggiungere la soluzione a partire dal nodo $n$.

IDA* è particolarmente utile quando si opera in un sistema con memoria limitata. La ricerca A* mantiene una gran quantità di nodi inesplorati in memoria, che si riempie esponenzialmente. Di contro, dato che IDA* non mantiene in memoria alcun nodo tranne quelli del cammino corrente, richiede una quantità di memoria lineare rispetto alla lunghezza della soluzione cercata. La sua complessità in termini di tempo è stata analizzata da Korf et al. sotto l'assunzione che l'euristica $h$ sia consistente (condizione più forte rispetto all'euristica ammissibile), ovvero tale che

    $h(n)\leq \mathrm {cost} (n,n')+h(n')$

per ogni nodo $n$ e per ogni suo successore $n'$; conclusero che, se messo a confronto con algoritmi di ricerca non informati (ovvero a forza bruta), i quali trovano una soluzione in tempi esponenziali, IDA* riduce la profondità di ricerca della soluzione (di un fattore costante), ma non riduce il fattore di diramazione.

