Αλγόριθμος αναζήτησης: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Vevek (συζήτηση | συνεισφορές) |
Vevek (συζήτηση | συνεισφορές) |
||
Γραμμή 5:
Αλγόριθμοι που αναζητούν λύση σε ένα προσδιορισμένο χώροχρησιμοποιούνται συχνά σε προβλήματα ικανοποίησης περιορισμών, που στόχο έχουν να βρουν ένα σύνολο απονομής τιμών σε συγκεκριμένες μεταβλητές, που θα ικανοποιήσει συγκεκριμένες μαθηματικές [[Ισότητα (Μαθηματικά)|ισότητες]] ή [[Ανισότητα (Μαθηματικά)|ανισότητες]]. Τέτοιοι αλγόριθμοι χρησιμοποιούνται επίσης όταν στόχος είναι η εύρεση μιας απονομής τιμών που θα [[Βελτιστοποίηση|μεγιστοποιήσουν ή ελαχιστοποιήσουν]] μια συγκεκριμένη συνάρτηση αυτών των μεταβλητών. Σ' αυτήν την κλάση αλγορίθμων συμπεριλαμβάνονται οι βίαιης αναζήτησης (brute-force search) και διάφοροι [[Ευρετική|ευρετικοί]] που εκμεταλλεύονται μερικές πληροφορίες για για τη δομή του χώρου αναζήτησης.
Μια σημαντική υποκλάση είναι οι μέθοδοι [[Τοπική αναζήτηση (Βελτιστοποίηση)|τοπικής αναζήτησης]] που ''βλέπουν'' τα στοιχεία του χώρου αναζήτησης ως [[Κόμβος (Θεωρία γράφων)|κορυφές]] ενός [[Γράφος|γραφήματος]], με [[Ακμή (Θεωρία γράφων)|ακμές]] ορισμένες από ένα [[σύνολο]] ευρετικών που εφαρμόζονται στην περίπτωση, και σαρώνουν τον χώρο κινούμενες από στοιχείο σε στοιχείο μέσω των ακμών, για παράδειγμα όπως συμβαίνει σε μια [[στοχαστική αναζήτηση]]. Αυτή η κατηγορία περιλαμβάνει μια μεγάλη ποικιλία γενικών μεταευρετικών μεθόδων, όπως είναι οι [[γενετικοί αλγόριθμοι]].
Αυτή η κλάση περιλαμβάνει επίσης διάφους αλγόριθμους αναζήτησης [[Δέντρο (δομή δεδομένων)|δέντρων]], που ''βλέπουν'' τα στοιχεία σαν κορυφές δέντρων και διαπερνούν το δέντρο σύμφωνα με μια συγκεκριμένη [[Δέντρο (Θεωρία Γράφων)#Διαπέραση δέντρων|διάταξη]]. Παραδείγματα είναι εξαντλητικές μέθοδοι, όπως η [[αναζήτηση κατά βάθος]] και η [[αναζήτηση κατά πλάτος]], καθώς επίσης και διάφορες βασισμένες στην ευρετική. Σε αντίθεση με τις γενικά μεταευρετικές μεθόδους, που στην καλύτερη περίπτωση λειτουργούν πιθανοτικά, πολλές από αυτές τις μεθόδους αναζήτησης δέντρων εγγυημένα βρίσκουν την ακριβή ή βέλτιστη λύση, δοθέντος κατάλληλου χρόνου.
| |||