| Περίληψη: | Η διπλωματική αυτή εργασία πραγματεύεται την αυτόματη κατασκευή και επίλυση θεματικών σταυρολέξων στην αγγλική γλώσσα μέσω εφαρμογής στο διαδικτυακό ιστό (Web). Το πρόβλημα αυτό αποτελείται απο τη διάκριση τριών υποπροβλημάτων όσον αφορά την δημιουργία του αλγορίθμου. Το πρώτο είναι η συμπλήρωση των λευκών κελιών ενός τετραγώνου του πλέγματος με γράμματα, ώστε να σχηματιστούν από τη μία έγκυρες, ταυτόχρονα όμως και θεμιτό ποσοστό από θεματικές λέξεις και στις δύο κατευθύνσεις, δηλαδή οριζοντίως και καθέτως. Το δεύτερο πρόβλημα είναι η συμπλήρωση των μαύρων κελιών για τα οποία υπάρχουν κάποιες προϋποθέσεις ώστε να διευκολύνει μεν την κατασκευή, από την άλλη να μην χαλάει τον πόλο έλξης του λύτη για την επίλυση του σταυρολέξου. Τρίτο πρόβλημα, είναι η δημιουργία κατάλληλων εννοιών - ορισμών που θα δώσουν στον λύτη μία κατεύθυνση για να μπορέσει να μαντέψει την απάντηση.
Το πρώτο πρόβλημα αντιμετωπίστηκε ως ένα πρόβλημα ικανοποίησης περιορισμών (SCP), δηλαδή ένας αλγόριθμος με μεταβλητές τα μη συμπληρωμένα μπλοκ λευκών κελιών πάνω στο πλέγμα και περιορισμούς το μήκος των λέξεων και το εκάστοτε σχηματισμό της λέξης. Έτσι, για την υλοποίηση χρησιμοποιήθηκε κατά βάση ένας αλγόριθμος, ο οποίος επιλέγει μια στρατηγική γεμίσματος μπλοκ και μετά μια στρατηγική επιλογής λέξης. Η σειρά επιλογής μπλοκ ξεκινάει με το γέμισμα των τριών πρώτων θεματικών μπλοκ. Οι λέξεις αντλούνται από το λεξικό θησαυρός WordNet, αλλά και από το παγκόσμιο διαδικτυακό ιστό μέσω της διαδικασίας εύρεσης σχετικών λέξεων από την αναζήτηση του θέματος. Ο αλγόριθμος, στη διαδικασία επιλογής λέξεων εκτελεί έλεγχο συνέπειας και χρησιμοποιεί τρεις διαφορετικούς τρόπους για την ολοκλήρωση του σε περίπτωση που φτάσει σε αδιέξοδο και πριν επιστρέψει στο προηγούμενο μπλοκ (backtracking), όπως η χαλάρωση των λέξεων ή η αντιστροφή μια λέξης.
Το δεύτερο πρόβλημα, η διαδικασία συμπλήρωσης των μαύρων κελιών, λύθηκε ως ένα πρόβλημα καλύτερου μονοπατιού επιλογής κελιών που θα μειώσουν την πολυπλοκότητα του πλέγματος κατά τη συμπλήρωση του (αλγόριθμος Dijkstra). Δηλαδή αρχικά επιλέγει τον τυχαίο αριθμό που θα συμπληρώσει τα συμμετρικά κελιά και σε κάθε τοποθέτηση αυτών βρίσκει τα διαθέσιμα κελιά για συμπλήρωση στο πλέγμα με βάση τους περιορισμούς του σταυρολέξου.
Το τρίτο πρόβλημα, η δημιουργία του εννοιών - ορισμών διεκπεραιώθηκε με την άντληση κυρίως από τα δεδομένα του λεξικού WordNet αλλά και την αναζήτηση μέσω του Google Spider. Για κάθε απάντηση που δημιουργήθηκε στο πλέγμα αναζητήσαμε είτε ορισμούς είτε παραδείγματα από το λεξικό και σε περίπτωση που δεν βρέθηκε κάτι τέτοιο αναζητήσαμε τη λέξη στο διαδίκτυο ώστε να βρούμε κάποιο αντίστοιχο ορισμό ή παράδειγμα.
Η εφαρμογή αυτή κατάφερε να ανταποκριθεί σε πολλές δοκιμές διαφόρων μεγεθών σταυρολέξου (11x11, 13x13, 15x15) και ο αλγόριθμος να κριθεί αποδοτικός. Τελικός σκοπός ήταν η αξιοπιστία και η εγκυρότητα του σταυρολέξου, όπου με βάση τις παραμέτρους του χρήστη πραγματοποιείται η αυτόματη κατασκευή, όπου και το καταφέραμε. Για τις στρατηγικές απόφασης σε κάθε βήμα του αλγορίθμου, έχει γίνει συγκριτική αξιολόγηση όλων των δεδομένων που είχαμε και καταλήξαμε στους καλύτερους δυνατούς συνδυασμούς.
|
|---|
