Ευρετικές Μέθοδοι

Στην επίλυση προβλημάτων βελτιστοποίησης εφαρμόζονται κυρίως διάφοροι ακριβείς αλγόριθμοι μαθηματικού προγραμματισμού. Ωστόσο, σε προβλήματα συνδυαστικής ή ολικής βελτιστοποίησης οι συμβατικές μέθοδοι δεν είναι συνήθως αρκετά αποτελεσματικές, ειδικά, όταν ο χώρος αναζήτησης του προβλήματος είναι μεγάλος και πολύπλοκος. Η πλειοψηφία αυτών των υπολογιστικών προβλημάτων ανήκουν στην κλάση NP-hard, και δεν είναι δυνατή η εύρεση λύσης σε πολυωνυμικό χρόνο (εκτός αν P = NP).

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