Πώς να επιλύσετε το πρόβλημα του Πύργου του Ανόι - Ένας εικονογραφημένος οδηγός αλγόριθμου

Πριν ξεκινήσετε, ας μιλήσουμε για το τι είναι το πρόβλημα του Πύργου του Ανόι. Λοιπόν, αυτό είναι ένα διασκεδαστικό παιχνίδι παζλ όπου ο στόχος είναι να μετακινήσετε μια ολόκληρη στοίβα δίσκων από τη θέση προέλευσης σε άλλη θέση. Ακολουθούν τρεις απλοί κανόνες:

  1. Μόνο ένας δίσκος μπορεί να μετακινηθεί κάθε φορά.
  2. Κάθε κίνηση συνίσταται στο να πάρουμε τον πάνω δίσκο από μία από τις στοίβες και να τον τοποθετήσουμε πάνω από μια άλλη στοίβα. Με άλλα λόγια, ένας δίσκος μπορεί να μετακινηθεί μόνο εάν είναι ο ανώτερος δίσκος σε μια στοίβα.
  3. Δεν μπορεί να τοποθετηθεί μεγαλύτερος δίσκος πάνω από έναν μικρότερο δίσκο.

Τώρα, ας προσπαθήσουμε να φανταστούμε ένα σενάριο. Ας υποθέσουμε ότι έχουμε μια στοίβα τριών δίσκων. Η δουλειά μας είναι να μεταφέρουμε αυτήν τη στοίβα από την πηγή Α στον προορισμό Γ . Πώς το κάνουμε αυτό;

Προτού φτάσουμε εκεί, ας υποθέσουμε ότι υπάρχει ένα ενδιάμεσο σημείο Β .

Μπορούμε να χρησιμοποιήσουμε το B ως βοηθός για να ολοκληρώσουμε αυτήν την εργασία. Είμαστε τώρα έτοιμοι να προχωρήσουμε. Ας ακολουθήσουμε κάθε ένα από τα βήματα:

  1. Μετακινήστε τον πρώτο δίσκο από το Α στο Γ
  2. Μετακινήστε τον πρώτο δίσκο από το Α στο Β
  3. Μετακινήστε τον πρώτο δίσκο από C σε B
  4. Μετακινήστε τον πρώτο δίσκο από το Α στο Γ
  5. Μετακινήστε τον πρώτο δίσκο από το Β στο Α
  6. Μετακινήστε τον πρώτο δίσκο από B σε C
  7. Μετακινήστε τον πρώτο δίσκο από το Α στο Γ

Κεραία! Λύσαμε το πρόβλημά μας.

Μπορείτε να δείτε την κινούμενη εικόνα παραπάνω για καλύτερη κατανόηση.

Τώρα, ας προσπαθήσουμε να δημιουργήσουμε τον αλγόριθμο για την επίλυση του προβλήματος. Περιμένετε, έχουμε μια νέα λέξη εδώ: « Αλγόριθμος ». Τι ΕΙΝΑΙ ΑΥΤΟ? Καμια ιδεα? Κανένα πρόβλημα, ας δούμε.

Τι είναι ο αλγόριθμος;

Ένας αλγόριθμος είναι μια από τις πιο σημαντικές έννοιες για έναν προγραμματιστή λογισμικού. Στην πραγματικότητα, νομίζω ότι δεν είναι μόνο σημαντικό για την ανάπτυξη λογισμικού ή τον προγραμματισμό, αλλά για όλους. Οι αλγόριθμοι μας επηρεάζουν στην καθημερινή μας ζωή. Ας δούμε πώς.

Ας υποθέσουμε ότι εργάζεστε σε ένα γραφείο. Έτσι κάθε πρωί κάνετε μια σειρά εργασιών διαδοχικά: πρώτα ξυπνάτε, μετά πηγαίνετε στην τουαλέτα, τρώτε πρωινό, ετοιμάζεστε για το γραφείο, φεύγετε από το σπίτι, τότε μπορείτε να πάρετε ταξί ή λεωφορείο ή να αρχίσετε να περπατάτε προς γραφείο και, μετά από ένα ορισμένο χρονικό διάστημα, φτάνετε στο γραφείο σας. Μπορείτε να πείτε ότι όλα αυτά τα βήματα αποτελούν αλγόριθμο .

Με απλά λόγια, ένας αλγόριθμος είναι ένα σύνολο εργασιών. Ελπίζω ότι δεν έχετε ξεχάσει αυτά τα βήματα που κάναμε για να μετακινήσουμε τρεις στοίβες δίσκων από το Α στο C. Μπορείτε επίσης να πείτε ότι αυτά τα βήματα είναι ο αλγόριθμος για την επίλυση του προβλήματος του Πύργου του Ανόι.

Στα μαθηματικά και την επιστήμη των υπολογιστών, ένας αλγόριθμος είναι μια ξεκάθαρη προδιαγραφή για το πώς να λυθεί μια κατηγορία προβλημάτων. Οι αλγόριθμοι μπορούν να εκτελούν υπολογισμούς, επεξεργασία δεδομένων και αυτοματοποιημένες εργασίες συλλογισμού. - Βικιπαίδεια

Εάν ρίξετε μια ματιά σε αυτά τα βήματα, μπορείτε να δείτε ότι κάναμε την ίδια εργασία πολλές φορές - μετακίνηση δίσκων από τη μία στοίβα στην άλλη. Μπορούμε να καλέσουμε αυτά τα βήματα σε επαναλαμβανόμενα βήματα .

Αναδρομή

Αναδρομήκαλεί την ίδια δράση από αυτήν την ενέργεια. Όπως και η παραπάνω εικόνα.

Υπάρχει λοιπόν ένας κανόνας για να κάνετε οποιαδήποτε αναδρομική εργασία: πρέπει να υπάρχει μια προϋπόθεση για να σταματήσετε την εκτέλεση αυτής της ενέργειας. Ελπίζω να καταλάβετε τα βασικά για την αναδρομή.

Τώρα, ας προσπαθήσουμε να χτίσουμε μια διαδικασία που θα μας βοηθήσει να λύσουμε το πρόβλημα του Πύργου του Ανόι. Προσπαθούμε να δημιουργήσουμε τη λύση χρησιμοποιώντας ψευδοκώδικα . Ο ψευδοκώδικας είναι μια μέθοδος σύνταξης κώδικα υπολογιστή χρησιμοποιώντας την αγγλική γλώσσα.

tower(disk, source, intermediate, destination) { }

Αυτός είναι ο σκελετός της λύσης μας. Λαμβάνουμε τον συνολικό αριθμό δίσκων ως όρισμα. Στη συνέχεια, πρέπει να περάσουμε την πηγή, το ενδιάμεσο μέρος και τον προορισμό, ώστε να κατανοήσουμε τον χάρτη που θα χρησιμοποιήσουμε για την ολοκλήρωση της εργασίας.

Τώρα πρέπει να βρούμε μια κατάσταση τερματικού . Η κατάσταση τερματικού είναι η κατάσταση στην οποία δεν πρόκειται να καλέσουμε αυτήν τη λειτουργία πια.

IF disk is equal 1

Στην περίπτωσή μας, αυτή θα ήταν η τελική μας κατάσταση. Επειδή όταν θα υπάρχει ένας δίσκος στη στοίβα μας, τότε είναι εύκολο να κάνουμε αυτό το τελικό βήμα και μετά από αυτό θα γίνει η εργασία μας. Μην ανησυχείτε εάν δεν είναι σαφές για εσάς. Όταν φτάσουμε στο τέλος, αυτή η ιδέα θα είναι σαφέστερη.

Εντάξει, βρήκαμε το σημείο κατάστασης του τερματικού μας όπου μετακινούμε τον δίσκο μας στον προορισμό ως εξής:

move disk from source to destination

Τώρα καλούμε ξανά τη λειτουργία μας περνώντας αυτά τα επιχειρήματα. Σε αυτήν την περίπτωση, χωρίζουμε τη στοίβα των δίσκων σε δύο μέρη. Ο μεγαλύτερος δίσκος ( nth disk) βρίσκεται σε ένα μέρος και όλοι οι άλλοι δίσκοι ( n-1 ) βρίσκονται στο δεύτερο μέρος. Εκεί καλούμε τη μέθοδο δύο φορές για - (n-1).

tower(disk - 1, source, destination, intermediate)

Όπως είπαμε περνάμε το total_disks_on_stack - 1 ως επιχείρημα. Και πάλι μετακινούμε τον δίσκο μας έτσι:

move disk from source to destination

Μετά από αυτό καλούμε ξανά τη μέθοδο μας ως εξής:

tower(disk - 1, intermediate, source, destination)

Ας δούμε τον πλήρη ψευδοκώδικα μας:

tower(disk, source, inter, dest) IF disk is equal 1, THEN move disk from source to destination ELSE tower(disk - 1, source, destination, intermediate) // Step 1 move disk from source to destination // Step 2 tower(disk - 1, intermediate, source, destination) // Step 3 END IF END

Αυτό είναι το δέντρο για τρεις δίσκους:

Αυτός είναι ο πλήρης κωδικός στο Ruby:

def tower(disk_numbers, source, auxilary, destination) if disk_numbers == 1 puts "#{source} -> #{destination}" return end tower(disk_numbers - 1, source, destination, auxilary) puts "#{source} -> #{destination}" tower(disk_numbers - 1, auxilary, source, destination) nil end

Κλήση tower(3, 'source','aux','dest')

Παραγωγή:

source -> dest source -> aux dest -> aux source -> dest aux -> source aux -> dest source -> dest

Χρειάστηκαν επτά βήματα για να φτάσουν τρεις δίσκοι στον προορισμό. Το ονομάζουμε αναδρομική μέθοδο .

Υπολογισμοί πολυπλοκότητας χρόνου και πολυπλοκότητας χώρου

Χρόνος πολυπλοκότητας

Όταν εκτελούμε κώδικα ή μια εφαρμογή στο μηχάνημά μας χρειάζεται χρόνος - κύκλοι CPU. Αλλά δεν είναι το ίδιο για κάθε υπολογιστή. Για παράδειγμα, ο χρόνος επεξεργασίας για έναν πυρήνα i7 και έναν διπλό πυρήνα δεν είναι ο ίδιος. Για την επίλυση αυτού του προβλήματος υπάρχει μια έννοια που χρησιμοποιείται στην επιστήμη των υπολογιστών που ονομάζεται χρονική πολυπλοκότητα .

Η πολυπλοκότητα του χρόνου είναι μια έννοια στην επιστήμη των υπολογιστών που ασχολείται με την ποσοτικοποίηση του χρόνου που απαιτείται από ένα σύνολο κώδικα ή αλγορίθμου για την επεξεργασία ή την εκτέλεση ως συνάρτηση του ποσού της εισαγωγής.

In other words, time complexity is essentially efficiency, or how long a program function takes to process a given input. — techopedia

The time complexity of algorithms is most commonly expressed using big O notation. It’s an asymptotic notation to represent the time complexity.

Now, the time required to move n disks is T(n). There are two recursive calls for (n-1). There is one constant time operation to move a disk from source to the destination, let this be m1. Therefore:

T(n) = 2T(n-1) + m1 ..... eq(1)

And

T(0) = m2, a constant ...... eq(2) From eq (1) T(1) = 2T(1-1) + m1 = 2T(0)+m1 = 2m2 + m1 ..... eq(3) [From eq 2] T(2) = 2T(2-1) + m1 = 2T(1) + m1 = 4m2 + 2m1 + m1 .... eq(4) [From eq(3)] T(3) = 2T(3-1) + m1 = 2T(2) + m1 = 8m2 + 4m1 + 2m1 + m1 [From eq(4)]

From these patterns — eq(2) to the last one — we can say that the time complexity of this algorithm is O(2^n) or O(a^n) where a is a constant greater than 1. So it has exponential time complexity. For the single increase in problem size, the time required is double the previous one. This is computationally very expensive. Most of the recursive programs take exponential time, and that is why it is very hard to write them iteratively.

Space complexity

After the explanation of time complexity analysis, I think you can guess now what this is…This is the calculation of space required in ram for running a code or application.

In our case, the space for the parameter for each call is independent of n,meaning it is constant. Let it be J. When we do the second recursive call, the first one is over. That means that we can reuse the space after finishing the first one. Hence:

T(n) = T(n-1) + k .... eq(1) T(0) = k, [constant] .... eq(2) T(1) = T(1-1) + k = T(0) + k = 2K T(2) = 3k T(3) = 4k

So the space complexity is O(n).

After these analyses, we can see that time complexity of this algorithm is exponential but space complexity is linear.

Conclusion

From this article, I hope you can now understand the Tower of Hanoi puzzle and how to solve it. Also, I tried to give you some basic understanding about algorithms, their importance, recursion, pseudocode, time complexity, and space complexity. If you want to learn these topics in detail, here are some well-known online courses links:

  1. Algorithms, Part I
  2. Algorithms, Part II
  3. Το μάθημα Google για το Udacity
  4. Πιστοποίηση αλγορίθμων και δομών δεδομένων Javascript (300 ώρες)

Μπορείτε να επισκεφθείτε τη δομή δεδομένων μου και το repo αλγορίθμωννα δω τις λύσεις μου για άλλα προβλήματα.

Είμαι στο GitHub | Twitter | LinkedIn