Admissibel heuristik
term_id: admissible_heuristic
Category: basic_concepts
Definition
Vid sökning och vägvalsproblem ger en admissibel heuristik en undre gräns för den faktiska kostnaden för att nå målnoden. Genom att garantera att den beräknade kostnaden alltid är mindre än eller lika med den verkliga kostnaden säkerställs att algoritmen hittar den optimala lösningen.
Summary
En heuristisk funktion i sökalgoritmer som aldrig överskattar den verkliga kostnaden för att nå målet, vilket garanterar optimalitet.
Key Concepts
- Undre gräns
- Optimalitetsgaranti
- A*-sökning
- Kostnadsuppskattning
Use Cases
- Ruttplanering i GPS-navigering
- Lösning av pussel (t.ex. 8-pussel)
- Robotrötningsplanering i miljöer med många hinder