Εβδομάδα 3: Ευριστική αναζήτηση

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

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

Ευριστικός μηχανισμός

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

Στην πράξη ο μηχανισμός γράφεται ως ευριστική συνάρτηση (heuristic function). Παίρνει μια κατάσταση και επιστρέφει έναν αριθμό, την ευριστική τιμή. Η τιμή αυτή δεν είναι η πραγματική απόσταση από τον στόχο, αλλά μια εκτίμηση. Γι’ αυτό ένας ευριστικός μηχανισμός μπορεί και να σε στείλει σε λάθος κατεύθυνση.

Η συνάρτηση αξιολόγησης f μιας κατάστασης n ορίζεται με τρεις τρόπους:

Εδώ το g(n) είναι το πραγματικό κόστος της διαδρομής από την αρχική κατάσταση ως την n, και το h(n) η εκτίμηση από την n ως τον στόχο. Οι αλγόριθμοι που ακολουθούν μετρούν κόστος (τον 2ο ή τον 3ο τρόπο), οπότε μικρότερη τιμή σημαίνει «πιο υποσχόμενη» κατάσταση.

Ευριστικές συναρτήσεις: δύο κλασικά παραδείγματα

Λαβύρινθος: απόσταση Manhattan και Ευκλείδεια

Σε έναν λαβύρινθο-πλέγμα, για μια θέση S = (x₁, y₁) και την έξοδο F = (x₂, y₂):

• Απόσταση Manhattan: |x₁ − x₂| + |y₁ − y₂|. Μετράει τα βήματα αν κινείσαι μόνο οριζόντια και κάθετα, όπως στους κάθετους δρόμους του Μανχάταν.
• Ευκλείδεια απόσταση: √((x₁ − x₂)² + (y₁ − y₂)²), η απόσταση «σε ευθεία γραμμή».

Για S = (2, 3) και F = (7, 1): η απόσταση Manhattan είναι |2 − 7| + |3 − 1| = 5 + 2 = 7, ενώ η Ευκλείδεια είναι √(25 + 4) = √29 ≈ 5,39. Καμία δεν λαμβάνει υπόψη τους τοίχους, γι’ αυτό είναι εκτιμήσεις: η πραγματική διαδρομή είναι συνήθως μεγαλύτερη.

8-puzzle: πλακίδια εκτός θέσης και άθροισμα Manhattan

Στο N-puzzle η ευριστική συνάρτηση εκτιμά πόσες κινήσεις απέχει μια κατάσταση από την τελική. Δύο απλές επιλογές:

1. Πλακίδια εκτός θέσης: πόσα πλακίδια δεν βρίσκονται στη θέση τους (το κενό δεν μετράει).
2. Άθροισμα αποστάσεων Manhattan: για κάθε πλακίδιο, πόσες γραμμές και στήλες απέχει από τη σωστή του θέση, και το άθροισμα όλων.

Παράδειγμα (το «·» είναι το κενό):

Κατάσταση     Στόχος
5 1 3         1 2 3
4 · 2         4 5 6
7 8 6         7 8 ·

• Εκτός θέσης είναι τα 5, 1, 2 και 6, άρα η πρώτη συνάρτηση δίνει 4.
• Οι αποστάσεις Manhattan είναι: 5 → 2 (μία γραμμή και μία στήλη), 1 → 1, 2 → 2, 6 → 1, όλα τα άλλα 0. Το άθροισμα είναι 6.

Η λύση χρειάζεται στην πραγματικότητα 12 κινήσεις. Και οι δύο συναρτήσεις υποεκτιμούν, αλλά η Manhattan δίνει πιο κοντινή εκτίμηση, άρα οδηγεί καλύτερα την αναζήτηση. Αυτό θα μας χρειαστεί στον A*.

Το παράδειγμά μας

Για να συγκρίνουμε τους αλγορίθμους, χρησιμοποιούμε το ίδιο μικρό πρόβλημα: θέλουμε να πάμε από το S στο G. Οι δρόμοι είναι διπλής κατεύθυνσης, με κόστος:

και ευριστικές τιμές (εκτίμηση απόστασης ως το G):

Η φθηνότερη διαδρομή είναι S → B → C → G με κόστος 4 + 1 + 3 = 8. Ας δούμε ποιος αλγόριθμος τη βρίσκει.

Greedy Best-First Search

Ο Greedy Best-First («πρώτα το καλύτερο», άπληστος) κρατά ένα μέτωπο αναζήτησης όπως η τυφλή αναζήτηση, αλλά το ταξινομεί κατά h: κάθε φορά επεκτείνει την κατάσταση που φαίνεται πιο κοντά στον στόχο. Επειδή κρατά και τις υπόλοιπες στο μέτωπο, μπορεί να γυρίσει πίσω σε μια παλιότερη επιλογή, αν ο δρόμος που ακολουθεί χειροτερέψει.

Τα βήματα:

1. Βάλε την αρχική κατάσταση στο μέτωπο.
2. Αν το μέτωπο είναι άδειο, σταμάτα (δεν υπάρχει λύση).
3. Βγάλε την πρώτη κατάσταση S του μετώπου. Αν είναι ήδη στο κλειστό σύνολο, πήγαινε στο 2.
4. Αν η S είναι τελική, ανέφερε τη λύση.
5. Βρες τα παιδιά της S, υπολόγισε την h του καθενός και βάλ’ τα στο μέτωπο.
6. Ταξινόμησε το μέτωπο κατά αύξουσα h, βάλε την S στο κλειστό σύνολο και πήγαινε στο 2.

Στο παράδειγμά μας:

Βρίσκει γρήγορα τη διαδρομή S → A → C → G, με κόστος 2 + 5 + 3 = 10. Δεν είναι η βέλτιστη (8): ο αλγόριθμος κοιτάζει μόνο πόσο απέχει ακόμα από τον στόχο, όχι πόσο έχει ήδη πληρώσει.

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

Αναρρίχηση λόφων (Hill Climbing)

Ο Hill Climbing (HC) είναι πιο «βιαστικός»: από τα παιδιά της τρέχουσας κατάστασης κρατά μόνο το καλύτερο και πετάει τα υπόλοιπα. Δεν χρειάζεται μέτωπο αναζήτησης.

1. Η αρχική κατάσταση είναι η τρέχουσα.
2. Αν η τρέχουσα είναι τελική, ανέφερέ τη και σταμάτα.
3. Βρες τα παιδιά της και διάλεξε αυτό με τη μικρότερη h.
4. Αυτό γίνεται η τρέχουσα κατάσταση· πήγαινε στο 2.

Στο παράδειγμά μας ο HC κάνει τις ίδιες επιλογές με τον Greedy: S → A (3 < 4) → C → G, κόστος 10. Η διαφορά φαίνεται όταν η καλύτερη επιλογή αποδειχθεί αδιέξοδο: ο Greedy θα γύριζε στο B που έχει κρατήσει στο μέτωπο, ενώ ο HC το έχει ήδη πετάξει και κολλάει.

Γιατί «αναρρίχηση λόφων»; Φαντάσου ότι ανεβαίνεις έναν λόφο μέσα στην ομίχλη και κάθε φορά κάνεις το βήμα που ανεβαίνει περισσότερο. Φτάνεις γρήγορα σε μια κορυφή, αλλά ίσως σε ένα χαμηλό ύψωμα και όχι στην ψηλότερη κορυφή, την οποία δεν βλέπεις.

• Υπέρ: πολύ γρήγορος και με ελάχιστη μνήμη.
• Κατά: δεν είναι πλήρης (μπορεί να μη βρει λύση, ακόμη κι αν υπάρχει), δεν εγγυάται τη βέλτιστη λύση και εξαρτάται πολύ από την h.

Ακτινωτή αναζήτηση (Beam Search)

Η Beam Search είναι η μέση λύση ανάμεσα στους δύο: λειτουργεί όπως ο Greedy Best-First, αλλά μετά την ταξινόμηση κρατά μόνο τις N καλύτερες καταστάσεις του μετώπου και πετάει τις υπόλοιπες. Το N λέγεται «πλάτος ακτίνας».

• Με N = 1 συμπεριφέρεται σαν τον Hill Climbing.
• Με πολύ μεγάλο N συμπεριφέρεται σαν τον Greedy Best-First.

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

Ο αλγόριθμος A*

Ο A* («Α άστρο») λειτουργεί όπως ο Best-First, αλλά ταξινομεί το μέτωπο με

f(n) = g(n) + h(n)

δηλαδή με το πραγματικό κόστος που έχει ήδη γίνει συν την εκτίμηση για όσο απομένει. Η f(n) είναι μια εκτίμηση του κόστους της καλύτερης λύσης που περνά από την n.

Δύο επιπλέον κανόνες για το μέτωπο:

• Αν βρεις μια κατάσταση που υπάρχει ήδη στο μέτωπο, κράτα μόνο τη φθηνότερη διαδρομή προς αυτήν.
• Ταξινόμησε όλο το μέτωπο κατά f.

Στο παράδειγμά μας:

Στο βήμα 4 ο A* βρίσκει φθηνότερο δρόμο προς το C (κόστος 5 μέσω B αντί για 7 μέσω A) και κρατά μόνο αυτόν. Το αποτέλεσμα είναι η διαδρομή S → B → C → G με κόστος 8, η βέλτιστη. Πρόσεξε ότι στο βήμα 2 επέκτεινε πρώτα το A, όπως ο Greedy, αλλά μόλις φάνηκε το πραγματικό κόστος του δρόμου μέσω A, γύρισε στο B.

Αποδεκτή ευριστική συνάρτηση

Ο A* εγγυάται ότι βρίσκει τη βέλτιστη λύση με μία προϋπόθεση: η h δεν υπερεκτιμά ποτέ το πραγματικό κόστος ως τον στόχο. Μια τέτοια h λέγεται αποδεκτή (admissible). Με αποδεκτή h, ο A* είναι πλήρης και βέλτιστος.

Στο παράδειγμα η h είναι αποδεκτή: π.χ. h(S) = 6 ενώ το πραγματικό κόστος είναι 8, και h(B) = 4 όσο ακριβώς είναι το πραγματικό. Στο 8-puzzle και οι δύο συναρτήσεις που είδαμε είναι αποδεκτές, γιατί κάθε πλακίδιο εκτός θέσης θέλει τουλάχιστον μία κίνηση, και τουλάχιστον τόσες κινήσεις όσες η απόστασή του Manhattan.

Σύγκριση

* Με αποδεκτή ευριστική συνάρτηση.

Εργαστήριο: τα πρώτα βήματα στο MATLAB

Στο εργαστήριο του μαθήματος δουλεύουμε με το MATLAB, είτε εγκατεστημένο στον υπολογιστή είτε στον browser μέσω του MATLAB Online. Το βασικό παράθυρο είναι το Command Window, όπου γράφεις εντολές μετά το >>. Δίπλα βρίσκονται ο τρέχων φάκελος (Current Folder), ο χώρος εργασίας (Workspace) με τις μεταβλητές σου και το ιστορικό εντολών.

Πράξεις και μεταβλητές

>> 7 + 3 * 2        % ο πολλαπλασιασμός γίνεται πρώτα
ans = 13
>> (7 + 3) * 2      % οι παρενθέσεις αλλάζουν τη σειρά
ans = 20
>> 2^10             % δύναμη
ans = 1024
>> x = 1.5e3        % επιστημονικός συμβολισμός: 1.5 · 10³
x = 1500

Η σειρά των πράξεων είναι η γνωστή από τα μαθηματικά: παρενθέσεις, δυνάμεις, πολλαπλασιασμοί και διαιρέσεις, προσθέσεις και αφαιρέσεις. Τα ονόματα μεταβλητών ξεκινούν με λατινικό γράμμα, έχουν μόνο γράμματα, ψηφία και _, και τα κεφαλαία διαφέρουν από τα μικρά (y και Y είναι δύο μεταβλητές). Το % ξεκινά σχόλιο και το ; στο τέλος μιας εντολής κρύβει το αποτέλεσμα.

Πίνακες

Ο πίνακας είναι το βασικό εργαλείο του MATLAB. Γράφεται σε αγκύλες: κενά ή κόμματα χωρίζουν τα στοιχεία μιας γραμμής και το ; αλλάζει γραμμή.

v = [4 1 3];          % πίνακας-γραμμή
A = [1 2; 3 4];       % πίνακας 2×2
Z = zeros(2, 3);      % 2×3 με μηδενικά
A(2, 1)               % στοιχείο 2ης γραμμής, 1ης στήλης: 3
A(:, 2)               % όλη η 2η στήλη: [2; 4]

Χρήσιμες συναρτήσεις: min, max, sum, prod, sort και find, που επιστρέφει τις θέσεις των στοιχείων που ικανοποιούν μια συνθήκη (π.χ. find(v > 2) δίνει [1 3]). Σε δισδιάστατο πίνακα, οι min, max, sum και prod δουλεύουν ανά στήλη. Για οποιαδήποτε εντολή, η help όνομα δείχνει τη βοήθειά της.

Με όσα είδαμε σήμερα, η απόσταση Manhattan και η Ευκλείδεια του παραδείγματος γράφονται σε μία γραμμή η καθεμία:

S = [2 3];  F = [7 1];
manhattan = sum(abs(S - F))         % 7
euclid    = sqrt(sum((S - F).^2))   % 5.3852

Το .^ σημαίνει «ύψωσε κάθε στοιχείο στο τετράγωνο».

if, for και αρχεία .m

h = [3 4];                 % ευριστικές τιμές των παιδιών A και B
[best, idx] = min(h);      % η μικρότερη τιμή και η θέση της
if best == 0
    disp('Βρέθηκε ο στόχος')
else
    disp(['Επεκτείνω το παιδί ', num2str(idx)])
end

total = 0;
for k = 1:5                % k = 1, 2, 3, 4, 5
    total = total + k;
end
disp(total)                % 15

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

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

1. Ποια είναι η διαφορά ανάμεσα στον Greedy Best-First και στον Hill Climbing;

Και οι δύο διαλέγουν την κατάσταση με τη μικρότερη h. Ο Greedy κρατά όλες τις υπόλοιπες στο μέτωπο και μπορεί να γυρίσει σε αυτές· ο Hill Climbing τις πετάει, γι’ αυτό χρειάζεται ελάχιστη μνήμη αλλά μπορεί να κολλήσει σε αδιέξοδο.

2. Γιατί ο Greedy βρήκε στο παράδειγμα διαδρομή κόστους 10 και όχι 8;

Γιατί ταξινομεί μόνο με την h. Το A είχε μικρότερη h από το B (3 < 4), οπότε ακολούθησε τον δρόμο μέσω A, χωρίς να λογαριάσει ότι ο δρόμος A–C κοστίζει 5. Ο A* προσθέτει το g και το καταλαβαίνει.

3. Τι γίνεται αν δώσουμε στον A* την h(n) = 0 για κάθε κατάσταση;

Η h = 0 δεν υπερεκτιμά ποτέ, άρα είναι αποδεκτή και ο A* βρίσκει ακόμα τη βέλτιστη λύση. Όμως δεν έχει καμία «πυξίδα»: ταξινομεί μόνο με το κόστος g, όπως η αναζήτηση με επέκταση και οριοθέτηση (Branch and Bound), και εξετάζει πολύ περισσότερες καταστάσεις.

4. Ποια σχέση έχει η Beam Search με N = 1 και ο Hill Climbing;

Με N = 1 κρατά στο μέτωπο μόνο την καλύτερη κατάσταση, δηλαδή κάνει ό,τι και ο Hill Climbing.

5. Στο 8-puzzle, μια συνάρτηση δίνει 4 και μια άλλη 6 για την ίδια κατάσταση. Και οι δύο είναι αποδεκτές. Ποια προτιμάς για τον A*;

Αυτή που δίνει 6 (εδώ το άθροισμα Manhattan). Αφού καμία δεν υπερεκτιμά, η μεγαλύτερη είναι πιο κοντά στο πραγματικό κόστος, άρα οδηγεί την αναζήτηση καλύτερα και ο A* επεκτείνει λιγότερες καταστάσεις.

---

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