Αλγόριθμοι βέλτιστης επίλυσης για τον κύβο του Ρούμπικ
Loading...
Date
2026-07-06
Authors
Τόσκα, Αλέξανδρος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Η παρούσα διπλωματική εργασία μελετά αλγορίθμους επίλυσης του κύβου του Rubik 3×3×3 και ειδικά το ζήτημα της βέλτιστης λύσης: πότε μια ακολουθία κινήσεων λύνει απλώς τον κύβο και πότε μπορεί να αποδειχθεί ότι είναι η συντομότερη. Το επίσημο θέμα ζητά την υλοποίηση των αλγορίθμων Thistlethwaite, Kociemba και Korf, τον υπολογισμό της απόστασης μιας κατάστασης από τη λυμένη θέση και την επιλογή ευρετικής συνάρτησης για αναζήτηση τύπου A* ή παραλλαγή της. Η εργασία ακολουθεί αυτούς τους τρεις άξονες. Υλοποιείται μοντέλο του κύβου με βάση τα κυβίδια, με ελέγχους φυσικής εγκυρότητας και ανεξάρτητη επαλήθευση των λύσεων. Πάνω σε αυτό το μοντέλο υλοποιούνται οι τρεις αλγόριθμοι. Ο Korf δίνεται ως αναζήτηση IDA* με παραδεκτές ευρετικές από βάσεις δεδομένων προτύπων, ενώ οι Kociemba και Thistlethwaite χρησιμοποιούνται ως πρακτικοί επιλυτές. Για τον υπολογισμό απόστασης, το πρόγραμμα δίνει ακριβή τιμή μόνο όταν η αναζήτηση ολοκληρώνει την απόδειξη· διαφορετικά αναφέρει κάτω φράγμα, λήξη χρονικού ορίου ή άκυρη κατάσταση. Τα πειράματα παρουσιάζουν τι πετυχαίνει κάθε προσέγγιση στο επιλεγμένο σύνολο δοκιμών. Ο κώδικας της εργασίας αποδεικνύει βελτιστότητα έως απόσταση 14, καθώς και για το superflip (απόσταση 20). Για βαθύτερες ακριβείς περιπτώσεις χρησιμοποιείται εξωτερική μηχανή ως έλεγχος αναφοράς. Το superflip εξετάζεται ως δύσκολη περίπτωση του κύβου 3×3×3, ενώ ο κύβος 2×2×2 (Pocket Cube) χρησιμοποιείται ως μικρότερο παράδειγμα όπου μπορεί να γίνει πλήρης εξαντλητική μελέτη. Τα αποτελέσματα συνοδεύονται από σενάρια αναπαραγωγής, ώστε να φαίνεται ποιες λύσεις είναι απλώς επαληθευμένες, ποιες είναι αποδεδειγμένα βέλτιστες και ποιες αναζητήσεις δεν ολοκληρώθηκαν. Ο κώδικας, μαζί με τα σενάρια αναπαραγωγής των μετρήσεων και τα δεδομένα εισόδου των πειραμάτων, είναι δημόσια διαθέσιμος στη διεύθυνση: https://github.com/AlexTs10/rubik-optimal
Description
Keywords
Κύβος του Rubik, Βέλτιστη επίλυση, Παραδεκτή ευρετική