Guide

In senso lato si potrebbe dire che tutta la ricerca in AI è un problema di route finding, al computer lasciato libero di agire autonomamente si chiede di partire dai dati a sua disposizione e arrivare all’operazione richiesta nel modo migliore, dove migliore significa più breve, più economico, più produttivo.

Ma senza dubbio riferirsi al primo caso, al significato concreto, è molto più immediato. Senza contare che applicazioni di route finding in senso stretto sono oggi estremamente diffuse.

Dalle reti di computer, dove sono i dati a cercare un percorso ottimo nell’ottica di velocità delle connessioni, alla pianificazione dei voli aerei, settore estremamente complesso per le numerose variabili in gioco, che sarebbe impossibile realizzare senza l’ausilio del computer.

E poi ancora applicazioni alla portata di tutti quotidianamente, quali la navigazione satellitare tramite GPS e l’utilizzo di programmi o siti web per la ricerca di mappe e percorsi.

Quando attraverso un sito web cerchiamo il percorso più breve tra Cuneo e Benevento, oppure impostiamo il tragitto sul navigatore dell’automobile, il sistema ovviamente non conosce in anticipo la risposta, ma la calcola all’istante. Per fare questo utilizza alcune informazioni di base: la distanza in linea d’aria tra le due città, la distanza dalla città di partenza con tutte le città più prossime, la distanza della città più prossima con la città di arrivo.

Questo insieme di informazioni sono preziosissime per l’elaboratore, poiché lo tolgono dal consueto scenario di indeterminazione in cui molto spesso si trovano a lavorare sistemi esperti. In sostanza l’elaboratore sa dove vuole arrivare, e sa quale sarebbe la soluzione ottima per arrivarci, ossia la distanza in linea d’aria. Non potendo ottenere quel risultato cercherà comunque di non scostarsene troppo. Non solo, avendo numerose informazioni anche sulle città adiacenti, potrà anche muoversi con criterio verso la destinazione più prossima, tipicamente cercando una città che in linea d’aria disti dalla meta meno della precedente.

Tutto questo si può tradurre in una funzione matematica che prende in nome di funzione euristica, dal greco eurisko che significa “trovare”.

Supponiamo di trovarci al nodo n nel grafo di città da attraversare per arrivare alla meta. Questo nodo avrà un costo g(n) rappresentato dai chilometri percorsi dalla partenza. Da questo nodo si disterà in linea d’aria alla meta di una quantità h(n). In totale quindi il nodo è rappresentato dalla funzione f(n)=g(n)+h(n).

Al nodo successivo si possono fare le medesime considerazioni, ottenendo una funzione f*(successivo(n)).

In definitiva il criterio di scelta del nodo successivo sarà tale che f(n)