Σε αυτό το σεμινάριο, θα μάθετε τι είναι ένας άπληστος αλγόριθμος. Επίσης, θα βρείτε ένα παράδειγμα άπληστης προσέγγισης.
Ένας άπληστος αλγόριθμος είναι μια προσέγγιση για την επίλυση ενός προβλήματος επιλέγοντας την καλύτερη διαθέσιμη λύση αυτή τη στιγμή, χωρίς να ανησυχείτε για το μελλοντικό αποτέλεσμα που θα φέρει. Με άλλα λόγια, οι τοπικά καλύτερες επιλογές στοχεύουν στην παραγωγή καλύτερων αποτελεσμάτων παγκοσμίως.
Αυτός ο αλγόριθμος μπορεί να μην είναι η καλύτερη επιλογή για όλα τα προβλήματα. Ενδέχεται να έχει λανθασμένα αποτελέσματα σε ορισμένες περιπτώσεις.
Αυτός ο αλγόριθμος δεν επιστρέφει ποτέ για να αντιστρέψει την απόφαση που έχει ληφθεί. Αυτός ο αλγόριθμος λειτουργεί με προσέγγιση από πάνω προς τα κάτω.
Το κύριο πλεονέκτημα αυτού του αλγορίθμου είναι:
- Ο αλγόριθμος είναι πιο εύκολο να περιγραφεί .
- Αυτός ο αλγόριθμος μπορεί να αποδώσει καλύτερα από άλλους αλγόριθμους (αλλά όχι σε όλες τις περιπτώσεις).
Εφικτή λύση
Μια εφικτή λύση είναι αυτή που παρέχει τη βέλτιστη λύση στο πρόβλημα.
Άπληστος αλγόριθμος
- Κατ 'αρχάς, το σύνολο λύσεων (που περιέχει απαντήσεις) είναι κενό.
- Σε κάθε βήμα, ένα στοιχείο προστίθεται στο σύνολο λύσεων.
- Εάν το σύνολο λύσεων είναι εφικτό, το τρέχον στοιχείο διατηρείται.
- Διαφορετικά, το αντικείμενο απορρίπτεται και δεν εξετάζεται ποτέ ξανά.
Παράδειγμα - Άπληστη προσέγγιση
Πρόβλημα: Πρέπει να κάνετε μια αλλαγή ποσού χρησιμοποιώντας τον μικρότερο δυνατό αριθμό κερμάτων. Ποσό: 28 $ Διαθέσιμα νομίσματα: κέρμα 5 $ $ 2 κέρμα $ 1 κέρμα
Λύση:
- Δημιουργήστε ένα κενό σύνολο λύσεων = ().
- νομίσματα = (5, 2, 1)
- άθροισμα = 0
- Ενώ το άθροισμα ≠ 28, κάντε τα εξής.
- Επιλέξτε ένα νόμισμα C από κέρματα έτσι ώστε το άθροισμα + C <28.
- Εάν C + άθροισμα> 28, επιστρέψτε καμία λύση.
- Άλλο, άθροισμα = άθροισμα + C.
- Προσθέστε C στο σύνολο λύσεων.
Μέχρι τις 5 πρώτες επαναλήψεις, το σύνολο λύσεων περιέχει 5 $ 5 κέρματα. Μετά από αυτό, παίρνουμε κέρμα 1 $ 2 και τέλος, κέρμα 1 $ 1.
Άπληστες εφαρμογές αλγορίθμου
- Ταξινόμηση επιλογής
- Πρόβλημα σακιδίων
- Ελάχιστο δέντρο έκτασης
- Πρόβλημα συντομότερης διαδρομής μίας πηγής
- Πρόβλημα προγραμματισμού εργασίας
- Αλγόριθμος Minimal Spanning Tree Prim
- Ο αλγόριθμος του ελάχιστου ανοίγματος του Kruskal
- Ο ελάχιστος αλγόριθμος δέντρου της Dijkstra
- Κωδικοποίηση Huffman
- Αλγόριθμος Ford-Fulkerson
