Iterative deepening A*

Template:Algoritmo 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 \underset{n\in fringe}{\min }(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

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

 function Template:Colore(Template:Colore, Template:Colore, Template:Colore)
   Template:Colore := Template:Colore.last
   Template:Colore := Template:Colore + Template:Colore(Template:Colore)
   if Template:Colore > Template:Colore then return Template:Colore
   if Template:Colore(Template:Colore) then return FOUND
   Template:Colore := ∞
   for Template:Colore in Template:Colore(Template:Colore) do
     if Template:Colore not in Template:Colore then
       Template:Colore.push(Template:Colore)
       Template:Colore := Template:Colore(Template:Colore, Template:Colore + Template:Colore(Template:Colore, Template:Colore), Template:Colore)
       if Template:Colore = FOUND then return FOUND
       if Template:Colore < Template:Colore then Template:Colore := Template:Colore
       Template:Colore.pop()
     end if
   end for
   return Template:Colore
 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)\le 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)\le \mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}(n,n^{\prime })+h(n^{\prime })$

per ogni nodo $n$ e per ogni suo successore $n^{\prime }$; 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

• Template:Cita pubblicazione
• Template:Cita pubblicazione
• Template:Cita libro

Voci correlate

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