Admissibel heuristik
term_id: admissible_heuristic
Category: basic_concepts
Definition
Ved stifinding og søgeproblemer giver en admissibel heuristik et nedre grænse for den faktiske omkostning til at nå målknuden. Ved at garantere, at den estimerede omkostning altid er mindre end eller lig med den sande omkostning, sikres det, at algoritmen finder den optimale løsning.
Summary
En heuristisk funktion i søgealgoritmer, der aldrig undervurderer den sande omkostning til at nå målet, hvilket sikrer optimalitet.
Key Concepts
- Nedre grænse
- Optimalitetsgaranti
- A*-søgning
- Omkostningsestimatering
Use Cases
- Ruteplanlægning i GPS-navigation
- Løsning af puslespil (f.eks. 8-puslespil)
- Robotbevægelsesplanlægning i miljøer med mange forhindringer