Sådan løses tårnet i Hanoi-problemet - en illustreret algoritmevejledning

Lad os tale om, hvad Tower of Hanoi-problemet er, før vi kommer i gang. Nå, dette er et sjovt puslespil, hvor målet er at flytte en hel stak diske fra kildepositionen til en anden position. Tre enkle regler følges:

  1. Kun en disk kan flyttes ad gangen.
  2. Hvert træk består i at tage den øverste disk fra en af ​​stakkene og placere den oven på en anden stak. Med andre ord kan en disk kun flyttes, hvis den er den øverste disk på en stak.
  3. Ingen større disk må placeres oven på en mindre disk.

Lad os nu forestille os et scenarie. Antag, at vi har en stak på tre diske. Vores opgave er at flytte denne stak fra kilde A til destination C . Hvordan gør vi dette?

Lad os forestille os, at der er et mellemliggende punkt B, inden vi kan komme derhen .

Vi kan bruge B som hjælper til at afslutte dette job. Vi er nu klar til at komme videre. Lad os gennemgå hvert af trinene:

  1. Flyt den første disk fra A til C
  2. Flyt den første disk fra A til B.
  3. Flyt den første disk fra C til B.
  4. Flyt den første disk fra A til C
  5. Flyt den første disk fra B til A
  6. Flyt den første disk fra B til C
  7. Flyt den første disk fra A til C

Boom! Vi har løst vores problem.

Du kan se det animerede billede ovenfor for en bedre forståelse.

Lad os nu prøve at opbygge algoritmen til at løse problemet. Vent, vi har et nyt ord her: " Algoritme ". Hvad er det? Enhver idé? Intet problem, lad os se.

Hvad er en algoritme?

En algoritme er et af de vigtigste begreber for en softwareudvikler. Faktisk tror jeg, det ikke kun er vigtigt for softwareudvikling eller programmering, men for alle. Algoritmer påvirker os i vores hverdag. Lad os se hvordan.

Antag at du arbejder på et kontor. Så hver morgen gør du en række opgaver i rækkefølge: først vågner du op, så går du i vaskerummet, spiser morgenmad, bliver forberedt på kontoret, forlader hjemmet, så kan du tage en taxa eller bus eller begynde at gå mod kontor, og efter en vis tid når du dit kontor. Du kan sige, at alle disse trin udgør en algoritme .

Enkelt sagt er en algoritme et sæt opgaver. Jeg håber, du ikke har glemt de trin, vi gjorde for at flytte tre diskstak fra A til C. Du kan også sige, at disse trin er algoritmen til at løse Tower of Hanoi-problemet.

I matematik og datalogi er en algoritme en entydig specifikation af, hvordan man løser en klasse af problemer. Algoritmer kan udføre beregninger, databehandling og automatiserede ræsonnementsopgaver. - Wikipedia

Hvis du ser på disse trin, kan du se, at vi udførte den samme opgave flere gange - flytning af diske fra en stak til en anden. Vi kan kalde disse trin inden for trinrekursion .

Rekursion

Rekursionkalder den samme handling fra den handling. Ligesom ovenstående billede.

Så der er én regel for at udføre ethvert rekursivt arbejde: der skal være en betingelse for at stoppe den handling, der udføres. Jeg håber, du forstår det grundlæggende om rekursion.

Lad os nu prøve at opbygge en procedure, der hjælper os med at løse Tower of Hanoi-problemet. Vi forsøger at opbygge løsningen ved hjælp af pseudokode . Pseudokode er en metode til at udskrive computerkode ved hjælp af det engelske sprog.

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

Dette er skelettet til vores løsning. Vi tager det samlede antal diske som et argument. Så er vi nødt til at sende kilde, mellemliggende sted og destinationen, så vi kan forstå det kort, som vi vil bruge til at fuldføre jobbet.

Nu skal vi finde en terminaltilstand . Terminaltilstanden er den tilstand, hvor vi ikke længere kalder denne funktion.

IF disk is equal 1

In our case, this would be our terminal state. Because when there will be one disk in our stack then it is easy to just do that final step and after that our task will be done. Don’t worry if it’s not clear to you. When we reach the end, this concept will be clearer.

Alright, we have found our terminal state point where we move our disk to the destination like this:

move disk from source to destination

Now we call our function again by passing these arguments. In that case, we divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part. There we call the method two times for -(n-1).

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

As we said we pass total_disks_on_stack — 1 as an argument. And then again we move our disk like this:

move disk from source to destination

After that we again call our method like this:

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

Lad os se vores fulde pseudokode:

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

Dette er træet til tre diske:

Dette er den fulde kode i 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

Opkald tower(3, 'source','aux','dest')

Produktion:

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

Det tog syv trin for tre diske at nå destinationen. Vi kalder dette en rekursiv metode .

Tidskompleksitet og rumkompleksitetsberegninger

Tidskompleksitet

Når vi kører kode eller et program i vores maskine, tager det tid - CPU-cyklusser. Men det er ikke det samme for hver computer. For eksempel er behandlingstiden for en kerne i7 og en dobbeltkerne ikke den samme. For at løse dette problem findes der et koncept, der anvendes inden for datalogi kaldet tidskompleksitet .

Tidskompleksitet er et begreb inden for datalogi, der beskæftiger sig med kvantificeringen af ​​den tid, det tager af et sæt kode eller algoritme at behandle eller køre som en funktion af mængden af ​​input.

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-kurset om Udacity
  4. Javascript-algoritmer og datastrukturer-certificering (300 timer)

Du kan besøge mine datastrukturer og algoritmer repoat se mine andre problemløsninger.

Jeg er på GitHub | Twitter | LinkedIn