Как да решим проблема с кулата на Ханой - илюстрирано ръководство за алгоритъм

Преди да започнем, нека поговорим какъв е проблемът на Ханойската кула. Е, това е забавна пъзел игра, при която целта е да се премести цял стек дискове от позицията на източника на друга позиция. Следват се три прости правила:

  1. Едновременно може да се премества само един диск.
  2. Всеки ход се състои от вземане на горния диск от един от стековете и поставянето му върху друг стек. С други думи, диск може да бъде преместен само ако е най-горният диск в стека.
  3. Не може да се поставя по-голям диск върху по-малък диск.

Сега, нека се опитаме да си представим сценарий. Да предположим, че имаме купчина от три диска. Нашата работа е да се премести тази купчина от източник А до дестинация C . Как да направим това?

Преди да можем да стигнем до там, нека си представим, има междинна точка Б .

Можем да използваме B като помощник, за да завършим тази работа. Вече сме готови да продължим напред. Нека да преминем през всяка от стъпките:

  1. Преместете първия диск от A в C
  2. Преместете първия диск от A в B
  3. Преместете първия диск от C в B
  4. Преместете първия диск от A в C
  5. Преместете първия диск от B в A
  6. Преместете първия диск от B в C
  7. Преместете първия диск от A в C

Бум! Решихме проблема си.

Можете да видите анимираното изображение по-горе за по-добро разбиране.

Сега, нека се опитаме да изградим алгоритъма за решаване на проблема. Чакай, тук имаме нова дума: „ Алгоритъм “. Какво е това? Някаква идея? Няма проблем, да видим.

Какво е алгоритъм?

Алгоритъмът е една от най-важните концепции за разработчика на софтуер. Всъщност мисля, че това е важно не само за разработването или програмирането на софтуер, но и за всички. Алгоритмите ни влияят в ежедневието ни. Да видим как.

Да предположим, че работите в офис. Така че всяка сутрин правите поредица от задачи в последователност: първо се събуждате, след това отивате до тоалетната, закусвате, подготвяте се за офиса, излизате от дома, след това можете да вземете такси или автобус или да започнете да вървите към офис и след определено време стигате до офиса си. Можете да кажете, че всички тези стъпки образуват алгоритъм .

С прости думи, алгоритъмът е набор от задачи. Надявам се, че не сте забравили тези стъпки, които направихме, за да преместим три дискови стека от А в С. Можете също така да кажете, че тези стъпки са алгоритъмът за решаване на проблема Кулата на Ханой.

В математиката и компютърните науки алгоритъмът е недвусмислена спецификация за това как да се реши клас задачи. Алгоритмите могат да извършват задачи за изчисляване, обработка на данни и автоматизирани разсъждения. - Уикипедия

Ако погледнете тези стъпки, можете да видите, че сме изпълнявали една и съща задача няколко пъти - преместване на дискове от един стек в друг. Можем да наречем тези стъпки вътре в стъпки рекурсия .

Рекурсия

Рекурсияизвиква същото действие от това действие. Точно като горната снимка.

Така че има едно правило за извършване на рекурсивна работа: трябва да има условие за спиране на изпълнението на това действие. Надявам се, че разбирате основите на рекурсията.

Сега, нека се опитаме да изградим процедура, която ни помага да разрешим проблема с Кулата на Ханой. Опитваме се да изградим решението с помощта на псевдокод . Псевдокодът е метод за изписване на компютърен код с използване на английски език.

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

Това е скелетът на нашето решение. Като аргумент приемаме общия брой дискове. След това трябва да предадем източника, междинното място и дестинацията, за да можем да разберем картата, която ще използваме, за да завършим работата.

Сега трябва да намерим терминално състояние . Състоянието на терминала е състоянието, в което вече няма да извикваме тази функция.

IF disk is equal 1

В нашия случай това би било нашето крайно състояние. Защото, когато в нашия стек ще има един диск, лесно е да направим тази последна стъпка и след това нашата задача ще бъде изпълнена. Не се притеснявайте, ако не ви е ясно. Когато стигнем до края, тази концепция ще бъде по-ясна.

Добре, намерихме нашата терминална точка, където преместваме диска си до местоназначението по следния начин:

move disk from source to destination

Сега отново извикваме нашата функция, като предаваме тези аргументи. В този случай разделяме стека дискове на две части. Най-големият диск ( n-ти диск) е в едната част, а всички останали ( 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

Седем стъпки отнеха три диска, за да достигнат дестинацията. Ние наричаме това рекурсивен метод .

Сложност на времето и изчисления на сложността на пространството

Сложност във времето

Когато стартираме код или приложение в нашата машина, отнема време - цикли на процесора. Но това не е еднакво за всеки компютър. Например времето за обработка на ядро ​​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. 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