Kako riješiti problem Hanojske kule - ilustrirani vodič za algoritam

Prije početka, razgovarajmo o tome u čemu je problem Tower of Hanoi. Pa, ovo je zabavna puzzle igra čiji je cilj premjestiti čitav niz diskova s ​​izvornog položaja na drugi položaj. Poštuju se tri jednostavna pravila:

  1. Istodobno se može premještati samo jedan disk.
  2. Svaki potez sastoji se od uzimanja gornjeg diska iz jednog od stogova i postavljanja na vrh drugog stoga. Drugim riječima, disk se može premjestiti samo ako je to najgornji disk na hrpi.
  3. Nijedan veći disk ne smije se postaviti na vrh manjeg diska.

Pokušajmo sada zamisliti scenarij. Pretpostavimo da imamo stog od tri diska. Naš posao je da se premjestiti ovaj snop papira iz izvora A na odredište C . Kako to radimo?

Prije nego što možete doći, neka je zamisliti da postoji srednji točka B .

Možemo koristiti B kao pomoćnika da završimo ovaj posao. Sada smo spremni za dalje. Prođimo kroz svaki od koraka:

  1. Pomaknite prvi disk s A na C
  2. Pomaknite prvi disk s A na B
  3. Premjestite prvi disk s C na B
  4. Pomaknite prvi disk s A na C
  5. Pomaknite prvi disk s B na A
  6. Pomaknite prvi disk s B na C
  7. Pomaknite prvi disk s A na C

Bum! Riješili smo svoj problem.

Za bolje razumijevanje možete vidjeti gornju animiranu sliku.

Pokušajmo sada izgraditi algoritam za rješavanje problema. Čekajte, ovdje imamo novu riječ: " Algoritam ". Što je to? Bilo koja ideja? Nema problema, da vidimo.

Što je algoritam?

Algoritam je jedan od najvažnijih koncepata za programera softvera. Zapravo, mislim da to nije važno samo za razvoj softvera ili programiranje, već i za sve. Algoritmi utječu na nas u našem svakodnevnom životu. Da vidimo kako.

Pretpostavimo da radite u uredu. Dakle, svako jutro radite niz zadataka u slijedu: prvo se probudite, a zatim idete u umivaonicu, jedete doručak, pripremite se za ured, napuštate dom, a zatim možete uzeti taksi ili autobus ili krenuti prema ulici ureda i nakon određenog vremena stižete do svog ureda. Možete reći da svi ti koraci tvore algoritam .

Jednostavno rečeno, algoritam je skup zadataka. Nadam se da niste zaboravili korake koje smo poduzeli za premještanje stoga s tri diska s A na C. Također možete reći da su ti koraci algoritam za rješavanje problema Tower of Hanoi.

U matematici i računarstvu algoritam je nedvosmislena specifikacija načina rješavanja klase problema. Algoritmi mogu izvršavati zadatke izračuna, obrade podataka i automatiziranog zaključivanja. - Wikipedija

Ako pogledate te korake, možete vidjeti da smo isti zadatak radili više puta - premještajući diskove iz jednog u drugi stog. Te korake unutar koraka možemo nazvati rekurzijom .

Rekurzija

Rekurzijapoziva istu akciju iz te akcije. Baš kao i gornja slika.

Dakle, postoji jedno pravilo za bilo koji rekurzivan posao: mora postojati uvjet da se zaustavi izvršavanje te radnje. Nadam se da razumijete osnove o rekurziji.

Pokušajmo sada izgraditi postupak koji nam pomaže riješiti problem Tower of Hanoi. Pokušavamo izgraditi rješenje pomoću pseudokoda . Pseudocode je metoda ispisivanja računalnog koda pomoću engleskog jezika.

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

Ovo je kostur našeg rješenja. Ukupan broj diskova uzimamo kao argument. Zatim trebamo proći izvor, srednje mjesto i odredište kako bismo mogli razumjeti kartu koju ćemo koristiti za dovršetak posla.

Sada moramo pronaći stanje terminala . Stanje terminala je stanje u kojem više nećemo pozivati ​​ovu funkciju.

IF disk is equal 1

U našem slučaju ovo bi bilo naše terminalno stanje. Jer kada će u našem stogu biti jedan disk, onda je jednostavno učiniti taj posljednji korak i nakon toga će naš zadatak biti gotov. Ne brinite ako vam nije jasno. Kad dođemo do kraja, ovaj će koncept biti jasniji.

Dobro, pronašli smo točku stanja terminala u kojoj premještamo disk na odredište ovako:

move disk from source to destination

Sada ponovno pozivamo svoju funkciju prosljeđivanjem ovih argumenata. U tom slučaju hrpu diskova dijelimo na dva dijela. Najveći disk ( n-ti disk) nalazi se u jednom dijelu, a svi ostali ( n-1 ) diskovi su u drugom dijelu. Tamo metodu nazivamo dva puta za - (n-1).

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

Kao što smo rekli, kao argument prosljeđujemo total_disks_on_stack - 1 . I onda opet premještamo naš disk ovako:

move disk from source to destination

Nakon toga svoju metodu opet nazivamo ovako:

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

Pogledajmo naš puni pseudokod:

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

Ovo je stablo za tri diska:

Ovo je puni kod u 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

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

Izlaz:

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

Trebalo je sedam koraka da tri diska dođu do odredišta. To nazivamo rekurzivnom metodom .

Izračun vremenske složenosti i složenosti prostora

Složenost vremena

Kada u našem stroju pokrenemo kod ili aplikaciju, potrebno je vrijeme - CPU ciklusi. Ali to nije isto za svako računalo. Primjerice, vrijeme obrade jezgre i7 i dvojezgrene jezgre nije isto. Da bi se riješio ovaj problem, u računalnoj znanosti se koristi koncept koji se naziva vremenska složenost .

Složenost vremena koncept je u računalnoj znanosti koji se bavi kvantifikacijom količine vremena potrebnog skupu koda ili algoritma za obradu ili pokretanje kao funkcija količine unosa.

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. The Google course on Udacity
  4. Javascript Algorithms And Data Structures Certification (300 hours)

You can visit my data structures and algorithms repoto see my other problems solutions.

I am on GitHub | Twitter | LinkedIn