Algoritmo di Ricerca A*
- Introdotto da
- Peter E. Hart, Nils J. Nilsson, and Bertram Raphael
- Anno
- 1968
- Tipo
- algorithm
- Famiglia
- Graph Algorithms
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'Algoritmo di Ricerca A*, sviluppato da Peter E. Hart, Nils J. Nilsson e Bertram Raphael nel 1968, è un algoritmo di pathfinding ottimale che combina i benefici dell'algoritmo di Dijkstra con la guida euristica.
Trova efficientemente il percorso più breve bilanciando la distanza effettiva dall'inizio con la distanza stimata verso l'obiettivo.
L’intuizione alla base del metodo
A* utilizza una funzione di valutazione f(n) = g(n) + h(n), dove g(n) è il costo effettivo dall'inizio al nodo n, e h(n) è una stima euristica del costo rimanente verso l'obiettivo. Esplorando i nodi con il valore f(n) più basso, l'algoritmo restringe efficientemente lo spazio di ricerca verso l'obiettivo mantenendo l'ottimalità quando l'euristica è ammissibile (non sovrastima mai). Ciò rende A* significativamente più veloce dei metodi di ricerca non informati, pur garantendo di trovare il percorso ottimale.
Storia
Hart, Nilsson e Raphael pubblicarono A* nel 1968, dimostrando che l'aggiunta di informazioni euristiche all'algoritmo di Dijkstra poteva migliorare drasticamente l'efficienza della ricerca mantenendo l'ottimalità. L'algoritmo divenne fondamentale nell'intelligenza artificiale e nella ricerca operativa. Sviluppi successivi includono A* bidirezionale, IDA* (iterative deepening) e vari miglioramenti euristici. A* rimane la scelta standard per il pathfinding nei moderni motori di gioco e nei sistemi robotici.
Quando usarlo
Applicare A* quando è necessario trovare percorsi ottimali in grafi in cui è disponibile una buona funzione euristica. È particolarmente efficace per il pathfinding nei giochi, nella robotica e nella pianificazione dei percorsi, dove la ricerca informata può ridurre sostanzialmente il calcolo. Usarlo quando la velocità è importante ma è richiesta l'ottimalità. Per casi senza un'euristica affidabile, utilizzare invece l'algoritmo di Dijkstra.
Limiti e considerazioni
- L'ottimalità dipende dall'ammissibilità della funzione euristica
- Le prestazioni si degradano significativamente con euristiche scarse o inammissibili
- L'utilizzo della memoria può essere sostanziale in ampi spazi di ricerca (mantiene insiemi aperti e chiusi)
- Richiede una conoscenza esplicita del dominio per progettare buone funzioni euristiche
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Pathfinding ottimale quando l'euristica è ammissibile
- Molto più veloce di Dijkstra o della ricerca in ampiezza quando sono disponibili buone euristiche
- Flessibile: funziona con qualsiasi funzione euristica ammissibile
- Ben adatto a problemi di pathfinding con un singolo obiettivo
- Ampia validazione nel mondo reale in giochi, robotica e sistemi di navigazione
Applicazioni
- Pathfinding nei videogiochi: navigazione NPC in tempo reale in ambienti di gioco dinamici
- Pianificazione del movimento robotico: pianificazione di percorsi ottimali per robot autonomi che evitano ostacoli
- Navigazione GPS: calcolo di percorsi efficienti considerando reti stradali e traffico
- Risoluzione di puzzle: ricerca di soluzioni ottimali in problemi combinatori come il puzzle delle 15
- Routing di rete: determinazione di percorsi efficienti per pacchetti con euristiche sulla qualità dei collegamenti
- Bioinformatica: ricerca di allineamento di sequenze e predizione della struttura proteica
Come funziona
Come funziona
Creare un insieme aperto con il nodo di partenza, impostare il suo valore g (costo dall'inizio) a zero e calcolare il suo valore h utilizzando la funzione euristica.
Selezionare il nodo con il valore f più basso dall'insieme aperto, calcolare i valori f per i suoi vicini non visitati e aggiungere i vicini promettenti all'insieme aperto.
Continuare ad espandere i nodi finché l'obiettivo non viene raggiunto con il valore f più basso, il che garantisce il percorso ottimale; ricostruire il percorso tracciando i puntatori dei genitori.
Errori comuni
- Utilizzo di un'euristica inammissibile che sovrastima i costi, portando a percorsi subottimali
- Scelta di un'euristica troppo semplice o non correlata al problema, riducendo l'efficienza della ricerca
- Implementazione inefficiente dell'insieme aperto (dovrebbe usare una coda di priorità), causando una lenta selezione dei nodi
Domande frequenti
Cos'è un'euristica ammissibile e perché è importante?
Un'euristica ammissibile non sovrastima mai il costo effettivo verso l'obiettivo. Questa proprietà garantisce che A* trovi il percorso ottimale. Se un'euristica sovrastima, A* potrebbe perdere percorsi più brevi e restituire soluzioni subottimali.
Come si progetta una buona euristica per un problema?
Le buone euristiche si basano sulla conoscenza del dominio e sulla struttura del problema. Per il pathfinding basato su griglia, la distanza di Manhattan o euclidea funziona bene. Per problemi più complessi, considerare il rilassamento dei vincoli o l'uso di database di pattern per calcolare euristiche ammissibili.
Qual è la differenza tra l'algoritmo A* e Dijkstra?
Entrambi trovano percorsi ottimali, ma A* utilizza un'euristica per dare priorità all'esplorazione verso l'obiettivo, rendendolo molto più veloce quando è disponibile una buona euristica. Dijkstra esplora uniformemente in tutte le direzioni ed è più sicuro quando le euristiche non sono affidabili.
A* può garantire di trovare il percorso più breve?
Sì, A* garantisce il percorso più breve quando l'euristica è ammissibile (non sovrastima mai il costo effettivo). Con euristiche inammissibili, l'ottimalità non è garantita.
Metodi correlati
Fonti
Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107.
Apri il riferimento DOICopiato.Russell, S. J., & Norvig, P. (2009). Artificial Intelligence: A Modern Approach (3rd ed.). Pearson.
ISBN: 978-0-13-604259-4Copiato.