Zulässige Heuristik
term_id: admissible_heuristic
Category: basic_concepts
Definition
Bei Pfadsuch- und Suchproblemen bietet eine zulässige Heuristik eine untere Schranke für die tatsächlichen Kosten, um den Zielknoten zu erreichen. Durch die Garantie, dass die geschätzten Kosten immer kleiner oder gleich den tatsächlichen Kosten sind, wird sichergestellt, dass Suchalgorithmen wie A* optimale Pfade finden.
Summary
Eine Heuristik-Funktion in Suchalgorithmen, die die tatsächlichen Kosten zum Erreichen des Ziels niemals überschätzt und somit die Optimalität sicherstellt.
Key Concepts
- Untere Schranke
- Optimalitätsgarantie
- A*-Suche
- Kostenschätzung
Use Cases
- Routenplanung in GPS-Navigationssystemen
- Lösen von Puzzles (z. B. 8-Puzzle)
- Bewegungsplanung von Robotern in umgebungsreichen Umgebungen