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