ハノイの塔の問題を解決する方法-図解アルゴリズムガイド

始める前に、ハノイの塔の問題とは何かについて話しましょう。さて、これは楽しいパズルゲームで、目的はディスクのスタック全体をソース位置から別の位置に移動することです。3つの簡単なルールに従います。

  1. 一度に移動できるディスクは1つだけです。
  2. 各移動は、スタックの1つから上位ディスクを取り出し、それを別のスタックの上に配置することで構成されます。つまり、ディスクは、スタックの最上位のディスクである場合にのみ移動できます。
  3. 小さいディスクの上に大きいディスクを配置することはできません。

それでは、シナリオを想像してみましょう。3つのディスクのスタックがあるとします。私たちの仕事は、このスタックをソースAから宛先Cに移動することです。これをどのように行うのですか?

そこにたどり着く前に、中間点Bがあると想像してみましょう。

この仕事を終えるためのヘルパーとしてBを使うことができます。これで、次に進む準備ができました。各手順を実行してみましょう。

  1. 最初のディスクをAからCに移動します
  2. 最初のディスクをAからBに移動します
  3. 最初のディスクをCからBに移動します
  4. 最初のディスクをAからCに移動します
  5. 最初のディスクをBからAに移動します
  6. 最初のディスクをBからCに移動します
  7. 最初のディスクをAからCに移動します

ブーム!私たちは問題を解決しました。

あなたはより良い理解のために上のアニメーション画像を見ることができます。

それでは、問題を解決するためのアルゴリズムを構築してみましょう。待ってください、ここに新しい単語があります:「アルゴリズム」。それは何ですか?何か案が?問題ありません、見てみましょう。

アルゴリズムとは何ですか?

アルゴリズムは、ソフトウェア開発者にとって最も重要な概念の1つです。実際、それはソフトウェア開発やプログラミングだけでなく、すべての人にとって重要だと思います。アルゴリズムは私たちの日常生活に影響を与えます。方法を見てみましょう。

あなたがオフィスで働いているとしましょう。したがって、毎朝、一連のタスクを順番に実行します。最初に目を覚まし、次に洗面所に行き、朝食を食べ、オフィスの準備をし、家を出て、タクシーやバスに乗るか、オフィスと、一定時間後、あなたはあなたのオフィスに到着します。これらすべてのステップがアルゴリズムを形成していると言えます

簡単に言うと、アルゴリズムは一連のタスクです。3つのディスクスタックをAからCに移動するために行った手順を忘れていないことを願っています。これらの手順は、ハノイの塔の問題を解決するためのアルゴリズムであるとも言えます。

数学とコンピュータサイエンスでは、アルゴリズムはあるクラスの問題を解決する方法の明確な仕様です。アルゴリズムは、計算、データ処理、および自動推論タスクを実行できます。—ウィキペディア

これらの手順を見ると、同じタスクを複数回実行していたことがわかります。つまり、あるスタックから別のスタックにディスクを移動しています。これらのステップは、ステップ再帰内で呼び出すことができます。

再帰

再帰そのアクションから同じアクションを呼び出しています。上の写真のように。

したがって、再帰的な作業を行うための1つのルールがあります。それは、そのアクションの実行を停止する条件が必要です。再帰の基本を理解していただければ幸いです。

それでは、ハノイの塔の問題を解決するのに役立つ手順を作成してみましょう。擬似コードを使用してソリューションを構築しようとしています。擬似コードは、英語を使用してコンピューターコードを書き出す方法です。

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

これが私たちのソリューションの骨組みです。ディスクの総数を引数として取ります。次に、ジョブを完了するために使用するマップを理解できるように、ソース、中間の場所、および宛先を渡す必要があります。

次に、端末の状態を見つける必要があります。最終状態は、この関数をもう呼び出さない状態です。

IF disk is equal 1

私たちの場合、これは私たちの最終状態になります。スタックにディスクが1つある場合は、その最後のステップを実行するのは簡単で、その後にタスクが実行されるためです。はっきりしなくても心配しないでください。終わりに達すると、この概念はより明確になります。

了解しました。次のように、ディスクを宛先に移動するターミナル状態ポイントが見つかりました。

move disk from source to destination

次に、これらの引数を渡して関数を再度呼び出します。その場合、ディスクのスタックを2つの部分に分割します。最大のディスク(n番目のディスク)は1つの部分にあり、他のすべての(n-1)ディスクは2番目の部分にあります。そこで、-(n-1)に対してメソッドを2回呼び出します。

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

これは、3つのディスクのツリーです。

これは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

3つのディスクが宛先に到達するまでに7つのステップが必要でした。これを再帰メソッドと呼びます。

時間計算量と空間計算量の計算

時間の複雑さ

マシンでコードまたはアプリケーションを実行すると、時間がかかります—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. 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