Το Tetris αναδεικνύεται ένα από τα πιο δύσκολα προβλήματα μαθηματικών
Το γνωστό σε όλους μας Tetris είναι ένα από τα πιο δύσκολα προβλήματα μαθηματικών, όπως απέδειξαν επιστήμονες από το Τεχνολογικό Ινστιτούτο της Μασαχουσέτης. Πρόκειται για ένα ακόμα πρόβλημα NP-πλήρες.
39
Το Tetris είναι ένα από τα πιο γνωστά παιχνίδια υπολογιστών που έχουν κυκλοφορήσει ποτέ και μέρος της δημοτικότητάς του οφείλεται και στη δυσκολία του. Σκοπός του παιχνιδιού είναι η κατάλληλη μετακίνηση και περιστροφή τυχαίων γεωμετρικών σχημάτων που πέφτουν ώστε να συμπληρωθούν σειρές στη βάση του ταμπλό του παιχνιδιού. Τώρα, μαθηματικοί απέδειξαν ότι το Tetris είναι ένα από τα πιο δύσκολα προβλήματα προς επίλυση, ακόμα και όταν ο παίκτης γνωρίζει ποιό σχήμα έπεται.
Ειδικότερα, οι επιστήμονες του Τεχνολογικού Ινστιτούτου της Μασαχουσέτης έδειξαν ότι πρόκειται για ένα πρόβλημα στο οποίο εφαρμόζεται η θεωρία της NP-πληρότητας.
Η θεωρία αυτή παρέχει ένα σύνολο από τεχνικές, με τις οποίες αποδεικνύουμε ότι ένα πρόβλημα είναι εξίσου δύσκολο με ένα σύνολο από ανάλογα προβλήματα που απασχολούν τους θεωρητικούς εδώ και πολύ καιρό.
Αν μπορέσουμε να αποδείξουμε ότι ένα πρόβλημα -στην προκειμένη περίπτωση το Tetris- είναι εξίσου δύσκολο π.χ. με το πρόβλημα του περιοδεύοντος πωλητή τότε δεν σπαταλάμε πλέον χρόνο για την κατασκευή πολυωνυμικού αλγορίθμου και μπορούμε να εφαρμόσουμε ένα σύνολο από γνωστές τεχνικές, με τις οποίες λύνονται τα προβλήματα αυτά, όπως προσεγγιστικούς αλγορίθμους.
Με απλά λόγια, αν και είναι εύκολο να ελέγξει κανείς ότι μια λύση είναι έγκυρη, δεν υπάρχει αποτελεσματικός τρόπος για να βελτιστοποιήσουμε οποιοδήποτε από τους στόχους του παιχνιδιού. Δηλαδή, να μεγιστοποιήσουμε τον αριθμό των σειρών που συμπληρώνονται, τον αριθμό των γεωμετρικών σχημάτων που τοποθετούνται επιτυχώς πριν χάσουμε, τον αριθμό των τετράδων που συμπληρώνονται και να διατηρήσουμε το ύψος όσο το δυνατόν πιο χαμηλά κατά τη διάρκεια του παιχνιδιού. Κι όλα αυτά, ακόμα και όταν γνωρίζουμε εκ των προτέρων το σχήμα που θα κληθούμε να τοποθετήσουμε σωστά.
Ένα ακόμα πρόβλημα NP-πλήρες είναι ο ναρκαλιευτής, αναφέρει το Scientific American. Οπότε, την επόμενη φορά που θα αποτύχετε σε ένα από τα δύο αυτά προβλήματα θα ξέρετε ότι και ένας υπολογιστής δεν θα τα κατάφερνε πολύ καλύτερα -τουλάχιστον σε ικανοποιητικό χρόνο.
Newsroom ΑΛΤΕΡ ΕΓΚΟ
- Ζαχαριάδης: «Την αξιωματική αντιπολίτευση την ορίζει ο λαός με εκλογές – Δεν ψήφισε Ανδρουλάκη για αρχηγό»
- FY & Αλεξία Κεφαλά: Μαζί στη ζωή, μαζί και στο MadWalk
- Βίκτορ Όρμπαν: Θα προσκαλέσει τον Μπενιαμίν Νετανιάχου στην Ουγγαρία σε κόντρα με το ένταλμα σύλληψης του ΔΠΔ
- ΑΕΚ: Το μεγάλο ξεσκαρτάρισμα του Γενάρη – Το… σχέδιο Ριμπάλτα και οι «5» που είναι σε δύσκολη θέση
- Η πρώτη επίσημη συνάντηση Ανδρουλάκη ως αρχηγός της αξιωματικής αντιπολίτευσης
- Σοφία Βεργκάρα: Ετοιμάζεται για την φετινή Γιορτή των Ευχαριστιών με ένα ξεχωριστό χορό
