Οι αλγορίθμους απληστίας είναι ένας τύπος αλγοριθμικής στρατηγικής που κάνει τη βέλτιστη επιλογή σε κάθε βήμα με την ελπίδα να βρει το βέλτιστο παγκόσμιο. Χρησιμοποιούνται ευρέως στην επίλυση προβλημάτων βελτιστοποίησης όπου οι τοπικές αποφάσεις οδηγούν σε μια παγκόσμια βέλτιστη λύση. Αυτό το άρθρο διερευνά την έννοια των άπληστων αλγορίθμων, παρέχει πρακτικά παραδείγματα και δείχνει πώς να εκτελέσει σχετικούς υπολογισμούς.

Τι Είναι οι Αλγόριθμοι της Απληστίας;

Ένας άπληστος αλγόριθμος δημιουργεί μια λύση κομμάτι κομμάτι, επιλέγοντας πάντα το επόμενο κομμάτι που προσφέρει το πιο άμεσο όφελος. Αυτή η προσέγγιση είναι απλή και αποτελεσματική αλλά δεν εγγυάται πάντα την καλύτερη συνολική λύση για όλα τα προβλήματα.

Πρακτικά Παραδείγματα

Τα κοινά προβλήματα που λύνονται με τη χρήση άπληστων αλγορίθμων περιλαμβάνουν το πρόβλημα αλλαγής νομισμάτων, την επιλογή δραστηριότητας και το πρόβλημα κλασματικού knapsack. Αυτά τα παραδείγματα δείχνουν πώς κάνοντας τοπικά βέλτιστες επιλογές μπορεί να οδηγήσει σε μια παγκόσμια βέλτιστη λύση σε συγκεκριμένα σενάρια.

Υπολογισμός και εφαρμογή

Ας υποθέσουμε ότι οι ονομαστικές αξίες των νομισμάτων είναι 1, 5, 10 και 25 σεντς, και το ποσό-στόχος είναι 63 σεντς.

Υπολογισμός βήμα προς βήμα:

  • Επιλέξτε 25 λεπτά (μείναμε: 63 - 25 = 38)
  • Επιλέξτε 25 λεπτά (απομένουν: 38 - 25 = 13)
  • Επιλέξτε 10 λεπτά (απομένουν: 13 - 10 = 3)
  • Επιλέξτε 1 λεπτό (απομένουν: 3 - 1 = 2)
  • Επιλέξτε 1 λεπτό (απομένουν: 2 - 1 = 1)
  • Επιλέξτε 1 λεπτό (απομένουν: 1 - 1 = 0)

Συνολικά χρησιμοποιούμενα κέρματα: 6.