8. La ricerca euristica

A differenza del precedente articolo in cui abbiamo visto diversi tipi di ricerca non informata, in questo articolo vedremo come alcuni algoritmi elaborano i percorsi in base alle informazioni sui nodi e sugli archi in loro possesso. Le informazioni euristiche su quali nodi sono più promettenti possono guidare la ricerca modificando il nodo selezionato alla riga 11 dell'algoritmo di ricerca generico.

Questi tipi di algoritmo si basano su una funzione euristica h ( n ), prende in input un nodo n e restituisce un valore reale positivo che è la stima del costo del percorso meno costoso dal nodo n al nodo obiettivo. La funzione h ( n ) è un'euristica ammissibile se h ( n ) è sempre minore o uguale all'attuale costo del percorso meno costoso dal nodo n al nodo obiettivo.

La funzione euristica utilizza le informazioni che possono essere facilmente ottenibili sui nodi. C'è sempre un compromesso tra il costo per determinare il valore euristico e l'accuratezza del valore stesso. Un metodo standard per derivare questo tipo di funzione è risolvere un problema più semplice e utilizzare il costo per l'obiettivo nel problema semplificato come funzione euristica del problema originale.

Un'applicazione della funzione euristica consiste nella ricerca in profondità per ordinare i neighbors che vengono aggiunti allo stack della frontiera. Così facendo si aggiunge alla frontiera quel nodo che rappresenta il miglior vicino. Questo metodo prende il nome di ricerca euristica in profondità (heuristic depth-first search). Questa ricerca seleziona il percorso locale migliore, anche se ha lo svantaggio di esplorare tutti i percorsi dal percorso selezionato prima di selezionarne un'altro. E' evidente che condivide gli stessi problemi della ricerca in profondità e non è garantito che trovi una soluzione, e anche se la trovasse, non è detto che sia quella ottimale.

Un altro modo per utilizzare una funzione euristica consiste nel selezionare sempre un percorso sulla frontiera con il valore euristico più basso. Questo algoritmo prende il nome di greedy best-first search. Questa ricerca svolge bene le sue attività, anche se a volte segue dei percorsi che sembrano promettenti perchè appaiono vicini all'obiettivo, ma il percorso esplorato può allungarsi.

La ricerca A*

La ricerca A* è un tipo di ricerca che utilizza sia il costo del percorso sia le informazioni euristiche nella selezione dell'estensione del percorso. Per ogni percorso sulla frontiera, A* utilizza una stima del costo totale del costo relativo al percorso dal nodo iniziale al nodo obiettivo. Viene utilizzata la funzione cost ( p ) come funzione euristica del costo stimato del percorso dalla fine di p all'obiettivo. Per ogni p sulla frontiera viene definita la funzione f ( p ) = cost ( p ) + h ( p ). Questa è la stima del costo totale del percorso. Graficamente si può visualizzare come:

$\underbrace { \underbrace { start \xrightarrow { \text { actual } } }_{\text{cost ( p ) } }\underbrace { n \xrightarrow { \text { estimate } } goal }_{\text{h ( p ) } }}_{\text {f ( p )}}$

In questa formula se h ( n ) è una euristica ammissibile e non sovrastima il costo dal nodo n al nodo obiettivo, allora f ( p ) non sovrastima il costo del percorso dal nodo iniziale al'obiettivo. L'algoritmo A* viene implementato usando l'algoritmo di ricerca generico, con l'unica differenza che la frontiera viene trattata come una coda di priorità ordinata secondo f ( p ).

Un algoritmo è ammissibile se, se, ogni volta che esiste una soluzione, restituisce una soluzione ottima. Per garantire l'ammissibilità, devono valere alcune condizioni sul grafico e sull'euristica. Definiamo quelle relative a un algoritmo di ricerca A*.

Definizione di ammissibilità relativa ad A*

A* è un algoritmo di ricerca ammissibile se:

• il fattore di ramificazione è infinito
• tutti i costi dell'arco sono maggiori di $\epsilon > 0$
• h è una funzione euristica ammissibile

L'ammissibilità dell'algoritmo A* non garantisce che ogni nodo intermedio selezionato dalla frontiera si trovi su un percorso ottimale dal nodo iniziale a un nodo finale. L'ammissibilità garantisce che la prima soluzione trovata sarà ottimale anche in grafi con cicli.

Approfondimento iterativo A* (IDA*)

Un particolare algoritmo che si basa sulla ricerca A* è l'approfondimento iterativo A*, o IDA*, il quale esegue iterativamente ricerche di profondità con un limite di ricerca. Invece del limite sugli archi, il limite si trasforma in un limite sul valore di f ( n ). Inizialmente questa soglia è il valore di f ( s ), dove s è il nodo iniziale. Successivamente l'algoritmo espande il percorso con una ricerca in profondità senza mai andare oltre il valore del limite di f.

Se la ricerca fallisce e il limite è stato raggiunto, il limite successivo è il valore minimo di f rispetto al limite corrente. Invece se la ricerca fallisce e il limite è stato raggiunto, il limite successivo è il minimo valore di f che ha superato il valore precedente. Quindi l'algoritmo IDA*, a differenza del'algoritmo A*, ricalcola una ricerca approfondita invece di memorizzarne il valore.

Progettare una funzione euristica

E' arrivato ora il momento di discutere di come progettare una funzione euristica. Il modo standard per costruire una funzione euristica è trovare una soluzione a un problema più semplice, con meno vincoli rispetto al precedente e quindi di facile risoluzione. Una soluzione ottima al problema più semplice non può avere un costo maggiore di una soluzione ottima al problema completo perché qualsiasi soluzione al problema completo è una soluzione al problema più semplice.

In molti problemi spaziali in cui il costo è la distanza e la soluzione è vincolata a percorrere archi predefiniti (ad esempio segmenti stradali), la distanza euclidea in linea retta tra due nodi è un'euristica ammissibile perché è la soluzione del problema più semplice in cui il l'agente non è vincolato a percorrere gli archi. Una volta semplificato il problema, potrebbe essere risolto utilizzando la ricerca, che dovrebbe essere più semplice del problema originale.

È spesso utile memorizzare nella cache questi risultati in un database pattern che mappa i nodi del problema più semplice nel valore euristico. Nel problema più semplice, spesso ci sono meno nodi, quindi più nodi originali sono mappati in un singolo nodo più semplice, quindi questo potrebbe essere fattibile.