4.5 Άπληστη μέθοδος

Σε πολλά προβλήματα βελτιστοποίησης, όπου απαιτείται να βρεθεί η μέγιστη ή η ελάχιστη τιμή ενός μεγέθους, χρησιμοποιείται μία μέθοδος, που δεν βρίσκει πράγματι τη βέλτιστη λύση, αλλά σκοπός της είναι να την προσεγγίσει. Συνήθως, οι αλγόριθμοι αυτού του τύπου προχωρούν με βάση σταδιακές επιλογές που αφορούν στο βέλτιστο κάθε βήματος, χωρίς μέριμνα για το τελικό βέλτιστο. Έτσι η λειτουργία τους είναι παρόμοια με τις κινήσεις ενός παίκτη στο σκάκι που σκέφτεται και επιλέγει την επόμενη κίνηση χωρίς να τον απασχολούν οι επόμενες κινήσεις ούτε του αντιπάλου ούτε οι δικές του. Η πρώτη προσέγγιση στο παράδειγμα του ταχυδρόμου, το οποίο περιγράφεται στο Κεφάλαιο 4.1, ανήκει στην κατηγορία αυτή. Η μέθοδος αυτή που είναι γνωστή και ως "άπληστη μέθοδος" (greedy method), μπορεί να τυποποιηθεί σύμφωνα με τις εξής δύο παραδοχές: - σε κάθε βήμα επιλογή της τρέχουσας βέλτιστης επιλογής - επιβεβαίωση ότι αυτή η προσέγγιση εγγυάται τη συνολική βέλτιστη λύση (όταν ο αλγόριθμος δεν χρησιμοποιείται ως μια απλή ευριστική προσεγγιστική τακτική).

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