Τεχνητή Νοημοσύνη — Ιούνιος 2022¶

IMG_20220617_133535.jpg¶

Θέμα 1° (Μονάδες 20) Παρακάτω παρουσιάζεται μια εκδοχή του προβλήματος των πύργων του Hanoi. Υπάρχουν 3 πύργοι (A, B, C) και 2 δίσκοι (μικρός και μεγάλος). Στόχος είναι να μεταφερθούν και οι 2 δίσκοι από τον πύργο A στον πύργο C (όπως φαίνεται στην εικόνα) σύμφωνα με τις παρακάτω προϋποθέσεις: - Μπορεί να μεταφερθεί μόνο ένα δίσκος τη φορά. - Δεν μπορεί να τοποθετηθεί ο μεγάλος δίσκος πάνω από τον μικρό δίσκο.

[Σχήμα: Τρεις πύργοι A, B, C. Αρχική κατάσταση: Στον πύργο A βρίσκονται τοποθετημένοι ο μεγάλος δίσκος στη βάση και ο μικρός δίσκος από πάνω. Οι πύργοι B και C είναι άδειοι. Βέλος προς Τελική κατάσταση. Τελική κατάσταση: Οι πύργοι A και B είναι άδειοι. Στον πύργο C βρίσκονται τοποθετημένοι ο μεγάλος δίσκος στη βάση και ο μικρός δίσκος από πάνω.]

Α) Περιγράψτε το σαν πρόβλημα αναζήτησης, δηλ. βρείτε μια αναπαράσταση μιας τυχαίας κατάστασης και με βάση αυτήν ορίστε την αρχική και την/τις τελική/ές κατάσταση/εις. Προσδιορίστε τον χώρο καταστάσεων του προβλήματος. [5] Β) Ορίστε κατάλληλους τελεστές μετάβασης (σύμβολο, περιγραφή, προϋποθέσεις, αποτέλεσμα). [5] Γ) Ορίστε ένα ευρετικό για την εκτίμηση της απόστασης κάθε κατάστασης από την τελική λύση. Θεωρώντας ότι η εφαρμογή κάθε τελεστή έχει κόστος 1, είναι παραδεκτό το ευρετικό που ορίσατε; [5] Δ) Σχεδιάστε το πλήρες δένδρο αναζήτησης. Υποθέστε ότι οι κύκλοι ανιχνεύονται και δεν αναπτύσσονται κόμβοι που έχουν ήδη αναπτυχθεί στο μονοπάτι προς τη ρίζα. Επιπλέον αν μία κατάσταση δεν βρίσκεται στο μονοπάτι προς τη ρίζα, αλλά έχει αναλυθεί ήδη σε προηγούμενο επίπεδο του δέντρου, δεν αναλύεται ξανά. [5]

Θέμα 2° (Μονάδες 15) Θεωρείστε το γράφημα μεταβάσεων του παρακάτω σχήματος όπου \(S\) είναι η αρχική κατάσταση και \(G1, G2, G3\) οι τρεις τελικές καταστάσεις. Πάνω στις ακμές αναγράφεται το κόστος μετάβασης μεταξύ δύο καταστάσεων και δίπλα σε κάθε κόμβο περιγράφεται το κόστος που αντιστοιχεί σε μια ευρετική συνάρτηση \(h(n)\).

[Σχήμα: Κατευθυνόμενο γράφημα καταστάσεων με ρίζα \(S\) (\(h=10\)). Από \(S\): - ακμή κόστους 5 προς \(A\) (\(h=13\)) - ακμή κόστους 4 προς \(B\) (\(h=12\)) - ακμή κόστους 2 προς \(C\) (\(h=11\)) Από \(A\): ακμή κόστους 10 προς \(D\) (\(h=16\)). Από \(D\): ακμή κόστους 12 προς \(G1\) (\(h=0\)). Από \(B\): ακμή κόστους 10 προς \(E\) (\(h=11\)). Από \(E\): ακμή κόστους 15 προς \(G2\) (\(h=0\)). Από \(C\): ακμή κόστους 8 προς \(F\) (\(h=13\)). Από \(F\): ακμή κόστους 10 προς \(H\) (\(h=14\)). Από \(H\): ακμή κόστους 16 προς \(G3\) (\(h=0\)).]

Α) Για τον παραπάνω χώρο καταστάσεων να εφαρμόσετε: i) Αναζήτηση \(\text{A}^*\) και ii) Αναζήτηση ομοιόμορφου κόστους (UCS).

IMG_20220617_133602.jpg¶

καθεμιά από τις παραπάνω δύο στρατηγικές αναζήτησης, να περιγράψετε την εξέλιξη της αναζήτησης χρησιμοποιώντας τις λίστες [ΜΑ] (μέτωπο αναζήτησης) και [ΚΛΕΙΣΤΟ]. Στο τέλος κάθε αναζήτησης να αναφέρετε το μονοπάτι (λύση) που βρήκατε. Σε περίπτωση ισοτιμίας καταστάσεων με ίδιο κόστος να θεωρήσετε αλφαβητική προτεραιότητα. [10] Β) Δίνουν οι παραπάνω αλγόριθμοι τη βέλτιστη λύση; Αιτιολογήστε για τον καθένα γιατί δίνει ή όχι τη βέλτιστη λύση. [5]

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

Α) Να αναπαρασταθεί η γνώση με πλαίσια. [10] Β) Εξηγείστε πώς βρίσκεται η απάντηση στο ερώτημα «Τι χρώμα έχει ο Τουΐτι;» με βάση τον (1) αλγόριθμο βασισμένο στην απόσταση συλλογισμού, (2) τον αλγόριθμο τύπου Ν, και (3) τον αλγόριθμο τύπου Ζ. [10]

ΘΕΜΑ 4° (μονάδες 20) Δίνεται η παρακάτω βάση κανόνων με συντελεστές βεβαιότητας (με πλάγια γραφή εμφανίζονται οι μεταβλητές):

R1	R4
if is(shape, round) then assert(fruit, mandarin) (0.4)	if is(shape, round) and is(color, red) then assert(fruit, apple) (0.7)
R2	R5
if is(shape, round) then assert(fruit, apple) (0.3)	if is(shape, round) and is(color, red) and is(size, small) then assert(fruit, apple) (0.5)
R3	R6
if is(shape, round) and is(surface, weasand) then assert(fruit, mandarin) (0.8)	if is(shape, round) and is(size, small) then assert(fruit, mandarin) (0.6)

Δίνονται τα εξής δεδομένα διαδοχικά: “is(shape, round)”, “is(surface, weasand) (-0.2)”, “is(color, red) (0.5)”, “is(size, small) (0.7)”. Περιγράψτε τα βήματα εξαγωγής συμπεράσματος όταν μας ενδιαφέρει η τιμή της μεταβλητής fruit. Ποια τιμή θα επιστραφεί;

ΘΕΜΑ 5° (μονάδες 25) Δίνεται η εξής περιγραφή: «Όλα οι οργανισμοί τρώνε κάποιο είδος τροφής, ενώ και τα ίδια μπορούν να αποτελέσουν τροφή για κάποιον άλλο οργανισμό. Όλα τα ζώα και όλα τα φυτά είναι οργανισμοί. Τα φυτοφάγα ζώα τρώνε μόνο φυτά. Τα σαρκοβόρα ζώα τρώνε άλλα ζώα, ενώ τα παμφάγα ζώα τρώνε και φυτά και άλλα ζώα. Τα σαρκοβόρα και τα παμφάγα ζώα τρώνε τα μικρότερα από αυτά ζώα. Ο σκύλος είναι ένα είδος παμφάγου ζώου.»

Α) Να αναπαρασταθεί η γνώση με προτάσεις ΚΛΠΤ. Δεν είναι απαραίτητο να καταγράψετε όλα τα βήματα. [15] Β) Να μετατρέψετε τη γνώση από ΚΛΠΤ σε Προτασιακή Μορφή. Δεν είναι απαραίτητο να καταγράψετε όλα τα βήματα. [10]

ΚΑΛΗ ΕΠΙΤΥΧΙΑ!

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2022-06.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): IMG_3335.png, 2234.png

Λύσεις (🟡 community)

Κατάσταση: 🟡 community Πηγή: φωτογραφία λύσης, πηγή άγνωστη (μάλλον φοιτητική)

Προσοχή

Στον πίνακα του A* (γραμμή 5) ο κόμβος 5 εμφανίζεται δύο φορές στο OPEN· ο πίνακας χρειάζεται έλεγχο.

Λύσεις — Τεχνητή Νοημοσύνη — Ιούνιος 2022¶

2234.png¶

Άσκηση 4

Στο γράφημα του σχήματος να εφαρμόσετε τους αλγορίθμους: α) \(A^*\), β) BestFS, γ) Hill Climbing με αρχικό κόμβο τον 0 και κόμβο στόχο τον 5. Οι αριθμοί στις ακμές δείχνουν το πραγματικό κόστος. Να δείξετε την εξέλιξη της αναζήτησης χρησιμοποιώντας τις λίστες OPEN και CLOSED, όπου υπάρχουν. Όπου υπάρχει ισοδυναμία, επεκτείνεται ο κόμβος με τη μικρότερη αρίθμηση. Να αναφέρετε το τελικό μονοπάτι και το κόστος για κάθε αλγόριθμο.

[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους 0 (\(h(0)=3\)), 1 (\(h(1)=1\)), 2 (\(h(2)=2\)), 3 (\(h(3)=3\)), 4 (\(h(4)=4\)), 5 (\(h(5)=0\)). Κόστη ακμών: \(0 \to 1: 3\), \(0 \to 2: 2\), \(1 \to 3: 3\), \(1 \to 4: 1\), \(2 \to 5: 7\), \(3 \to 5: 5\), \(4 \to 5: 4\).]

Απάντηση

Greedy Best-First search	Hill-Climbing search	A* search
1. OPEN: [0] CLOSED: []	1. OPEN: [0] CLOSED: []	1. OPEN: [0] CLOSED: []
2. OPEN: [1, 2] CLOSED: [0]	2. OPEN: [1] CLOSED: [0]	2. OPEN: [1, 2] CLOSED: [0]
3. OPEN: [2, 3, 4] CLOSED: [0, 1]	3. OPEN: [3, 4] CLOSED: [0, 1]	3. OPEN: [2, 4, 3] CLOSED: [0, 1]
4. OPEN: [5, 3, 4] CLOSED: [0, 1, 2]	4. OPEN: [5] CLOSED: [0, 1, 3]	4. OPEN: [4, 3, 5]¹ CLOSED: [0, 1, 2]
5. OPEN: [3, 4] CLOSED: [0, 1, 2, 5]	5. OPEN: [] CLOSED: [0, 1, 3, 5]	5. OPEN: [5, 3, 5] CLOSED: [0, 1, 2, 4]

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή