Σε έναν άπληστο Αλγόριθμο, κάνουμε όποια επιλογή φαίνεται καλύτερη αυτή τη στιγμή με την ελπίδα ότι θα οδηγήσει σε παγκόσμια βέλτιστη λύση. Στον Δυναμικό Προγραμματισμό λαμβάνουμε αποφάσεις σε κάθε βήμα λαμβάνοντας υπόψη το τρέχον πρόβλημα και τη λύση στο προηγουμένως λυμένο υποπρόβλημα για να υπολογίσουμε τη βέλτιστη λύση.
Πόσες εφικτές λύσεις υπάρχουν στην άπληστη μέθοδο;
Ένας αλγόριθμος Greedy κάνει άπληστες επιλογές σε κάθε βήμα για να διασφαλίσει ότι η αντικειμενική συνάρτηση είναι βελτιστοποιημένη. Ο αλγόριθμος Greedy έχει μόνο μία βολή για να υπολογίσει τη βέλτιστη λύση, ώστε να μην επιστρέψει ποτέ πίσω και να αντιστρέψει την απόφαση.
Ποια είναι η έννοια της άπληστης μεθόδου;
Ορισμός: Ένας αλγόριθμος που λαμβάνει πάντα την καλύτερη άμεση ή τοπική λύση ενώ βρίσκει μια απάντηση. Οι άπληστοι αλγόριθμοι βρίσκουν τη συνολική ή συνολικά τη βέλτιστη λύση για ορισμένα προβλήματα βελτιστοποίησης, αλλά μπορεί να βρουν λιγότερο από βέλτιστες λύσεις για ορισμένες περιπτώσεις άλλων προβλημάτων.
Ποια είναι τα οφέλη της άπληστης προσέγγισης;
Το πλεονέκτημα της χρήσης ενός άπληστου αλγόριθμου είναι ότι οι λύσεις σε μικρότερες περιπτώσεις του προβλήματος μπορούν να είναι απλές και κατανοητές. Το μειονέκτημα είναι ότι είναι απολύτως πιθανό οι βέλτιστες βραχυπρόθεσμες λύσεις να οδηγήσουν στο χειρότερο δυνατό μακροπρόθεσμο αποτέλεσμα.
Πότε πρέπει να χρησιμοποιούμε το greedy;
Παρακάτω αναφέρονται ορισμένα προβλήματα που χρησιμοποιούν τη βέλτιστη λύση χρησιμοποιώντας την προσέγγιση Greedy
- Πρόβλημα με τον ταξιδιώτη πωλητή.
- Αλγόριθμος ελάχιστων δέντρων της Kruskal.
- Αλγόριθμος ελάχιστης έκτασης δέντρου της Dijkstra.
- Πρόβλημα με σακίδιο.
- Πρόβλημα προγραμματισμού εργασιών.
