Σχεδιασμός και υλοποίηση σοβαρού παιγνίου για τον υπολογισμό ελάχιστων μονοπατιών
Loading...
Date
2026-10-09
Authors
Λέκας, Μιλτιάδης
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Η κατανόηση και η επίλυση προβλημάτων που αφορούν δίκτυα αποτελεί, από τα πρώτα βήματα της επιστήμης των υπολογιστών, έναν από τους πιο γόνιμους τομείς μελέτης. Ο άνθρωπος διαπίστωσε νωρίς ότι μπορεί να μοντελοποιήσει τις σχέσεις και τιςαλληλεπιδράσεις ανάμεσα σε τόπους, πρόσωπα ή έννοιες χρησιμοποιώντας δομές που ονομάζονται γραφήματα. Όταν ένα γράφημα αναπαριστά ένα δίκτυο, οι κορυφές του αντιστοιχούν σε κόμβους και οι ακμές του σε συνδέσμους, ενώ όταν σε κάθε σύνδεσμο αποδοθεί ένα αριθμητικό βάρος, το γράφημα αποκτά τη δυνατότητα να περιγράψει αποστάσεις, κόστη ή χρόνους διαδρομής.Το πρόβλημα της εύρεσης ελαχίστων μονοπατιών, δηλαδή της ανακάλυψης της διαδρομής με το μικρότερο δυνατό συνολικό βάρος ανάμεσα σε δύο κορυφές ενός σταθμισμένου γραφήματος, είναι από τα πιο διαδεδομένα προβλήματα της θεωρίας γραφημάτων. Η πιο γνωστή αλγοριθμική του λύση διατυπώθηκε το 1959 από τον Ολλανδό επιστήμονα Edsger W. Dijkstra και χρησιμοποιείται μέχρι σήμερα σε συστήματα δορυφορικής πλοήγησης, σε πρωτόκολλα δρομολόγησης δικτύων, στη βελτιστοποίηση εφοδιαστικών αλυσίδων και σε πλήθος άλλων εφαρμογών. Η κατανόηση του αλγορίθμου δεν είναι όμως πάντα εύκολη, καθώς απαιτεί την ταυτόχρονη παρακολούθηση πολλών μεγεθών που μεταβάλλονται σε κάθε βήμα, με αποτέλεσμα οι φοιτητές συχνά να απομνημονεύουν τα βήματα χωρίς να κατανοούν τη λογική τους.Τα σοβαρά παίγνια, δηλαδή ψηφιακές εφαρμογές οι οποίες αξιοποιούν αρχές και μηχανισμούς παιχνιδιού έχοντας ως κύριο στόχο την εκπαίδευση και όχι μόνο την ψυχαγωγία, προσφέρουν μια εναλλακτική προσέγγιση. Μέσω της αλληλεπίδρασης, της διαδραστικότητας και της αίσθησης επιτεύγματος που προσφέρουν, λειτουργούν ως αποτελεσματικά εργαλεία διδασκαλίας και κατανόησης σύνθετων εννοιών.Στο πλαίσιο της παρούσας διπλωματικής εργασίας παρουσιάζεται το σοβαρό παίγνιο «Dijkstra Quest», το οποίο αποσκοπεί να βοηθήσει φοιτητές και κάθε ενδιαφερόμενο να κατανοήσουν το πρόβλημα εύρεσης ελαχίστων μονοπατιών και να εξοικειωθούν με τον αλγόριθμο του Dijkstra. Σύμφωνα με το σενάριο του παιχνιδιού, οι παίκτες καλούνται να χαράξουν τη συντομότερη διαδρομή ανάμεσα σε δύο τοποθεσίες ενός φανταστικού οδικού δικτύου, επιλέγοντας οι ίδιοι τους δρόμους που τη συνθέτουν, πριν τους αποκαλυφθεί η λύση.Το παιχνίδι προσφέρει δύο μορφές, τον «Αγώνα», στον οποίο η απάντησηχρονομετρείται και βαθμολογείται, και την «Εκπαίδευση», στην οποία ο παίκτης μπορεί να παρακολουθήσει την εκτέλεση του αλγορίθμου βήμα προς βήμα πάνω στο ίδιο τογράφημα, χωρίς πίεση χρόνου. Και στις δύο περιπτώσεις τα οδικά δίκτυα παράγονται αυτόματα ως τυχαία σταθμισμένα γραφήματα, σε τέσσερα επίπεδα δυσκολίας, ενώ ο έλεγχος της απάντησης του παίκτη γίνεται με τρόπο που αναγνωρίζει και τις ισοδύναμες βέλτιστες διαδρομές.Το παιχνίδι μας είναι διαθέσιμο στα ελληνικά και στα αγγλικά και είναι ελεύθερα προσβάσιμο μέσω οποιουδήποτε προγράμματος περιήγησης ιστού. Έχει αναπτυχθεί ως διαδικτυακή εφαρμογή με τεχνολογίες ανοικτού κώδικα, με τη γλώσσα JavaScript τόσο στον διακομιστή όσο και στον φυλλομετρητή, και φιλοξενείται στην πλατφόρμα νέφους Railway.
Description
Keywords
Σοβαρά παίγνια, Ελάχιστα μονοπάτια, Συντομότερη διαδρομή, Τυχαία γραφήματα, Οπτικοποίηση αλγορίθμων