Στη μαθηματική βελτιστοποίηση και την επιστήμη των υπολογιστών, η ευρετική (από τα ελληνικά εὑρίσκω «βρίσκω, ανακαλύπτω») είναι μια τεχνική σχεδιασμένη για την ταχύτερη επίλυση ενός προβλήματος όταν οι κλασικές μέθοδοι είναι πολύ αργές για την εύρεση μιας κατά προσέγγιση λύσης ή όταν οι κλασικές μέθοδοι αποτυγχάνουν να βρουν ακριβή λύση. Αυτό επιτυγχάνεται με τη βέλτιστη συναλλαγή, την πληρότητα, την ακρίβεια ή την ακρίβεια ως προς την ταχύτητα. Κατά κάποιον τρόπο, μπορεί να θεωρηθεί συντόμευση.
Μια ευρετική συνάρτηση, που ονομάζεται επίσης ευρετική, είναι μια συνάρτηση που κατατάσσει εναλλακτικές σε αλγόριθμους αναζήτησης σε κάθε βήμα διακλάδωσης με βάση τις διαθέσιμες πληροφορίες για να αποφασίσει ποιο κλάδο θα ακολουθήσει. Για παράδειγμα, μπορεί να προσεγγίζει την ακριβή λύση.[1]
Ορισμός και κίνητρο
Ο στόχος μιας ευρετικής είναι να παράγει μια λύση σε εύλογο χρονικό πλαίσιο που είναι αρκετά καλή για την επίλυση του προβλήματος. Αυτή η λύση μπορεί να μην είναι η καλύτερη από όλες τις λύσεις σε αυτό το πρόβλημα ή μπορεί απλώς να προσεγγίζει την ακριβή λύση. Αλλά εξακολουθεί να είναι πολύτιμο γιατί η εύρεση του δεν απαιτεί απαγορευτικά μεγάλο χρονικό διάστημα.
Οι ευρετικές μπορεί να παράγουν αποτελέσματα από μόνα τους ή μπορούν να χρησιμοποιηθούν σε συνδυασμό με αλγόριθμους βελτιστοποίησης για τη βελτίωση της αποτελεσματικότητάς τους (π.χ., μπορούν να χρησιμοποιηθούν για τη δημιουργία καλών τιμών σποράς).
Τα αποτελέσματα σχετικά με τη σκληρότητα NP στη θεωρητική επιστήμη των υπολογιστών καθιστούν τα ευρετικά τη μόνη βιώσιμη επιλογή για μια ποικιλία σύνθετων προβλημάτων βελτιστοποίησης που πρέπει να επιλύονται τακτικά σε εφαρμογές πραγματικού κόσμου.
Η ευρετική αποτελεί τη βάση ολόκληρου του πεδίου της Τεχνητής Νοημοσύνης και της προσομοίωσης της σκέψης από υπολογιστή, καθώς μπορεί να χρησιμοποιηθούν σε καταστάσεις όπου δεν υπάρχουν γνωστοί αλγόριθμοι.[2]
Ανταλλαγή
Τα κριτήρια αντιστάθμισης για να αποφασίσετε εάν θα χρησιμοποιήσετε μια ευρετική για την επίλυση ενός δεδομένου προβλήματος περιλαμβάνουν τα ακόλουθα:
Βελτιστότητα: Όταν υπάρχουν πολλές λύσεις για ένα δεδομένο πρόβλημα, η ευρετική εγγυάται ότι θα βρεθεί η καλύτερη λύση; Είναι πράγματι απαραίτητο να βρεθεί η καλύτερη λύση;
Πληρότητα: Όταν υπάρχουν πολλές λύσεις για ένα δεδομένο πρόβλημα, μπορεί ο ευρετικός να τις βρει όλες; Χρειαζόμαστε πραγματικά όλες τις λύσεις; Πολλά ευρετικά προορίζονται να βρουν μόνο μία λύση.
Ακρίβεια και ακρίβεια: Μπορεί η ευρετική να παρέχει ένα διάστημα εμπιστοσύνης για την υποτιθέμενη λύση; Είναι η γραμμή σφάλματος στη λύση αδικαιολόγητα μεγάλη;
Χρόνος εκτέλεσης: Είναι αυτό το πιο γνωστό ευρετικό για την επίλυση αυτού του τύπου προβλήματος; Ορισμένα ευρετικά συγκλίνουν πιο γρήγορα από άλλα. Ορισμένα ευρετικά είναι μόνο οριακά ταχύτερα από τις κλασικές μεθόδους, οπότε η «επιβάρυνση» για τον υπολογισμό του ευρετικού μπορεί να έχει αρνητικό αντίκτυπο.
Σε ορισμένες περιπτώσεις, μπορεί να είναι δύσκολο να αποφασιστεί εάν η λύση που βρέθηκε από την ευρετική είναι αρκετά καλή, επειδή η θεωρία στην οποία βασίζεται η ευρετική δεν είναι πολύ περίπλοκη.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
