Eutopia

Αλγόριθμοι Αναζήτησης TN

Στόχος της αναζήτησης είναι να βρεθούν λύσεις στα προβλήματα που αναπαριστούνται με γράφους ή δέντρα. Για να επιλύσει ένας ευφυής πράκτορας ένα πρόβλημα πρέπει να είναι καλά ορισμένο. Αρκεί ο πράκτορας να γνωρίζει:

• την αρχική κατάσταση στην οποία βρίσκεται

• όλες τις δυνατές ενέργειες που έχει στη διάθεσή του. Δηλαδή να υπάρχει μία συνάρτηση διαδόχων (successor function), η οποία να αντιστοιχεί κάθε δυνατή ενέργεια σε κάποια διάδοχή κατάσταση.

  • (Λέμε ότι η αρχική κατάσταση και η συνάρτηση διαδόχψν ορίζουν το χώρο των καταστάσεων (state space) - το σύνολο δηλαδή των καταστάσεων που είναι προσπελάσιμες από την αρχική κατάσταση)

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

• μια συνάρτηση κόστους διαδρομής (path cost), που αποδίδει ένα αριθμητικό κόστος στην κάθε διαδρομή που ακολουθείται (ή που αξιολογεί την κατάσταση στην οποία βρίσκεται ο πράκτορας).

Οι αλγόριθμοι που παρουσιάζονται είναι χωρισμένοι σε δύο κατηγορίες:

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

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

Uninformed (or Blind) Search Algorithms

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

Breadth-first search (BFS)

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

Χρονική και Χωρική πολυπλοκότητα: O(b^d+1) με b: παράγοντας διακλάδωσης, d: βάθος

[wiki] [applet]

Uniform-cost search

Ξεκινώντας από τον κόμβο-ρίζα, επεκτείνεται κάθε φορά ο κόμβος με το μικρότερο κόστος διαδρομής. Αν τα κόστη κάθε διαδρομής είναι ίσα, η αναζήτηση ομοιόμορφου κόστους ταυτίζεται με την BFS. Ο αλγόριθμος, με την προϋπόθεση ότι δεν υπάρχουν ενέργειες διαδοχής με μηδενικό κόστος (κάτι που θα τον παγίδευε σε μια κατάσταση), είναι πλήρης και επειδή εξετάζει τους κόμβους με σειρά αυξανόμενου κόστους διαδρομής είναι και βέλτιστος. Επειδή, ο αλγόριθμος λαμβάνει υπόψιν του μόνο τα κόστη των διαδρομών είναι δύσκολο να υπολογίσουμε την πολυπλοκότητά του συναρτήσει του βάθους (d)

Χωρική και Χρονική πολυπλοκότητα: O(b^1+[C*/ε]) με C*: κόστος της βέλτιστης λύσης και ε: ελάχιστο κόστος ενέργειας. Αυτό μπορεί να είναι πολύ μεγαλύτερο του BFS σε πολύ μεγάλα δέντρα και όταν ακολουθούνται μικρές διαδρομές/βήματα.

[wiki]

Depth-first search (DFS)

Ίσως ο πιο δημοφιλής αλγόριθμος τυφλής αναζήτησης, κυρίως λόγω των πολλών και χρήσιμων παραλλαγών του. Ξεκινώντας από την ρίζα επεκτείνεται πάντα ο βαθύτερος κόμβος. Όταν ο κόμβος δεν έχει διαδόχους, τότε η αναζήτηση "υποχωρεί" στον αμέσως ρηχότερο κόμβo. Η εικόνα δείχνει τους κόμβους με σειρά επίσκεψης. Ο αλγόριθμος είναι μη πλήρης (γιατί μπορεί να παγιδευτεί σε άπειρα κλαδιά) και μη βέλτιστος (γιατί μπορεί να μη βρει εναλλακτική λύση σε μικρότερο βάθος)

Χρονική πολυπλοκότητα: O(b^m) με m: μέγιστο βάθος
Χωρική πολυπλοκότητα: Ο(bm), γιατί αποθηκεύει μόνο το μονοπάτι από την ρίζα μέχρι το φύλλο και τους αδερφούς κόμβους που δεν έχουν επεκταθεί. Μόλις τελειώνει με την εξέταση κόμβων, τους αφαιρεί από τη μνήμη. Γίνεται Ο(m), όταν χρησιμοποιηθεί η παραλλαγή με backtracking, στην οποία δεν παράγονται οι αδερφοί κόμβοι στη μνήμη (δλδ. παράγεται ένας διάδοχος κάθε φορά κι όχι όλοι).

παραλλαγή: Depth-limited search [wiki]. Ο αλγόριθμος κάνει ό,τι και ο DFS απλά φτάνει σε μέγιστο βάθος l, στο οποίο σταματάει την κατά βάθος επέκταση (ακόμα κι αν υπάρχουν ανεξερεύνητοι κόμβοι σε μεγαλύτερο βάθος). 

[wiki]

Iterative deepening depth-first search (IDDFS or IDS)

Η αναζήτηση επαναληπτικής εκβάθυνσης συνδυάζει τα πλεονεκτήματα του DFS (δλδ. λογικές απαιτήσεις μνήμης) και του BFS (δλδ. πλήρης όταν ο παράγοντας διακλάδωσης είναι πεπερασμένος και βέλτιστος). Αυτό που κάνει είναι να εκτελέσει επαναληπτικά τον Depth-limited search με αυξανόμενο βάθος σε κάθε επανάληψη.

Μπορεί να φαίνεται σπάταλη στρατηγική, αλλά δεδομένου ότι ο παράγονρας διακλάδωσης (b) είναι σταθερός -άρα οι περισσότεροι κόμβοι βρίσκονται χαμηλά στο δέντρο- δεχόμαστε να κάνουμε το tradeoff για την απόκτηση των πλεονεκτημάτων του BFS.

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

Χρονική πολυπλοκότητα: O(b^d), η ίδια με τον DFS (παρά τις επαναλήψεις)
Χωρική πολυπλοκότητα: Ο(bd), όπου d το βάθος της βέλτιστης λύσης!

[wiki]

***Οι παραπάνω αλγόριθμοι βελτιώνουν την ταχύτητά τους, χρησιμοποιώντας κλειστό σύνολο***
***Οι αλγόριθμοι που ξεχνούν την ιστορία τους, είναι καταδικσμένοι να την επαναλάβουν  [:P] ***

Bidirectional search

Η αμφίδρομη αναζήτηση εκτελεί δύο ταυτόχρονες αναζητήσεις από την αρχική κατάσταση προς τον στόχο και την αντίστροφη. Αυτό γίνεται γιατί η χρονική πολυπλοκότητα από O(b^d) είναι σαφώς μεγαλύτερη του Ο(2b^d/2). Ενώ και η χωρική πολυπλοκότητα είναι ίδια Ο(2b^d/2). Αν και οι δύο αναζητήσεις είναι BFS τότε η BS είναι επίσης πλήρης και βέλτιστη. Η BS όμως δεν είναι πάντα εφαρμόσιμη καθώς σε πολλά προβλήματα δεν μπορούμε να "τρέξουμε" αποδοτικά την προς τα πίσω αναζήτηση

[wiki]

Informed Search Algorithms

Στους αλγορίθμους της πληροφορημένης αναζήτησης, πέρα από τις πληροφορίες από τον ορισμό του προβλήματος, ο πράκτορας χρησιμοποιεί μια συνάρτηση αξιολόγησης (evaluation function) για να υπολογίσει πόσο καλή είναι η κατάσταση στην οποία βρίσκεται. Οι αλγόριθμοι που ακολουθούν χρησιμοποιούν ειδικές συναρτήσεις αξιολόγησης, τις ευρετικές συναρτήσεις (heuristic function). Έστω, h(n) = εκτιμώμενο κόστος φθηνότερης διαδρομής από τον κόμβο n σε έναν κόμβο στόχου. Υπάρχουν πολλές διαφορετικές ευρετικές συναρτήσεις και η ανακάλυψη ευρετικών συναρτήσεων είναι μία από τις προκλήσεις που καλούνται να αντιμετωπίσουν οι ερευνητές της TN.

Best-first search

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

Χρονική και Χωρική πολυπλοκότητα: O(b^m). Στην πράξη με μια καλή ευρετική μειώνεται πολύ ο χώρος και ο χρόνος που απαιτείται για λύση.

Για καλύτερη συμπεριφορά χρησιμοποιείται η παραλλαγή με το κλειστό σύνολο

[wiki] [ai.autonomy.net] [wikibooks]

A* search

Ο Α* στοχεύει στην ελαχιστοποίηση του ολικού εκτιμώμενου κόστους λύσης. O A* αξιολογεί τους κόμβους με την ακόλουθη συνάρτηση:

f(n) = g(n) + h(n), όπου g(n) είναι το (πραγματικό) κόστος μετάβασης στον κόμβο n και h(n), όπως είπαμε προηγουμένως, το εκτιμώμενο κόστος από τον κόμβο n στο στόχο.

Ο αλγόριθμος είναι πλήρης (αν ο παράγοντας διακλάδωσης είναι πεπερασμένος) και βέλτιστος αν η ευρετική είναι αποδεκτή. (Αποδεκτή είναι μια ευρετική, όταν σε κόμβο n δείχνει μικρότερο ή ίσο εκτιμώμενο κόστος από το πραγματικό κόστος της μετάβασης από τον n στο στόχο)

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

 [wiki]

bonus: Ένα βίντεο της συμμετοχής του Robin Baumgarten στο ΑΙ Mario Competition 2009, που χρησιμοποιεί -μεταξύ άλλων τον Α*

Local Search Algorithms

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

Hill Climbing (HC)

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

Για την αποφυγή των τοπικών μέγιστων και των οροπεδίων υπάρχουν πολλές παραλλαγές του αλγορίθμου:

• HC με πλάγια βήματα. Δηλαδή ο πράκτορας κάνει έναν αριθμό πεπερασμένων βημάτων προς κάποια κατεύθυνση ώστε να ξεφύγει από κάποιο εμπόδιο.

• HC με πρώτη επιλογή. Ο αλγόριθμος προχωράει στην πρώτη κατάσταση που είναι καλύτερη από την τρέχουσα, ακόμα κι αν αυτή δεν είναι η καλύτερη από όλα τα παιδιά. Με αυτόν τον τρόπο αποφεύγεται ο "ορειβάτης" να ανεβαίνει με μεγάλη κλήση (που μπορεί να τον παγιδέψει)

• HC με τυχαίες επανεκκινήσεις. Σε πολλούς greedy και τυχαιοποιημένους αλγορίθμους είναι προτιμότερο να γίνονται επανεκκινήσεις. Οι πιθανότητες επιτυχίας της κατάστασης στόχου από p στη μία επανεκκίνηση γίνονται n*p, με n επανεκκινήσεις.

• Στοχαστικός HC, ο οποίος διαλέγει την επόμενη κατάσταση στην τύχη, με συντελεστή ανάλογο της αξίας του κάθε παιδιού.

Συγκριτικά, ο HC στο πρόβλημα των 8 βασιλισσών επιτυγχάνει στο 14% των στιγμιοτύπων του προβλήματος με 4 βήματα, ενώ τις υπόλοιπες παγιδεύεται. Ο HC με 100 πλάγια βήματα πετυχαίνει στο 94% με μ.ο. 21 βήματα, ενώ ο HC με επανεκκινήσεις (τελείωνει όταν βρει λύση), κάνει μ.ο. 22 βήματα και είναι ο προτιμώτερος αφού πάντα μας βρίσκει λύση.

 [wiki] [HC site] [simulation]

Simulated Annealing

Ο αλγόριθμος προσομοιωμένης ανόπτησης (wtf? *) χρησιμοποιεί "κατηφορικές" κινήσεις και επιλέγει μετάβαση μεταξύ τυχαίων γειτόνων. Αν η κίνηση βελτιώνει την κατάσταση τότε γίνεται αποδεκτή, αλλιώς γίνεται αποδεκτή με πιθανότητα exp(ΔE/T). Όπου ΔΕ είναι η διαφορά της τρέχουσας κατάστασης από την νέα και Τ είναι ένας μετρητής που μειώνεται με κάποιο ρυθμό. Έτσι "κακές" ή κατηφορικές κινήσεις ενδέχεται να γίνουν αποδεκτές στην αρχή, αλλά όχι προς το τέλος. Αν το Τ μειώνεται με αργό ρυθμό ο αλγόριθμος φτάνει στη βέλτιση λύση με πιθανότητα σχεδόν 1.

*Ανόπτηση στη μεταλλουργεία είναι η διαδικασία στην οποία θερμαίνεται ένα μέταλο σε υψηλή θερμοκρασία ώστε να του δωθεί μορφή και μετά ψύχεται βαθμιαία ώστε το υλικό να καταλήξει σε κρυσταλλική κατάσταση χαμηλής ενέργειας (δλδ. γίνεται πολύ πιο άκαμπτο). Το ρόλο της θερμοκρασίας που πέφτει σταθερά κάνει το Τ στον αλγόριθμο.

[wiki] [applet with diffirent algorithms] [image evolution]

Beam search

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

[wiki]

Genetic Algorithm

Ο Γενετικός αλγόριθμος είναι μια παραλλαγή του στοχαστικού αλγόριθμου ακτινικής αναζήτησης, με τη διαφορά της συμμετοχής δύο γονικών καταστάσεων και όχι μιας μεμονωμένης κατάστασης. Η διαδικασία της λειτουργίας του αλγορίθμου είναι εμπνευσμένη από την γενετική. Στην αρχή διαλέγονται k καταστάσεις-"χρωμοσώματα" που ονομάζονται "πληθυσμός". Κάθε κατάσταση συμβολίζεται με μία γραμματοσειρά, ανάλογα με τις ανάγκες του προβλήματος (π.χ. για το πρόβλημα των 8 βασιλισσών, αρκεί ένα string με 8 ψηφία τα οποία αντιστοιχούν την κάθε βασίλισσα σε κάθε στήλη). Με τη χρήση μια συνάρτησης καταλληλότητας (fitness function), επιλέγονται τα χρωμοσώματα και διασταυρώνονται. Μιμούμενοι τη φυσική διασταύρωση των γονιδίων, στα νέα χρωμοσώματα γίνονται μεταλλάξεις, οι οποίες φροντίζουν για την ποικιλότητα του νέου πληθυσμού.

[wiki] [GA tutorials]

 ---

Θέματα που δεν πρόλαβα να αναπτύξω:

[Παιχνίδια αντιπαλότητας: Minimax | Alpha-Beta pruning I II | Negascout | Chess Tree Search ]

[ ID3 | String searching I II | Tabu search I II | Selection Algorithm ]

---

Ένα πολύ καλό applet

---

Δείτε και την βιβλιοθήκη αλγορίθμων αναζήτησης από τον solidus