Αλγόριθμος αναζήτησης
 |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Στη θεωρητική πληροφορική, ένας αλγόριθμος αναζήτησης είναι ένας αλγόριθμος για την εύρεση ενός αντικειμένου με συγκεκριμένες ιδιότητες μεταξύ μιας συλλογής αντικειμένων. Τα αντικείμενα μπορεί είτε να βρίσκονται αποθηκευμένα ατομικά ως δεδομένα σε μια δομή δεδομένων, ή μπορεί να είναι στοιχεία ενός χώρου αναζήτησης προσδιορισμένου από μια μαθηματική παράσταση ή διαδικασία, όπως οι ρίζες μιας εξίσωσης με ακέραιες μεταβλητές, ή ένας συνδυασμός των δύο, όπως οι κύκλοι Hamilton ενός γράφου.
Κλάσεις αλγορίθμων αναζήτησης
[Επεξεργασία | επεξεργασία κώδικα]Για περιοχές αναζήτησης
[Επεξεργασία | επεξεργασία κώδικα]Αλγόριθμοι που αναζητούν λύση σε ένα προσδιορισμένο χώρο χρησιμοποιούνται συχνά σε προβλήματα ικανοποίησης περιορισμών, που στόχο έχουν να βρουν ένα σύνολο απονομής τιμών σε συγκεκριμένες μεταβλητές, που θα ικανοποιήσει συγκεκριμένες μαθηματικές ισότητες ή ανισότητες. Τέτοιοι αλγόριθμοι χρησιμοποιούνται επίσης όταν στόχος είναι η εύρεση μιας απονομής τιμών που θα μεγιστοποιήσουν ή ελαχιστοποιήσουν μια συγκεκριμένη συνάρτηση αυτών των μεταβλητών. Σ' αυτήν την κλάση αλγορίθμων συμπεριλαμβάνονται οι τυφλής αναζήτησης (brute-force search) και διάφοροι ευρετικοί που εκμεταλλεύονται μερικές πληροφορίες για για τη δομή του χώρου αναζήτησης.
Μια σημαντική υποκλάση είναι οι μέθοδοι τοπικής αναζήτησης που βλέπουν τα στοιχεία του χώρου αναζήτησης ως κορυφές ενός γραφήματος, με ακμές ορισμένες από ένα σύνολο ευρετικών που εφαρμόζονται στην περίπτωση, και σαρώνουν τον χώρο κινούμενες από στοιχείο σε στοιχείο μέσω των ακμών, για παράδειγμα όπως συμβαίνει σε μια στοχαστική αναζήτηση. Αυτή η κατηγορία περιλαμβάνει μια μεγάλη ποικιλία γενικών μεταευρετικών μεθόδων, όπως είναι οι γενετικοί αλγόριθμοι.
Αυτή η κλάση περιλαμβάνει επίσης διάφορους αλγόριθμους αναζήτησης δέντρων, που βλέπουν τα στοιχεία σαν κορυφές δέντρων και διατρέχουν το δέντρο σύμφωνα με μια συγκεκριμένη διάταξη. Παραδείγματα είναι εξαντλητικές μέθοδοι, όπως η αναζήτηση κατά βάθος και η αναζήτηση κατά πλάτος, καθώς επίσης και διάφορες βασισμένες στην ευρετική. Σε αντίθεση με τις γενικά μεταευρετικές μεθόδους, που στην καλύτερη περίπτωση λειτουργούν πιθανοτικά, πολλές από αυτές τις μεθόδους αναζήτησης δέντρων εγγυημένα βρίσκουν την ακριβή ή βέλτιστη λύση, δοθέντος κατάλληλου χρόνου.
Μια άλλη σημαντική υποκλάση αποτελείται από αλγόριθμους που εξερευνούν το δέντρο παιχνιδιού ενός παιχνιδιού με πολλαπλούς παίκτες, όπως το σκάκι ή το τάβλι, του οποίου οι κορυφές αποτελούνται από όλες τις δυνατές καταστάσεις στις οποίες θα μπορούσε να μεταβεί το παιχνίδι από την παρούσα κατάσταση. Ο στόχος σ' αυτά τα προβλήματα είναι η εύρεση των κινήσεων που θα παρέχουν την μεγαλύτερη πιθανότητα νίκης, λαμβάνοντας υπόψη όλες τις πιθανές κινήσεις του αντιπάλου. Παρόμοια προβλήματα απαντώνται όταν άνθρωποι ή μηχανές πρέπει να πάρουν διαδοχικές αποφάσεις, των οποίων τα αποτελέσματα δεν εξαρτώνται από έναν, όπως συμβαίνει στην καθοδήγηση ρομπότ ή στο marketing, στον οικονομικό ή στρατιωτικό σχεδιασμό. Αυτό το είδος προβλήματος έχει μελετηθεί εκτεταμένα στο πλαίσιο της τεχνητής νοημοσύνης. Ένα παράδειγμα αλγόριθμου αυτής της κλάσης είναι ο αλγόριθμος Α*.
Για υποδομές δοσμένης δομής
[Επεξεργασία | επεξεργασία κώδικα]Ο όρος συνδυαστική αναζήτηση χρησιμοποιείται γενικά για αλγόριθμους που αναζητούν σε μια συγκεκριμένη υποδομή μιας διακριτής δομής, όπως ο γράφος, η συμβολοσειρά, μια πεπερασμένη ομάδα. Ο όρος συνδυαστική βελτιστοποίηση χρησιμοποιείται τυπικά όταν στόχος είναι η εύρεση της υποδομής εκείνης για την οποία μεγιστοποιείται ή ελαχιστοποιείται η τιμή μιας παραμέτρου. (Επειδή η υποδομή συνήθως αναπαρίσταται στον υπολογιστή από ένα σύνολο ακεραίων μεταβλητών με περιορισμούς, αυτά τα προβλήματα μπορούν να ειδωθούν ως ειδικές περιπτώσεις ικανοποίησης περιορισμών ή διακριτής βελτιστοποίησης. Αλλά συνήθως εκφράζονται και λύνονται με μια πιο αφηρημένη σκοπιά, χωρίς να γίνεται εκτενής αναφορά στην αναπαράσταση των δεδομένων).
Μια σημαντική και αρκετά μελετημένη υποκλάση είναι οι αλγόριθμοι γράφων, συγκεκριμένα οι αλγόριθμοι διαπέρασης γράφων, για την εύρεση συγκεκριμένων υποδομών ενός γράφου, όπως οι υπογράφοι, τα μονοπάτια, οι κύκλοι, κλπ. Παραδείγματα περιλαμβάνουν τον αλγόριθμου του Dijkstra, του Kruskal και του Prim.
Μια ακόμη σημαντική υποκλάση είναι οι αλγόριθμοι αναζήτησης συμβολοσειρών, που αναζητούν μοτίβα μέσα σε συμβολοσειρές.
Αναζήτηση ακρότατου συνάρτησης
[Επεξεργασία | επεξεργασία κώδικα]Το 1953, ο J. Kiefer επινόησε την αναζήτηση Fibonacci που μπορεί να χρησιμοποιηθεί για την εύρεση του μέγιστου μιας μονοκόρυφης συνάρτησης, η οποία βρίσκει πολλές εφαρμογές στην επιστήμη υπολογιστών.
Για κβαντικούς υπολογιστές
[Επεξεργασία | επεξεργασία κώδικα]Υπάρχουν επίσης μέθοδοι αναζήτησης σχεδιασμένοι για κβαντικούς υπολογιστές, όπως ο αλγόριθμος του Grover, που θεωρητικά είναι ταχύτερες από την γραμμική ή τυφλή αναζήτηση, ακόμα και χωρίς τη βοήθεια δομών δεδομένων ή ευρετικών.
Δείτε επίσης
[Επεξεργασία | επεξεργασία κώδικα]- Αλγόριθμοι ταξινόμησης, απαραίτητοι για τη λειτουργία κάποιων αλγορίθμων αναζήτησης.
- Μηχανή αναζήτησης
Αναφορές
[Επεξεργασία | επεξεργασία κώδικα]- Donald Knuth. The Art of Computer Programming. Volume 3: Sorting and Searching. ISBN 0-201-89685-0.
