Algoritmo di ricerca A*
A* è un insieme di passi (un algoritmo) che i computer possono usare per capire come arrivare velocemente da qualche parte tra due luoghi. Se hai una lista di luoghi e quanto è difficile andare da uno all'altro, usando A* puoi capire rapidamente qual è il modo più veloce. È correlato all'algoritmo di Dijkstra, ma fa congetture intelligenti in modo da non passare tanto tempo a cercare vie lente. È una buona serie di passi se si vuole solo il percorso tra due luoghi. Se hai intenzione di chiedere molti percorsi dalla stessa mappa, allora ci sono modi più veloci, che trovano tutte le risposte in una volta, come l'algoritmo Floyd-Warshall. A* non funziona se si vogliono visitare diversi luoghi in un solo viaggio (il problema del commesso viaggiatore).
I passi
A* ha bisogno prima di una lista di tutti i posti in cui puoi andare, e poi ha bisogno di una lista di quanto è lontana la strada tra ognuno di essi. Poi ti dirà il modo più veloce per andare dal posto A al posto Z.
Per un esempio, diremo che A è collegato ai posti B e C, e B e C sono entrambi collegati a D ed E. D ed E sono entrambi collegati a Z. Ci sono 4 modi possibili per andare da A a Z. Si può andare A-B-D-Z, A-C-D-Z, A-B-E-Z, o A-C-E-Z. Un computer che usa A* guarda prima quanto è difficile andare da A a B e da A a C. Questo è il "costo" per quei luoghi. Il costo di un luogo significa quanto è difficile andare da A a quel luogo. Dopo aver scritto entrambi i costi, il computer guarda quanto è difficile andare da B a D, e lo aggiunge al costo di B. Lo scrive come costo di D. Poi il computer guarda quanto è difficile andare da C a D, e lo aggiunge al costo di C. Questo è un costo diverso per D, e se è inferiore a quello che ha già, sostituirà quello vecchio. Il computer vuole solo conoscere il percorso migliore, quindi ignora il percorso con il costo più alto. Ricorderà solo uno tra A-B-D e A-C-D, quello che è più veloce.
Il computer continua e trova il modo più veloce per arrivare a E. Infine, va da D a Z e trova un costo, e da E a Z e trova un costo. Ottiene un costo finale per Z, e questo è il costo più piccolo che può ottenere. Ora il computer sa qual è la strada più veloce e ha la risposta. Il computer può fare una serie simile di passi, ma con molti più posti. Ogni volta, guarderà il posto più vicino ad A, e aggiungerà i costi ai vicini di quel posto.
La gente chiama la suddetta serie di passi l'algoritmo di Dijkstra. L'algoritmo di Dijkstra può essere lento, perché guarderà molti posti che potrebbero andare nella direzione sbagliata da Z. Se si chiede al computer come andare da una città ad una vicina, l'algoritmo di Dijkstra potrebbe finire per cercare in un altro stato.
A* risolve questo problema. A* ti permette di dire al computer un'ipotesi su quanto sarà lontano da ogni luogo alla fine. Il computer può usare l'ipotesi per dire approssimativamente quanto tempo ci vorrà per andare da un certo posto a Z. Invece di scegliere semplicemente il posto più vicino ad A da guardare, guarderà quello che probabilmente avrà il totale più basso. Trova questo totale aggiungendo il costo alla distanza prevista a sinistra. In questo modo, può guardare solo nella direzione in cui le cose probabilmente miglioreranno. Va bene se l'ipotesi non è perfetta, ma anche una semplice ipotesi sbagliata può far andare il programma molto più veloce. Se state cercando di trovare un percorso tra due luoghi nel mondo reale, una buona ipotesi è solo la distanza tra loro in linea retta. Il percorso reale sulle strade sarà più lungo, ma questo permette al programma di indovinarlo, e non andrà nella direzione sbagliata.
Nella letteratura matematica o informatica, questa ipotesi è spesso una funzione del luogo, ed è chiamata euristica. Ogni luogo è un vertice, e ogni percorso tra due luoghi è un bordo. Queste sono parole della teoria dei grafi.
