Αλγόριθμος αναζήτησης: Διαφορά μεταξύ των αναθεωρήσεων

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
JohnMad (συζήτηση | συνεισφορές)
 
Vevek (συζήτηση | συνεισφορές)
Χωρίς σύνοψη επεξεργασίας
Γραμμή 1:
Στην [[Επιστήμη Υπολογιστών]], ένας αλγόριθμος αναζήτησης είναι ένας [[αλγόριθμος]] για την εύρεση ενός αντικειμένου με συγκεκριμένες ιδιότητες μεταξύ μιας συλλογής αντικειμένων. Τα αντικείμενα μπορεί είτε να βρίσκονται αποθηκευμένα ατομικά ως δεδομένα σε μια [[δομή δεδομένων]], ή μπορεί να είναι στοιχεία ενός χώρου αναζήτησης προσδιορισμένου από μια μαθηματική παράσταση ή διαδικασία, όπως οι [[Ρίζα (μαθηματικά)|ρίζες]] μιας [[Εξίσωση|εξίσωσης]] με [[Μεταβλητή (Μαθηματικά)|ακέραιες μεταβλητές]], ή ένας συνδιασμός των δύο, όπως οι [[κύκλοι Hamilton]] ενός [[Γράφος|γράφου]].
#REDIRECT[[Επίλυση προβλημάτων (τεχνητή νοημοσύνη)]]
 
==Κλάσεις αλγορίθμων αναζήτησης==
===Για περιοχές αναζήτησης===
Αλγόριθμοι που αναζητούν λύση σε ένα προσδιορισμένο χώρο έχουν στόχο να βρουν ένα σύνολο απονομής τιμών σε συγκεκριμένες μεταβλητές, που θα ικανοποιήσει συγκεκριμένες μαθηματικές [[Ισότητα (Μαθηματικά)|ισότητες]] ή [[Ανισότητα (Μαθηματικά)|ανισότητες]]. Τέτοιοι αλγόριθμοι χρησιμοποιούνται επίσης όταν στόχος είναι η εύρεση μιας απονομής τιμών που θα [[Βελτιστοποίηση|μεγιστοποιήσουν ή ελαχιστοποιήσουν]] μια συγκεκριμένη συνάρτηση αυτών των μεταβλητών. Σ' αυτήν την κλάση αλγορίθμων συμπεριλαμβάνονται οι βίαιης αναζήτησης (brute-force search) και διάφοροι [[Ευρετική|ευρετικοί]] που εκμεταλλεύονται μερικές πληροφορίες για για τη δομή του χώρου αναζήτησης.
 
Μια σημαντική υποκλάση είναι οι μέθοδοι [[Τοπική αναζήτηση (Βελτιστοποίηση)|τοπικής αναζήτησης]] που ''βλέπουν'' τα στοιχεία του χώρου αναζήτησης ως [[Κόμβος (Θεωρία γράφων)|κορυφές]] ενός [[Γράφος|γραφήματος]], με [[Ακμή (Θεωρία γράφων)ακμές]] ορισμένες από ένα [[σύνολο]] ευρετικών που εφαρμόζονται στην περίπτωση, και σαρώνουν τον χώρο κινούμενες από στοιχείο σε στοιχείο μέσω των ακμών, για παράδειγμα όπως συμβαίνει σε μια [[στοχαστική αναζήτηση]]. Αυτή η κατηγορία περιλαμβάνει μια μεγάλη ποικιλία γενικών μεταευρετικών μεθόδων, όπως είναι οι [[γενετικοί αλγόριθμοι]].
 
Αυτή η κλάση περιλαμβάνει επίσης διάφους αλγόριθμους αναζήτησης [[Δέντρο (δομή δεδομένων)|δέντρων]], που ''βλέπουν'' τα στοιχεία σαν κορυφές δέντρων και διαπερνούν το δέντρο σύμφωνα με μια συγκεκριμένη [[Δέντρο (Θεωρία Γράφων)#Διαπέραση δέντρων|διάταξη]]. Παραδείγματα είναι εξαντλητικές μέθοδοι, όπως η [[αναζήτηση κατά βάθος]] και η [[αναζήτηση κατά πλάτος]], καθώς επίσης και διάφορες βασισμένες στην ευρετική. Σε αντίθεση με τις γενικά μεταευρετικές μεθόδους, που στην καλύτερη περίπτωση λειτουργούν πιθανοτικά, πολλές από αυτές τις μεθόδους αναζήτησης δέντρων εγγυημένα βρίσκουν την ακριβή ή βέλτιστη λύση, δοθέντος κατάλληλου χρόνου.
 
Μια άλλη σημαντική υποκλάση αποτελείται από αλγόριθμους που εξερευνούν το δέντρο παιχνιδιού ενός παιχνιδιού με πολλαπλούς παίκτες, όπως το [[σκάκι]] ή το [[τάβλι]], του οποίου οι κορυφές αποτελούνται από όλες τις δυνατές καταστάσεις στις οποίες θα μπορούσε να μεταβεί το παιχνίδι από την παρούσα κατάσταση. Ο στόχος σ' αυτά τα προβλήματα είναι η εύρεση των κινήσεων που θα παρέχουν την μεγαλύτερη πιθανότητα νίκης, λαμβάνοντας υπόωη όλες τις πιθανές κινήσεις του αντιπάλου. Παρόμοια προβλήματα απαντώνται όταν άνθρωποι ή μηχανές πρέπει να πάρουν διαδοχικές αποφάσεις, των οποίων τα αποτελέσματα δεν εξαρτώνται από έναν, όπως συμβαίνει στην καθοδήγηση [[ρομπότ]] ή στο [[marketing]], στον [[Χρηματοοικονομικά|οικονομικό]] ή στρατιωτικό σχεδιασμό. Αυτό το είδος προβλήματος έχει μελετηθεί εκτεταμένα στο πλαίσιο της [[Τεχνητή νοημοσύνη|τεχνιτής νοημοσύνης]]. Ένα παράδειγμα αλγόριθμου αυτής της κλάσης είναι ο Α*Αλγόριθμος.
 
===Για υποδομές δοσμένης δομής===
Ο όρος ''συνδιαστική αναζήτηση'' χρησιμοποιείται γενικά για αλγόριθμους που αναζητούν σε μια συγκεκριμένη υποδομή μιας διακριτής δομής, όπως ο [[γράφος]], η [[συμβολοσειρά]], μια πεπερασμένη [[Ομάδα (Άλγεβρα)|ομάδα]]. Ο όρος ''συνδιαστική βελτιστοποίηση'' χρησιμοποιείται τυπικά όταν στόχος είναι η εύρεση της υποδομής εκείνης για την οποία μεγιστοποιείται ή ελαχιστοποιείται η τιμή μιας παραμέτρου.