Επιτρεπτή ευριστική συνάρτηση
term_id: admissible_heuristic
Category: basic_concepts
Definition
Σε προβλήματα εύρεσης διαδρομής και αναζήτησης, μια επιτρεπτή ευριστική συνάρτηση παρέχει ένα κάτω φράγμα για το πραγματικό κόστος για την επίτευξη του κόμβου στόχου. Εγγυώμενη ότι το εκτιμώμενο κόστος είναι πάντα μικρότερο ή ίσο με το πραγματικό κόστος, διασφαλίζει ότι οι αλγόριθμοι όπως ο A* θα βρουν τη βέλτιστη λύση.
Summary
Μια ευριστική συνάρτηση σε αλγορίθμους αναζήτησης που δεν υπερτιμά ποτέ το πραγματικό κόστος για την επίτευξη του στόχου, εξασφαλίζοντας βελτιστότητα.
Key Concepts
- Κάτω φράγμα
- Εγγύηση βελτιστότητας
- Αναζήτηση A*
- Εκτίμηση κόστους
Use Cases
- Σχεδιασμός διαδρομών σε συστήματα GPS
- Επίλυση παζλ (π.χ. παζλ 8 κομματιών)
- Σχεδιασμός κίνησης ρομπότ σε περιβάλλοντα με εμπόδια