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

Ιστορικό

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

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

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

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

Ωστόσο, η χρήση ευρετικών μεθόδων σε ορισμένους πολύ τεχνικούς τομείς μπορεί να είναι επιζήμια - η επιστήμη των υπολογιστών είναι ένα παράδειγμα. Ο προγραμματισμός ενός υπολογιστή ώστε να εκτελεί περισσότερο ή λιγότερο τις επιθυμητές ενέργειες μπορεί να οδηγήσει σε σοβαρές δυσλειτουργίες. Ως εκ τούτου, οι εργασίες στον υπολογιστή πρέπει γενικά να είναι αρκετά ακριβείς. Ωστόσο, υπάρχουν ορισμένοι τομείς στους οποίους οι υπολογιστές μπορούν να υπολογίζουν ευρετικές λύσεις με ασφάλεια - για παράδειγμα, η τεχνολογία αναζήτησης της Google βασίζεται σε μεγάλο βαθμό σε ευρετικές λύσεις, παράγοντας "σχεδόν άστοχες" αντιστοιχίες σε ένα ερώτημα αναζήτησης όταν δεν μπορεί να βρεθεί ακριβής αντιστοιχία. Αυτό επιτρέπει στον χρήστη να διορθώσει τυχόν λάθη που παράγει η αναζήτηση. Παράδειγμα: Αναζητώντας το όνομα "Peter Smith" και μη μπορώντας να βρει το ακριβές όνομα, η μηχανή αναζήτησης ταιριάζει ευρετικά με το "Pete Smith" και το άτομο που χρησιμοποιεί τη μηχανή αναζήτησης πρέπει να αποφασίσει αν ο Pete και ο Peter είναι το ίδιο άτομο.

Παραδείγματα

Polya

Ακολουθούν μερικές άλλες ευρέως χρησιμοποιούμενες ευρετικές μέθοδοι, από το βιβλίο του Polya του 1945, How to Solve It:

• Αν δυσκολεύεστε να κατανοήσετε ένα πρόβλημα, δοκιμάστε να ζωγραφίσετε μια εικόνα.
• Αν δεν μπορείτε να βρείτε μια λύση, προσπαθήστε να υποθέσετε ότι έχετε μια λύση και να δείτε τι μπορείτε να αντλήσετε από αυτήν ("δουλεύοντας προς τα πίσω").
• Αν το πρόβλημα είναι αφηρημένο, προσπαθήστε να εξετάσετε ένα συγκεκριμένο παράδειγμα.
• Δοκιμάστε πρώτα να λύσετε ένα γενικότερο πρόβλημα: το "παράδοξο του εφευρέτη": το πιο φιλόδοξο σχέδιο μπορεί να έχει περισσότερες πιθανότητες επιτυχίας.

Πρόβλημα συσκευασίας

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

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

Επομένως, πρόκειται για μια ευρετική λύση.

Παράδειγμα προβλήματος συσκευασίας. Πρόκειται για ένα μονοδιάστατο πρόβλημα (με περιορισμούς) Knapsack: ποια κουτιά πρέπει να επιλεγούν ώστε να μεγιστοποιηθεί το χρηματικό ποσό και να διατηρηθεί το συνολικό βάρος κάτω από 15 kg; Ένα πολυδιάστατο πρόβλημα θα μπορούσε να εξετάσει την πυκνότητα ή τις διαστάσεις των κιβωτίων, το τελευταίο αποτελεί τυπικό πρόβλημα συσκευασίας. ( Η λύση στην περίπτωση αυτή είναι να επιλεγούν όλα τα κουτιά εκτός από το πράσινο).