Τεχνητή Νοημοσύνη — Ιούλιος 2025¶
8C463A75-458C-409E-9F37-888F3FFD1500.jpg¶
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ, ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ & ΠΛΗΡΟΦΟΡΙΚΗΣ ΓΡΑΠΤΗ ΕΞΕΤΑΣΗ ΣΤΟ ΜΑΘΗΜΑ "ΤΕΧΝΗΤΗ ΝΟΗΜΟΣΥΝΗ ", 1 ΙΟΥΛΙΟΥ 2025 ΔΙΑΡΚΕΙΑ ΕΞΕΤΑΣΗΣ: 2,5 ΩΡΕΣ ΟΝΟΜΑΤΕΠΩΝΥΜΟ: _________________________ AM: ______ ΕΤΟΣ: ___
ΘΕΜΑ 1ο (μονάδες 20) Θεωρείστε το παρακάτω γράφημα με αρχική κατάσταση Α και τελικές καταστάσεις \(G_1\) και \(G_2\). Οι τιμές στις ακμές είναι οι τιμές της συνάρτησης κόστους, ενώ οι τιμές στον πίνακα είναι οι τιμές της ευρετικής συνάρτησης.
[Σχήμα: Κατευθυνόμενο γράφημα με κόμβους A, B, C, D, E, F, G1, G2, I. Ακμές: A->B (4), A->C (1), A->D (4), B->E (4), C->E (2), C->F (1), D->G1 (2), E->G2 (2), F->I (4), I->G2 (1).]
| Κόμβος | Ευρετική |
|---|---|
| A | 4 |
| B | 5 |
| C | 2 |
| D | 1 |
| E | 2 |
| F | 3 |
| \(G_1\) | 0 |
| \(G_2\) | 0 |
| I | 1 |
Εκτελέστε αναλυτικά τις παρακάτω μεθόδους αναζήτησης: i) BestFS και ii) A*. Για κάθε έναν από τους αλγορίθμους δείξτε αναλυτικά τα βήματα που ακολουθεί μέχρι να βρει την πρώτη λύση. Δημιουργήστε πίνακα που θα περιέχει την τρέχουσα κατάσταση, το μέτωπο αναζήτησης, το κλειστό σύνολο καταστάσεων και τα παιδιά της τρέχουσας κατάστασης. Αναφέρετε το αποτέλεσμα του μονοπατιού και του κόστους κάθε αλγορίθμου. Υπόδειξη: Σε περίπτωση ισοβαθμίας χρησιμοποιείστε ως δευτερεύον κριτήριο την τιμή της ευρετικής συνάρτησης.
ΘΕΜΑ 2ο (μονάδες 20) Δίνεται η παρακάτω αρχική και τελική κατάσταση για ένα στιγμιότυπο του 8-puzzle. Η γειτονιά μιας κατάστασης προκύπτει από τις παρακάτω κινήσεις του κενού πλακιδίου: Πάνω (Π), Κάτω (Κ), Αριστερά (Α), Δεξιά (Δ).
Αρχική κατάσταση: | 1 | 8 | 4 | | 7 | 3 | 2 | | 5 | 6 | |
Κατάσταση Στόχος (τελική): | 1 | 2 | 3 | | 4 | 5 | 6 | | 7 | 8 | |
Α) Να εκτελέσετε τοπική αναζήτηση για δύο διαδοχικές μεταβάσεις, χρησιμοποιώντας ως συνάρτηση κόστους το πλήθος των πλακιδίων που βρίσκονται σε λάθος θέση. Δίνεται το κόστος της αρχικής κατάστασης \(h = 7\). Να σχεδιάσετε τις καταστάσεις που προκύπτουν σε κάθε βήμα και να δείξετε γιατί επιλέγεται κάθε μετάβαση [10]. Β) Να εξηγήσετε ποια μεθευρετική μέθοδος από αυτές που δίνονται ταιριάζει περισσότερο στην παρακάτω περιγραφή: «Προκειμένου να κατασκευάσουμε μια ανθεκτική γέφυρα, ξεκινάμε με ένα σύνολο τυχαίων σχεδίων. Μέσω προσομοίωσης εκτιμούμε την ανθεκτικότητα του κάθε σχεδίου. Οι καλύτερες γέφυρες συνδυάζονται μεταξύ τους ανταλλάσσοντας τμήματα του σχεδιασμού τους. Τυχαίες, μικρές τροποποιήσεις στα νέα
8C2E59A8-6750-47FC-A145-F6062B916AD7.jpg¶
σχέδια που προέκυψαν συμβαίνουν επίσης. Οι λιγότερο ανθεκτικές γέφυρες απορρίπτονται». i) τοπική αναζήτηση, ii) προσομοιωμένη ανόπτηση, iii) γενετικός αλγόριθμος, iv) Βελτιστοποίηση Σμήνους Σωματιδίων (PSO) [10].
[Λείπει από τη φωτογραφία: η αρχή του ΘΕΜΑΤΟΣ 3ου (προτάσεις ΚΛΠΤ) — το κείμενο κόβεται στο κάτω άκρο της φωτογραφίας.]
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2025-07¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
Γράφημα (κατευθυνόμενο): \(A\to B(4),\ C(1),\ D(4)\)· \(B\to E(4)\)· \(C\to E(2),\ F(1)\)· \(D\to G_1(2)\)· \(E\to G_2(2)\)· \(F\to I(4)\)· \(I\to G_2(1)\). Ευρετική: \(A=4,B=5,C=2,D=1,E=2,F=3,I=1,G_1=G_2=0\). Στις παρακάτω εκτελέσεις ο έλεγχος στόχου γίνεται όταν ο κόμβος επιλέγεται για επέκταση· κόμβοι στο κλειστό σύνολο δεν ξαναμπαίνουν. Ισοβαθμία ⇒ μικρότερο \(h\). Όλα τα βήματα επαληθεύτηκαν με πρόγραμμα.
i) BestFS (κλειδί = \(h\))
| Τρέχουσα | Μέτωπο πριν την επιλογή (κόμβος, \(h\)) | Κλειστό | Παιδιά (κόμβος, \(g\)) |
|---|---|---|---|
| \(A\) | \(\{A(4)\}\) | \(\emptyset\) | \(B(4),\ C(1),\ D(4)\) |
| \(D\) | \(\{D(1),\ C(2),\ B(5)\}\) | \(\{A\}\) | \(G_1(6)\) |
| \(G_1\) | \(\{G_1(0),\ C(2),\ B(5)\}\) | \(\{A,D\}\) | στόχος |
Μονοπάτι: \(A\to D\to G_1\), κόστος \(4+2=\mathbf{6}\).
ii) A* (κλειδί \(f=g+h\))
| Τρέχουσα | Μέτωπο πριν την επιλογή (κόμβος, \(f\)) | Κλειστό | Παιδιά (κόμβος, \(g\)) |
|---|---|---|---|
| \(A\) | \(\{A(4)\}\) | \(\emptyset\) | \(B(4),\ C(1),\ D(4)\) |
| \(C\) | \(\{C(3),\ D(5),\ B(9)\}\) | \(\{A\}\) | \(E(3),\ F(2)\) |
| \(D\) | \(\{D(5),\ E(5),\ F(5),\ B(9)\}\) — ισοβαθμία 5: \(h_D=1<h_E=2<h_F=3\) | \(\{A,C\}\) | \(G_1(6)\) |
| \(E\) | \(\{E(5),\ F(5),\ G_1(6),\ B(9)\}\) | \(\{A,C,D\}\) | \(G_2(5)\) |
| \(G_2\) | \(\{G_2(5),\ F(5),\ G_1(6),\ B(9)\}\) — ισοβαθμία 5: \(h=0\) για \(G_2\) | \(\{A,C,D,E\}\) | στόχος |
Μονοπάτι: \(A\to C\to E\to G_2\), κόστος \(1+2+2=\mathbf{5}\) (βέλτιστο· η εναλλακτική \(A\to C\to F\to I\to G_2\) κοστίζει 7).
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Α) Κόστος \(h\) = πλήθος πλακιδίων σε λάθος θέση (το κενό δεν μετράται). Αρχική:
1 8 4
7 3 2
5 6 _
Βήμα 1. Γείτονες (υπολογισμός με πρόγραμμα):
| Κίνηση | Κατάσταση | \(h\) |
|---|---|---|
| Π | 1 8 4 / 7 3 _ / 5 6 2 |
7 |
| Α | 1 8 4 / 7 3 2 / 5 _ 6 |
7 |
Κανένας γείτονας δεν είναι καλύτερος (\(7\not<7\)): η τοπική αναζήτηση με αυστηρή βελτίωση σταματά ήδη στην αρχική κατάσταση (οροπέδιο). Αν θέλουμε να εκτελέσουμε τις δύο μεταβάσεις που ζητούνται, επιτρέπουμε πλάγιες κινήσεις (ίδιο \(h\)) και επιλέγουμε μία, π.χ. την πρώτη (Π).
Βήμα 2 από 1 8 4 / 7 3 _ / 5 6 2 (\(h=7\)): γείτονες
| Κίνηση | Κατάσταση | \(h\) |
|---|---|---|
| Π | 1 8 _ / 7 3 4 / 5 6 2 |
7 |
| Κ (επιστροφή) | 1 8 4 / 7 3 2 / 5 6 _ |
7 |
| Α | 1 8 4 / 7 _ 3 / 5 6 2 |
7 |
Και πάλι όλα \(h=7\), οπότε δεν υπάρχει κίνηση που να βελτιώνει το κόστος: η συγκεκριμένη κατάσταση είναι οροπέδιο, και ο αλγόριθμος θα έπρεπε να σταματήσει (ή να κάνει πλάγια/τυχαία κίνηση, π.χ. Π ή Α). Συμπέρασμα: και στις δύο μεταβάσεις το \(h\) μένει 7 — η επιλογή γίνεται αυθαίρετα ή τυχαία, γιατί δεν υπάρχει καλύτερος γείτονας· η συνάρτηση «πλακίδια σε λάθος θέση» δίνει οροπέδιο εδώ.
Β) Η περιγραφή (αρχικός πληθυσμός τυχαίων σχεδίων, αξιολόγηση με προσομοίωση, συνδυασμός των καλύτερων με ανταλλαγή τμημάτων, τυχαίες μικρές αλλαγές, απόρριψη των χειρότερων) είναι ακριβώς ο γενετικός αλγόριθμος (iii): πληθυσμός = σύνολο σχεδίων, ικανότητα = ανθεκτικότητα, επιλογή των καλύτερων, διασταύρωση = ανταλλαγή τμημάτων, μετάλλαξη = τυχαίες μικρές τροποποιήσεις, επιβίωση του ισχυρότερου. Οι άλλες δεν ταιριάζουν: η τοπική αναζήτηση (i) και η προσομοιωμένη ανόπτηση (ii) εξελίσσουν μία λύση (όχι πληθυσμό με διασταύρωση), ενώ το PSO (iv) κινεί σωματίδια με ταχύτητες προς τις καλύτερες θέσεις και δεν ανταλλάσσει τμήματα.