.
Ένας άπληστος αλγόριθμος είναι οποιοσδήποτε αλγόριθμος που ακολουθεί την ευρετική επίλυση προβλημάτων της λήψης της τοπικά βέλτιστης επιλογής σε κάθε στάδιο. Σε πολλά προβλήματα, μια άπληστη στρατηγική δεν παράγει μια βέλτιστη λύση, αλλά μια άπληστη ευρετική μπορεί να δώσει τοπικά βέλτιστες λύσεις που προσεγγίζουν μια παγκόσμια βέλτιστη λύση σε εύλογο χρονικό διάστημα.
'Απληστος αλγόριθμος που καθορίζει τον ελάχιστο αριθμό νομισμάτων που πρέπει να δοθούν κατά την αλλαγή. Αυτά είναι τα βήματα που θα έπαιρναν οι περισσότεροι για να μιμηθούν έναν άπληστο αλγόριθμο που αντιπροσωπεύει 36 σεντ χρησιμοποιώντας μόνο νομίσματα με τιμές {1, 5, 10, 20}. Το νόμισμα της υψηλότερης αξίας, μικρότερη από την υπόλοιπη οφειλόμενη μεταβολή, είναι το τοπικό βέλτιστο. (Γενικά, το πρόβλημα της αλλαγής απαιτεί δυναμικό προγραμματισμό για να βρεθεί μια βέλτιστη λύση· ωστόσο, τα περισσότερα νομισματικά συστήματα είναι ειδικές περιπτώσεις όπου η άπληστη στρατηγική βρίσκει τη βέλτιστη λύση.)
Για παράδειγμα, μια άπληστη στρατηγική για το πρόβλημα του ταξιδιώτη πωλητή (το οποίο είναι υψηλής υπολογιστικής πολυπλοκότητας) είναι η ακόλουθη ευρετική: "Σε κάθε βήμα του ταξιδιού, επισκεφθείτε την πλησιέστερη χωρίς επίσκεψη πόλη ." Αυτό το ευρετικό δεν σκοπεύει να βρει την καλύτερη λύση, αλλά τελειώνει σε έναν εύλογο αριθμό βημάτων. Η εύρεση μιας βέλτιστης λύσης σε ένα τόσο περίπλοκο πρόβλημα απαιτεί συνήθως αδικαιολόγητα πολλά βήματα. Στη μαθηματική βελτιστοποίηση, οι άπληστοι αλγόριθμοι λύνουν βέλτιστα συνδυαστικά προβλήματα που έχουν τις ιδιότητες των μητροειδών και δίνουν προσεγγίσεις σταθερών παραγόντων στα προβλήματα βελτιστοποίησης με την υποαρθρωτή δομή.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
