Admissibel heuristikk
term_id: admissible_heuristic
Category: basic_concepts
Definition
I sti-finnings- og søkeproblemer gir en admissibel heuristikk en nedre grense for den faktiske kostnaden for å nå målknuten. Ved å garantere at den estimerte kostnaden alltid er mindre enn eller lik den faktiske kostnaden, sikres det at algoritmen finner den optimale løsningen.
Summary
En heuristisk funksjon i søkealgoritmer som aldri undervurderer den sanne kostnaden for å nå målet, noe som sikrer optimalitet.
Key Concepts
- Nedre grense
- Optimalitetsgaranti
- A*-søk
- Kostnadsestimering
Use Cases
- Ruteplanlegging for GPS-navigasjon
- Løsning av puslespill (f.eks. 8-brikker-puslespillet)
- Robotbevegelsesplanlegging i miljøer med mange hindringer