Πίνακας περιεχομένων:
Ορισμός - Τι σημαίνει Hill Climbing;
Η αναρρίχηση σε λόφο είναι μια μαθηματική βελτιστοποίηση που χρησιμοποιείται για την επίλυση υπολογιστικών προβλημάτων που έχουν πολλαπλές λύσεις. Πρόκειται για μια επαναληπτική μέθοδο που ανήκει στην τοπική οικογένεια αναζήτησης και ξεκινά με μια τυχαία λύση και στη συνέχεια βελτιώνει διαδοχικά την λύση αυτή ένα στοιχείο κάθε φορά μέχρι να φτάσει σε μια περισσότερο ή λιγότερο βελτιστοποιημένη λύση.
Η Techopedia εξηγεί το Hill Climbing
Η αναρρίχηση σε λόφο είναι μια τεχνική βελτιστοποίησης που χρησιμοποιείται για να βρει μια "τοπική βέλτιστη" λύση σε ένα υπολογιστικό πρόβλημα. Ξεκινάει με μια λύση που είναι πολύ φτωχή σε σύγκριση με τη βέλτιστη λύση και στη συνέχεια βελτιώνεται διαδοχικά από εκεί. Αυτό επιτυγχάνεται με τη δημιουργία λύσεων "γειτονικών" που είναι σχετικά βήμα καλύτερα από την τρέχουσα λύση, επιλέγει το καλύτερο και στη συνέχεια επαναλαμβάνει τη διαδικασία έως ότου φθάσει στην βέλτιστη λύση, επειδή δεν μπορεί πλέον να βρει βελτιώσεις.
Παραλλαγές:
- Απλή - Επιλέγεται ο πρώτος πλησιέστερος κόμβος ή λύση που θα βρεθεί.
- Απότομη ανάβαση - Λαμβάνονται υπόψη όλες οι διαθέσιμες διαδοχικές λύσεις και στη συνέχεια επιλέγεται το πλησιέστερο.
- Στοχαστική - Επιλέγεται τυχαία μια λύση γείτονος και στη συνέχεια αποφασίζεται εάν θα μεταφερθεί ή όχι στη λύση αυτή με βάση την ποσότητα βελτίωσης σε σχέση με τον τρέχοντα κόμβο.
Η αναρρίχηση του λόφου πραγματοποιείται επαναληπτικά - περνάει μια ολόκληρη διαδικασία και αποθηκεύεται η τελική λύση. Εάν μια διαφορετική επανάληψη βρίσκει μια καλύτερη τελική λύση, η αποθηκευμένη λύση ή κατάσταση αντικαθίσταται. Αυτό ονομάζεται επίσης ορειβασία λόφων κυνηγετικών όπλων, καθώς απλώς δοκιμάζει διαφορετικά μονοπάτια έως ότου χτυπά το καλύτερο, όπως και το πώς ένα καραμπίνα είναι ανακριβές, αλλά μπορεί ακόμα να χτυπήσει το στόχο του λόγω της μεγάλης εξάπλωσης των βλημάτων. Αυτό λειτουργεί πολύ καλά σε πολλές περιπτώσεις, επειδή σε αυτό αποδεικνύεται, είναι καλύτερο να δαπανήσει πόρους CPU διερευνά διαφορετικές διαδρομές από προσεκτικά βελτιστοποίηση από μια αρχική κατάσταση.
