Follow

Supponiamo di trovarci in una città a noi sconosciuta e di avere un appuntamento importante con una stupenda ragazza (o ragazzo a seconda dei casi). La cosa più semplice da fare è chiedere indicazioni ai passanti. Purtroppo però siamo sfortunati e quel giorno diluvia che dio la manda e non c’è anima viva in giro. Non c’è speranza.

LA RICERCA IN AMPIEZZA

In questo caso l’unica soluzione che avete è di tentare tutte le strade. Partite dal punto A e verificate tutti gli incroci a cui si arriva direttamente da A, se non siete arrivati tornate ad A e verificate tutti gli incroci a cui si arriva partendo da A e attraversando un solo incrocio, e così via, aumentanto ad ogni passo la profondità della ricerca. Questo tipo di ricerca prende il nome di ricerca in ampiezza. Funziona? Sicuro, prima o poi arriverete a destinazione. Tuttavia la domanda sorge spontanea: quanto poi?

Supponendo, come avviene spesso in realtà, che ad ogni incrocio si dipanino 3 strade (oltre a quella da cui siete venuti) se disgraziatamente la ragazza si trova a solo 10 incroci di distanza dovrete testare circa 59.049 incroci e un numero maggiore di strade. Un compito decisamente eccessivo anche per il più motivato.

Dobbiamo trovare un alternativa. Appare evidente che abbiamo bisogno di un informazione che ci permetta di scartare le strade che sicuramente non ci portano a destinazione. Chiamiamo quindi la ragazza e scopriamo che è una nerd d’alta categoria. Ella infatti vole metterci alla prova. Invece di dirci la strada ci promette solo di dirci la distanza in linea retta che separa ogni incrocio che vogliamo da lei. È sufficiente? Si, e non solo troviamo una strada che ci conduce da lei ma troviamo la migliore.

LA RICERCA GOLOSA

La prima soluzione che ci viene in mente è semplice: fra tutti gli incroci che posso raggiungere da A scelgo quello che è più vicino alla ragazza e così via per ogni incrocio su cui vado a finire. Questo tipo di ricerca (che prende il nome di ricerca golosa) è sicuramente migliore della ricerca in ampiezza tuttavia ha due grossi problemi: non trova la strada più breve e, nel caso di grafo con cicli, può finire per ciclare all’infinito.

LA RICERCA A*

Scegliamo questa strategia: assegno a tutti gli incroci che posso raggiungere dall’incrocio in cui sono un numero N corrispondente alla somma della strada percorsa fino a quel punto più la distanza in linea retta che separa quell’incrocio dalla ragazza. A questo punto scelgo l’incrocio che ha il numero N più basso fra quelli che ho assegnato fin’ora. Questa ricerca prende il nome di A* ed è l’algoritmo di ricerca più efficiente  su un grafo pesato (come ad esempio una mappa stradale).

I punti a favore di A* sono fondamentalmente due: l’efficienza computazionale e il fatto che, in alcune condizioni, il percorso trovato è ottimo.

EURISTICHE AMMISSIBILI

Ma quali sono queste condizioni? Torniamo all’informazione che ci forniva la ragazza: la distanza in linea retta di ogni incrocio da lei. Questa prende il nome di funzione euristica. In parole povere è una funzione che esprime una stima della “distanza” dall’obiettivo. Bene, affinché la ricerca di A* sia ottima è necessario che la funzione euristica non sovrastimi mai la distanza reale dall’obiettivo! Quando questa condizione è soddisfatti si dice che la funzione euristica è ammissibile.

Nel nostro caso la funzione euristica soddisfa questa condizione in quanto la distanza in linea retta fra un incrocio e la ragazza non può mai essere maggiore della distanza reale (per definizione la retta è la distanza più breve fra due punti). La funzione è quindi ammissibile soluzione che troveremo sarà quindi ottima.

La non ammissibilità di una funzione non è però un limite stringente, spesso infatti trovare una funzione euristica ammissibile necessita di un quantitativo di calcoli troppo elevato che vanificherebbe i vantaggi di A*. In questi casi si può scegliere di usare una funzione non ammissibile ma di facile calcolo a patto di accontentarsi di una soluzione che potrebbe non essere ottimale.

Abbiamo imparato tanto in questa uscita. La ragazza al nostro arrivo sarà sicuramente soddisfatta.