Wieże Hanoi

Wieże Hanoi – problem polegający na odbudowaniu, z zachowaniem kształtu, wieży z krążków o różnych średnicach (popularna dziecięca zabawka), przy czym podczas przekładania wolno się posługiwać buforem (reprezentowanym w tym przypadku przez dodatkowy słupek), jednak przy ogólnym założeniu, że nie wolno kłaść krążka o większej średnicy na mniejszy ani przekładać kilku krążków jednocześnie. Jest to przykład zadania, którego złożoność obliczeniowa wzrasta niezwykle szybko w miarę zwiększania parametru wejściowego, tj. liczby elementów wieży.

Spis treści

Pochodzenie

Zagadka Wież Hanoi powstała prawdopodobnie w Azji Wschodniej w XIX wieku lub wcześniej. Krążki były ceramiczne, produkowane w Chinach, Japonii i Wietnamie. Gra ta została sprowadzona na Zachód po raz pierwszy przez francuskiego matematyka Édouarda Lucasa w 1883 roku. Do sprzedawanego zestawu dołączona była tybetańska legenda, według której mnisi w świątyni Brahmy rozwiązują tę łamigłówkę dla 64 złotych krążków. Legenda mówi, że gdy mnisi zakończą zadanie, nastąpi koniec świata. Zakładając, że wykonują 1 ruch na sekundę, ułożenie wieży zajmie 2⁶⁴−1 = 18 446 744 073 709 551 615 (blisko 18 i pół tryliona) sekund, czyli około 584 miliardów lat. Dla porównania: Wszechświat ma około 13,7 mld lat.

Algorytm

Wieże Hanoi można łatwo rozwiązać za pomocą prostego algorytmu rekurencyjnego lub iteracyjnego.

Oznaczmy kolejne słupki literami A, B i C.
Niech n będzie liczbą krążków, które chcemy przenieść ze słupka A na słupek C posługując się słupkiem B jako buforem.

Rozwiązanie rekurencyjne

Algorytm rekurencyjny składa się z następujących kroków:

przenieś (rekurencyjnie) n-1 krążków ze słupka A na słupek B posługując się słupkiem C,
przenieś jeden krążek ze słupka A na słupek C,
przenieś (rekurencyjnie) n-1 krążków ze słupka B na słupek C posługując się słupkiem A

Przykładowe implementacje

w Pythonie:

def hanoi(n, A, B, C):
    """słupki A, B, C są listami"""
    if n > 0:
        hanoi(n-1, A, C, B)
        C.insert(0, A.pop(0))
        hanoi(n-1, B, A, C)

w Elixir:

defmodule Hanoi do

  # Jeśli brak krążków -> wszystko ok, nic nie trzeba robić
  def hanoi(0,_,_,_), do: :ok

  # Jeśli jeden krążek -> przełożyć na docelowy słupek
  def hanoi(1,a,_,c) do
    IO.puts "#{a}->#{c}"
  end

  # Więcej niż jeden -> rozwiąż rekurencyjnie
  def hanoi(n,a,b,c) do
    hanoi(n-1,a,c,b)
    hanoi(1,a,b,c)
    hanoi(n-1,b,a,c)
  end
  
end

w C++:

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C)
{
  // przekłada n krążków z A korzystając z B na C
  if (n > 0)
  {
    hanoi(n-1, A, C, B);
    cout << A << " -> " << C << endl;
    hanoi(n-1, B, A, C);
  }
}

int main(int argc, char *argv[])
{
  hanoi(3, 'A', 'B', 'C');
  return 0;
}

w C#:

using System;

namespace Hanoi
{
    public class WiezeHanoi
    {
        // przekłada n krążków z A, korzystając z B, na C
        static void Hanoi(int n, char A, char B, char C)
        {
            if(n > 0)
            {
                Hanoi(n - 1, A, C, B);
                Console.WriteLine("\t{0} -> {1}", A, C);
                Hanoi(n - 1, B, A, C);
            }
        }

        static void Main()
        {
            Console.WriteLine("Wieże Hanoi\n");
            Console.WriteLine("Algorytm przełożenia trzech krążków z wieży A na wieżę C z wykorzystaniem wieży B\n");
            Hanoi(3, 'A', 'B', 'C');
            Console.WriteLine("Naciśnij dowolny klawisz...");
            Console.ReadKey();
        }
    }
}

Algorytm rozwiązywania wież Hanoi jest klasycznym przykładem algorytmu rekurencyjnego używanego w nauczaniu informatyki.

Rozwiązanie iteracyjne[edytuj]

Algorytm iteracyjny składa się z następujących kroków:

przenieś najmniejszy krążek na kolejny (*) słupek.
wykonaj jedyny możliwy do wykonania ruch, nie zmieniając położenia krążka najmniejszego
powtarzaj punkty 1 i 2, aż do odpowiedniego ułożenia wszystkich krążków.

(*) Kolejny słupek wyznaczamy w zależności od liczby krążków. Jeśli liczba krążków jest parzysta, kolejnym słupkiem jest ten po prawej stronie (gdy dojdziemy do słupka C w następnym ruchu używamy słupka A). Natomiast jeśli liczba krążków jest nieparzysta, kolejnym słupkiem jest ten po lewej stronie (gdy dojdziemy do słupka A w następnym ruchu używamy słupka C)

Najmniejsza liczba wymaganych ruchów[edytuj]

Równanie określające liczbę ruchów potrzebnych do rozwiązania problemu wież Hanoi dla n krążków:

\!L(n)\ =\ L(n-1)\ +\ 1\ +\ L(n-1)

Dowód[edytuj]

Łatwo pokazać, że $\!L(n)\ \leq \ L(n-1)\ +\ 1\ +\ L(n-1)$ :

w pierwszym kroku przekładamy n-1 krążków na jeden słupek (bez straty ogólności załóżmy, że jest to krążek nr 3) - wymaga to co najmniej L(n-1) ruchów
przekładamy n-ty krążek na drugi słupek - wymaga to jednego ruchu
przekładamy pozostałe krążki ze słupka 3. na n-ty krążek leżący na 2. słupku - wymaga to co najmniej L(n-1) ruchów

a więc $\!L(n)\ \leq \ L(n-1)\ +\ 1\ +\ L(n-1)$ .

Aby wykazać, że $\!L(n)\ \geq \ L(n-1)\ +\ 1\ +\ L(n-1)$ można przeprowadzić następujące rozumowanie:

Aby móc ruszyć n-ty krążek, trzeba najpierw zdjąć wszystkie leżące na nim krążki, tak by po ich zdjęciu jeden z słupków pozostał wolny (aby na jego "dno" mógł trafić n-ty krążek). A więc ze słupka 1 przekładamy krążki $1,2,\cdots n-1$ na słupek 3. Ponieważ aż do momentu gdy na drążku 1 pozostanie tylko n-ty krążek nie ma znaczenia czy rzeczywiście się on tam znajduje, a więc do tego momentu sytuacja upraszcza się do rozwiązania problemu wież Hanoi dla n-1 krążków (którego minimalna liczba ruchów wynosi L(n-1)). Na przełożenie krążka n-tego potrzeba co najmniej jeden ruch. Po jego przełożeniu znów potrzeba przełożyć krążki $1,2,\cdots n-1$ - jest to oczywiście znów sytuacja n-1 krążków (wymagająca co najmniej L(n-1) ruchów).