5 minute read
Introduzione
A* è un algoritmo di ricerca e ottimizzazione basato su grafi. Viene frequentemente impiegato nell’intelligenza artificiale perché in grado di gestire grafi ampi e indeterminati.
L’algoritmo A* può essere utilizzato per risolvere problemi come: gioco del 15, percorso minimo, Sudoku, cubo di Rubik, ecc.
In generale, A* può risolvere efficacemente i problemi che soddisfano i requisiti:
- La soluzione è determinata da cambamenti sequenziali di stato rappresentabili con grafi;
- Il nodo iniziale e il nodo finale devono essere noti. Talvolta è sufficiente conoscere solo le regole che compongono la soluzione (vedi Sudoku);
- Deve essere noto un algoritmo euristico che stima il costo del percorso tra un nodo qualsiasi e la soluzione.
- Deve essere sempre noto il costo che separa due nodi adiacenti. (Nella maggioranza dei problemi tale valore è sempre unitario).
L’euristica
L’algoritmo euristico ha il compito di stimare la distanza tra qualsiasi nodo e la soluzione. L’euristica influenza fortemente i risultati conseguiti da A*. Esso, in particolare, ne determina il tempo complessivo di esecuzione. Un algoritmo euristico molto efficace consente ad A* di trovare velocemente la soluzione. Nel caso pessimo, una funzione euristica costante, A* diviene un algoritmo di ricerca molto simile a Dijkstra.
