Sopiva heuristiikka
term_id: admissible_heuristic
Category: basic_concepts
Definition
Reitityshakutehtävissä sopiva heuristiikka tarjoaa alarajan todelliselle kustannukselle kohteeseen pääsemiseksi. Varmistamalla, että arvioitu kustannus on aina pienempi tai yhtä suuri kuin todellinen kustannus, algoritmi takaa optimaalisen ratkaisun löytämisen.
Summary
Hakualgoritmeissa käytettävä heuristinen funktio, joka ei koskaan yliarvioi todellista kustannusta päämäärään pääsemiseksi, taaten optimaalisuuden.
Key Concepts
- Alaraja
- Optimaalisuustakuu
- A*-haku
- Kustannusten estimointi
Use Cases
- GPS-reittisuunnittelu
- Palapelien ratkaisu (esim. 8-puzzle)
- Robotin liikkeen suunnittelu esteikkäässä ympäristössä