Dopuszczalna heurystyka
term_id: admissible_heuristic
Category: basic_concepts
Definition
W problemach znajdowania ścieżki i wyszukiwania dopuszczalna heurystyka dostarcza dolnego ograniczenia rzeczywistego kosztu dotarcia do docelowego węzła. Gwarantując, że oszacowany koszt jest zawsze mniejszy lub równy rzeczywistemu kosztowi,
Summary
Funkcja heurystyczna w algorytmach wyszukiwania, która nigdy nie przeszacowuje prawdziwego kosztu dotarcia do celu, zapewniając optymalność.
Key Concepts
- Dolne ograniczenie
- Gwarancja optymalności
- Wyszukiwanie A*
- Estymacja kosztu
Use Cases
- Planowanie tras w nawigacji GPS
- Rozwiązywanie łamigłówek (np. 8-puzzle)
- Planowanie ruchu robota w środowiskach z przeszkodami