Το ασανσέρ ενός πολυόροφου κτηρίου κατοικιών μπαίνει σε αυτόματη λειτουργία σε περίπτωση που διαταχθεί η εκκένωσή του προς την ταράτσα, από την αστυνομία για οποιονδήποτε λόγο κοινής ασφάλειας.
Στην απλή εκδοχή του προβλήματος, το κτήριο διαθέτει ισόγειο χώρο, 4 ορόφους και ταράτσα στον 5ο όροφο. Επιπλέον, διαθέτει ένα ασανσέρ χωρητικότητας 8 ατόμων για την μετακίνηση των ενοίκων από όροφο σε όροφο. Στον 1ο όροφο συγκεντρώνονται 9 ένοικοι, στον 2ο 4 ένοικοι, στον 3ο 12 ένοικοι και στον 4ο 7 ένοικοι. Όταν έρχεται το σήμα εκκένωσης από την αστυνομία, το ασανσέρ βρίσκεται στο ισόγειο και είναι άδειο.
Το ασανσέρ μπορεί να κινηθεί προς τα επάνω και από οποιονδήποτε όροφο προς οποιονδήποτε όροφο αρκεί να μην είναι πλήρες (να μην έχουν επιβιβαστεί ήδη 8 άτομα) και επιπλέον στον όροφο που κατευθύνεται να περιμένει τουλάχιστον ένας ένοικος. Όταν το ασανσέρ φτάνει σε έναν όροφο, ανοίγει η πόρτα και επιτρέπεται να επιβιβαστούν τόσοι ένοικοι όσοι χωρούν και οι υπόλοιποι (αν υπάρχουν) περιμένουν να έρθει το ασανσέρ εκ νέου. Το ασανσέρ κινείται από οποιονδήποτε όροφο προς την ταράτσα (άνοδος) μόνο στην περίπτωση που είναι πλήρες ή που δεν είναι μεν πλήρες αλλά δεν περιμένει άλλος ένοικος σε κάποιον όροφο προς επιβίβαση.
Στόχος του προβλήματος είναι να ολοκληρωθεί επιτυχώς η εκκένωση προς την ταράτσα, δηλαδή να βρεθούν στην ταράτσα του κτηρίου όλοι οι ένοικοι.
Α) Επιλύστε το πρόβλημα του ασανσέρ όπως περιγράφεται παραπάνω, χρησιμοποιώντας τον αλγόριθμο
της πρώτα σε βάθος αναζήτησης (DFS) και της πρώτα σε πλάτος αναζήτησης (ΒFS) με παρακολούθηση μετώπου για εύρεση του στόχου, παρουσιάστε και σχολιάστε τα αποτελέσματα. Στην έναρξη της αναζήτησης, προσθέστε τη δυνατότητα επιλογής μεταξύ των δυο αλγορίθμων.
Β) Προσθέστε τη δυνατότητα παράλληλης παρακολούθησης της ουράς των μονοπατιών που δημιουργεί ο DFS και BFS κατά την επίλυση.
Γ) Εισάγετε κάποιο ευριστικό κριτήριο αναζήτησης, υιοθετώντας μια ευριστική μέθοδο αναζήτησης που θα επιτρέψει την αποτελεσματικότερη μετακίνηση του ασανσέρ για την εκκένωση του κτηρίου, και προσθέστε στον κώδικα αναζήτησης τη δυνατότητα επιλογής της μεθόδου που επιλέξατε. Παρουσιάστε και σχολιάστε τα αποτελέσματα.
Δ) Τέλος, τεκμηριώστε κατάλληλα την εργασία σας και παραδώστε την μαζί με τον κώδικα που θα προκύψει στο τέλος όλων των παραπάνω βημάτων μαζί με τους ελέγχους ορθότητας που θα πραγματοποιήσετε χωριστά σε κάθε βήμα.
- Να οριστούν και να αναπαρασταθούν κατάλληλα:
- Ο κόσμος του προβλήματος
- Η αρχική κατάσταση και η τελική κατάσταση του προβλήματος
- Να περιγραφούν οι τελεστές μετάβασης.
- Να προσδιοριστεί ο χώρος καταστάσεων του προβλήματος (περιγραφικά και με λίστες), παραθέτοντας αντιπροσωπευτικά παραδείγματα.
- Να παρουσιαστεί σχολιασμένη η κωδικοποίηση του κόσμου του προβλήματος.
- Να παρουσιαστούν σχολιασμένα η κωδικοποίηση των τελεστών μετάβασης του προβλήματος και η συνάρτηση εύρεσης απογόνων (findchildren).
- Να περιγραφούν οι μέθοδοι αναζήτησης που υποστηρίζει η εργασία σας. Για την/τις ευριστικές μεθόδους αναζήτησης που θα χρησιμοποιηθούν να παρουσιαστεί το ευριστικό κριτήριο και ο ευριστικός μηχανισμός.
- Για κάθε μέθοδο αναζήτησης να σχεδιαστεί το δένδρο αναζήτησης (όχι εξαντλητικό) για την απλή εκδοχή του προβλήματος που παρουσιάστηκε παραπάνω. Αν το δένδρο προχωρά σε πολύ μεγάλο βάθος περιορίστε το στα πρώτα 4 βήματα και στα 3 τελευταία.
- Να παρουσιαστούν και να σχολιαστούν οι περιπτώσεις εξαντλητικού ελέγχου που θα χρησιμοποιήσετε για κάθε μέθοδο αναζήτησης και τα συμπεράσματα που θα βγάλετε από τη συγκριτική μελέτη των αποτελεσμάτων των δοκιμών σας μεταξύ διαφορετικών μεθόδων αναζήτησης.