Euristica ammissibile
term_id: admissible_heuristic
Category: basic_concepts
Definition
Nei problemi di ricerca e individuazione del percorso, un’euristica ammissibile fornisce un limite inferiore al costo effettivo per raggiungere il nodo target. Garantendo che il costo stimato sia sempre minore o uguale al costo reale, algoritmi come A* possono trovare il percorso ottimale senza esplorare inutilmente lo spazio degli stati.
Summary
Una funzione euristica negli algoritmi di ricerca che non sovrastima mai il costo reale per raggiungere l’obiettivo, garantendo l’ottimalità.
Key Concepts
- Limite inferiore
- Garanzia di ottimalità
- Ricerca A*
- Stima del costo
Use Cases
- Pianificazione del percorso nella navigazione GPS
- Risoluzione di puzzle (es. puzzle 8)
- Pianificazione del movimento robotico in ambienti ricchi di ostacoli