Iterative deepening A*

Iterative deepening A*
Classe	Algoritmo di ricerca
Struttura dati	Grafo
Caso peggiore temporalmente	$O(|E|)=O(b^{d})$
Caso peggiore spazialmente	$O(d)$
Ottimale	sì
Completo	sì

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*.

Implementazione

 path              percorso di ricerca attuale (si comporta come una pila)
 node              nodo attuale (ultimo nodo di path)
 g                 il costo per raggiungere il nodo corrente
 f                 costo stimato per raggiungere la soluzione (radice->nodo attuale->soluzione)
 h(node)           costo stimato per raggiungere la soluzione (nodo attuale->soluzione)
 cost(node, succ)  costo per il prossimo passo
 is_goal(node)     funzione booleana che assume valore di verità se il nodo è una soluzione
 successors(node)  funzione di espansione di un nodo, sceglie i successori ordinandoli in base a g + h(n)
 ida_star(root)    restituisce o NOT_FOUND o una coppia di valori (cammino, costo)
   
 procedure ida_star(root)
   bound := h(root)
   path := [root]
   loop
     t := search(path, 0, bound)
     if t = FOUND then return (path, bound)
     if t = ∞ then return NOT_FOUND
     bound := t
   end loop
 end procedure

 function search(path, g, bound)
   node := path.last
   f := g + h(node)
   if f > bound then return f
   if is_goal(node) then return FOUND
   min := ∞
   for succ in successors(node) do
     if succ not in path then
       path.push(succ)
       t := search(path, g + cost(node, succ), bound)
       if t = FOUND then return FOUND
       if t < min then min := t
       path.pop()
     end if
   end for
   return min
 end function

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.

Bibliografia

• (EN) Richard E. Korf, Depth-first Iterative-Deepening: An Optimal Admissible Tree Search (PDF), in Artificial Intelligence, vol. 27, 1985, pp. 97–109, DOI:10.1016/0004-3702(85)90084-0.
• (EN) Richard E. Korf, Michael Reid e Stefan Edelkamp, Time complexity of iterative-deepening-A∗, in Artificial Intelligence, vol. 129, 1–2, 2001, pp. 199–218, DOI:10.1016/S0004-3702(01)00094-7.
• (EN) Stuart Russell, Peter Norvig, 3.5 Informed (heuristic) search strategies, in Artificial Intelligence: A Modern Approach, 3ª ed., Pearson, 1º dicembre 2009, p. 99, ISBN 9780136042594.

Voci correlate

• Algoritmo A*
• Recursive best-first search
• MA*