Εβδομάδα 2: Τυφλή αναζήτηση

Σημειώσεις μελέτης βασισμένες στη Διάλεξη 2 του μαθήματος. Οι διαφάνειες, με τις ασκήσεις πάνω σε δένδρα και λαβυρίνθους, βρίσκονται στο Moodle.

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

Γιατί η αναζήτηση είναι δύσκολη

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

Θυμίζει τον μύθο με τη σκακιέρα και τους κόκκους ρυζιού: ένας κόκκος στο πρώτο τετράγωνο, δύο στο δεύτερο, τέσσερις στο τρίτο… Στο τελευταίο τετράγωνο χρειάζονται πάνω από 9 πεντάκις εκατομμύρια (9 × 10¹⁸) κόκκοι. Γι’ αυτό μεγάλο μέρος της ΤΝ ασχολείται με το πώς περιορίζουμε την αναζήτηση.

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

Ο γενικός αλγόριθμος αναζήτησης

Όλοι οι αλγόριθμοι αυτής της εβδομάδας είναι παραλλαγές του ίδιου σχήματος. Χρειάζονται δύο λίστες:

• το μέτωπο αναζήτησης (frontier): οι καταστάσεις που έχουμε βρει αλλά δεν έχουμε ακόμα εξετάσει·
• το κλειστό σύνολο (closed set): οι καταστάσεις που έχουμε ήδη εξετάσει, ώστε να μην τις ξαναεξετάσουμε.

Ο αλγόριθμος:

1. Βάλε την αρχική κατάσταση στο μέτωπο.
2. Όσο το μέτωπο δεν είναι άδειο:
   1. Βγάλε την πρώτη κατάσταση από το μέτωπο.
   2. Αν είναι ήδη στο κλειστό σύνολο, προχώρα στην επόμενη.
   3. Αν είναι τελική, βρήκες λύση.
   4. Αλλιώς επέκτεινέ την: βρες τα παιδιά της και βάλ’ τα στο μέτωπο.
   5. Βάλε την κατάσταση στο κλειστό σύνολο.
3. Αν το μέτωπο άδειασε χωρίς λύση, το πρόβλημα δεν έχει λύση.

Το μόνο που αλλάζει από αλγόριθμο σε αλγόριθμο είναι σε ποιο σημείο του μετώπου μπαίνουν τα παιδιά, άρα ποια κατάσταση εξετάζεται μετά.

Τι κοιτάμε σε έναν αλγόριθμο

• Πλήρης (complete): αν υπάρχει λύση, θα τη βρει σίγουρα.
• Βέλτιστη λύση (optimal): η καλύτερη λύση, π.χ. με τις λιγότερες κινήσεις ή το μικρότερο κόστος.
• Αποδεκτός (admissible): βρίσκει πάντα τη βέλτιστη λύση, αν υπάρχει.
• Εξαντλητικός (exhaustive): εξετάζει ολόκληρο τον χώρο αναζήτησης.
• Μνήμη: πόσες καταστάσεις κρατά ταυτόχρονα στο μέτωπο.

Αναζήτηση πρώτα σε βάθος (DFS)

Ο DFS (Depth-First Search) πηγαίνει όσο πιο βαθιά μπορεί σε ένα κλαδί, και μόνο όταν φτάσει σε αδιέξοδο γυρίζει πίσω για να δοκιμάσει το επόμενο.

• Πώς: τα παιδιά μπαίνουν στην αρχή του μετώπου. Το μέτωπο λειτουργεί σαν στοίβα (LIFO: όποιος μπαίνει τελευταίος, βγαίνει πρώτος).
• Υπέρ: χρειάζεται λίγη μνήμη, γιατί κρατά βασικά μόνο το τρέχον κλαδί.
• Κατά: η πρώτη λύση που βρίσκει δεν είναι απαραίτητα η καλύτερη. Αν δεν ελέγχει για κύκλους ή αν ο χώρος είναι άπειρος, μπορεί να χαθεί σε ένα ατελείωτο κλαδί. Τότε δεν είναι πλήρης.
• Αν ο χώρος αναζήτησης είναι πεπερασμένος και χρησιμοποιεί κλειστό σύνολο, ο DFS είναι πλήρης.

Αναζήτηση πρώτα σε πλάτος (BFS)

Ο BFS (Breadth-First Search) εξετάζει το δένδρο επίπεδο-επίπεδο: πρώτα όλες τις καταστάσεις σε απόσταση 1 κίνησης, μετά όλες σε απόσταση 2, κ.ο.κ.

• Πώς: τα παιδιά μπαίνουν στο τέλος του μετώπου. Το μέτωπο λειτουργεί σαν ουρά (FIFO: όποιος μπαίνει πρώτος, βγαίνει πρώτος).
• Υπέρ: είναι πλήρης και βρίσκει τη λύση με τις λιγότερες κινήσεις.
• Κατά: θέλει πολλή μνήμη. Το μέτωπο κρατά σχεδόν ολόκληρο το τρέχον επίπεδο, που μεγαλώνει εκθετικά (b^d). Σε πραγματικά προβλήματα συχνά σταματά επειδή τελειώνει η μνήμη.

Στο πρόβλημα των ποτηριών της Εβδομάδας 1, η λύση των έξι κινήσεων είναι ακριβώς αυτή που βρίσκει ο BFS: δεν υπάρχει λύση με λιγότερες.

Επαναληπτική εκβάθυνση (ID)

Η επαναληπτική εκβάθυνση (Iterative Deepening) συνδυάζει τα καλά των δύο. Τρέχει τον DFS με όριο βάθους, και αν δεν βρει λύση, ξεκινά από την αρχή με μεγαλύτερο όριο:

1. Όρισε ένα αρχικό όριο βάθους (συνήθως 1).
2. Τρέξε DFS χωρίς να κατέβεις πιο βαθιά από το όριο.
3. Αν βρήκες λύση, σταμάτα.
4. Αλλιώς αύξησε το όριο (συνήθως κατά 1) και ξαναπήγαινε στο βήμα 2.

• Υπέρ: είναι πλήρης, δεν χάνεται σε ατελείωτα κλαδιά και θέλει λίγη μνήμη, όπως ο DFS. Αν το όριο αυξάνει κατά 1, βρίσκει τη λύση με τις λιγότερες κινήσεις, όπως ο BFS.
• Κατά: κάθε γύρος ξεκινά από το μηδέν και ξαναεξετάζει τα πάνω επίπεδα.

Η επανάληψη κοστίζει λιγότερο απ’ όσο φαίνεται, γιατί οι περισσότεροι κόμβοι βρίσκονται στο τελευταίο επίπεδο. Για b = 10 και d = 5 ο BFS εξετάζει 111.111 κόμβους και η ID 123.456, μόνο περίπου 11% περισσότερους.

Παράδειγμα: ο λαβύρινθος ως πρόβλημα

Για να ψάξεις διαδρομή σε έναν λαβύρινθο, πρώτα τον γράφεις ως πρόβλημα (I, G, T, S):

• χωρίζεις τον χάρτη σε πλέγμα και κάθε τετράγωνο είναι μια θέση pos(X, Y)·
• S: όλες οι ελεύθερες θέσεις (όχι οι τοίχοι)·
• I: η θέση της εισόδου, G: η θέση της εξόδου·
• T: τέσσερις κινήσεις: αριστερά, πάνω, δεξιά, κάτω (χωρίς διαγώνιες), αρκεί η νέα θέση να είναι ελεύθερη.

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

Αναζήτηση διπλής κατεύθυνσης (BiS)

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

• Γιατί βοηθά: δύο αναζητήσεις μέχρι τη μέση (βάθος d/2) εξετάζουν πολύ λιγότερους κόμβους από μία μέχρι το τέλος: περίπου 2·b^(d/2) αντί για b^d.
• Προϋποθέσεις: οι κινήσεις πρέπει να αντιστρέφονται και η τελική κατάσταση να είναι γνωστή από πριν.
• Κατά: οι δύο αναζητήσεις πρέπει συνεχώς να ελέγχουν αν συναντήθηκαν, κάτι που έχει επιπλέον κόστος.

Επέκταση και οριοθέτηση (Branch & Bound)

Ο B&B χρησιμοποιείται όταν δεν αρκεί μια οποιαδήποτε λύση, αλλά θέλουμε αυτή με το ελάχιστο κόστος.

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

Παράδειγμα: ο πλανόδιος πωλητής με 4 πόλεις

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

• α–β: 3, α–γ: 5, α–δ: 3
• β–γ: 5, β–δ: 9
• γ–δ: 5

Ο B&B δοκιμάζει τις διαδρομές με τη σειρά, σαν DFS:

1. α→β→γ→δ→α: 3 + 5 + 5 + 3 = 16. Πρώτη πλήρης λύση· το όριο γίνεται 16.
2. α→β→δ→γ: ήδη 3 + 9 + 5 = 17 > 16, άρα κλάδεμα πριν καν γυρίσει στην α.
3. α→γ→β→δ: ήδη 5 + 5 + 9 = 19, κλάδεμα.
4. α→γ→δ→β: ήδη 5 + 5 + 9 = 19, κλάδεμα.
5. α→δ→β→γ: ήδη 3 + 9 + 5 = 17, κλάδεμα.
6. α→δ→γ→β→α: 3 + 5 + 5 + 3 = 16, ίσο με το όριο, άρα όχι καλύτερη. Είναι η ίδια διαδρομή με την πρώτη, ανάποδα.

Η βέλτιστη διαδρομή είναι α→β→γ→δ→α με κόστος 16. Μόλις βρέθηκε μια καλή λύση, τέσσερις από τις υπόλοιπες πέντε διαδρομές σταμάτησαν πριν ολοκληρωθούν. Σε μεγαλύτερα προβλήματα το κλάδεμα γίνεται πιο ψηλά στο δένδρο και εξοικονομεί τεράστιο αριθμό καταστάσεων.

Γιατί χρειάζεται κάτι τέτοιο; Με N πόλεις υπάρχουν (N−1)! διαφορετικές διαδρομές. Για 20 πόλεις είναι περίπου 1,2 × 10¹⁷, πάρα πολλές για να τις δοκιμάσεις όλες. Ο πλανόδιος πωλητής είναι ένα από τα γνωστά NP-πλήρη προβλήματα, για τα οποία δεν ξέρουμε γρήγορο αλγόριθμο.

Το πόσο βοηθά ο B&B εξαρτάται από το πόσο νωρίς βρίσκει μια καλή λύση. Αν οι λύσεις βρεθούν από τη χειρότερη προς την καλύτερη, μπορεί να μην κλαδέψει σχεδόν τίποτα και να δουλέψει σαν απλός DFS.

Σύγκριση

Εξάσκηση

Στο δένδρο παρακάτω οι τελικές καταστάσεις είναι οι I και J. Όταν ένας κόμβος έχει πολλά παιδιά, εξετάζεις πρώτα το αριστερό.

              A
          /       \
         B         C
        / \       / \
       D   E     F   G
          / \    |
         H   I*  J*

Με ποια σειρά εξετάζει τους κόμβους ο DFS;

A → B → D → E → H → I. Κατεβαίνει πρώτα το αριστερό κλαδί (B, D) και, όταν φτάνει σε αδιέξοδο στο D, γυρίζει στο E.

Με ποια σειρά εξετάζει τους κόμβους ο BFS;

A → B → C → D → E → F → G → H → I. Πρώτα όλο το επίπεδο 1 (B, C), μετά όλο το επίπεδο 2 (D, E, F, G), και στο επίπεδο 3 βρίσκει το I.

Και η ID, με αρχικό όριο βάθους 1 και βήμα 1;

• Όριο 1: A → B → C
• Όριο 2: A → B → D → E → C → F → G
• Όριο 3: A → B → D → E → H → I

Η λύση βρίσκεται στον τρίτο γύρο, στο ίδιο βάθος με τον BFS, αλλά με τη μνήμη του DFS.

Ερωτήσεις αυτοαξιολόγησης

1. Ποια είναι η μόνη ουσιαστική διαφορά ανάμεσα στον DFS και τον BFS;

Το πού μπαίνουν τα παιδιά στο μέτωπο: στην αρχή στον DFS (στοίβα), στο τέλος στον BFS (ουρά). Όλα τα άλλα βήματα του γενικού αλγορίθμου είναι ίδια.

2. Γιατί ο BFS συχνά δεν χρησιμοποιείται σε μεγάλα προβλήματα, παρόλο που βρίσκει τη συντομότερη λύση;

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

3. Τι προϋποθέσεις χρειάζεται η αναζήτηση διπλής κατεύθυνσης;

Κινήσεις που αντιστρέφονται, ώστε να μπορείς να ψάξεις «προς τα πίσω» από τον στόχο, και μια τελική κατάσταση που είναι γνωστή από πριν.

4. Στον B&B, γιατί μπορούμε να πετάξουμε μια μερική διαδρομή με κόστος 17 όταν έχουμε ήδη λύση με κόστος 16;

Γιατί το κόστος μιας διαδρομής μόνο μεγαλώνει όσο τη συνεχίζουμε (οι αποστάσεις είναι θετικές). Μια διαδρομή που κοστίζει ήδη 17 δεν μπορεί να καταλήξει φθηνότερη από 16.

---

Πηγές: Διάλεξη 2 του μαθήματος· Ι. Βλαχάβας, Π. Κεφαλάς, Ν. Βασιλειάδης, Φ. Κόκκορας, Η. Σακελλαρίου, Τεχνητή Νοημοσύνη (4η έκδοση), κεφάλαιο για τους αλγορίθμους τυφλής αναζήτησης.