Wieże Hanoi – problem polegający na odbudowaniu, z zachowaniem kształtu, wieży z krążków o różnych średnicach (popularna układanka), 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.

Rozwiązanie łamigłówki dla czterech krążków

Pochodzenie

edytuj

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 264 −1 = 18 446 744 073 709 551 615 (blisko 18 i pół tryliona) sekund, czyli około 584,6 miliardów lat. Dla porównania: od Wielkiego Wybuchu minęło około 14 mld lat.

Algorytm

edytuj
 
Od lewej: słupek A z całą wieżą, pusty słupek B pełniący rolę bufora i pusty słupek docelowy C

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   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

edytuj

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

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

Przykładowe implementacje

def hanoi(n:int, A:list, B:list, C:list):
    """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)
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
#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;
}
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:

  1. przenieś najmniejszy krążek na kolejny (*) słupek,
  2. wykonaj jedyny możliwy do wykonania ruch, nie zmieniając położenia krążka najmniejszego,
  3. 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   krążków:

 

Dowód

edytuj

Łatwo pokazać, że  

  • w pierwszym kroku przekładamy   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   ruchów
  • przekładamy  -ty krążek na drugi słupek – wymaga to jednego ruchu
  • przekładamy pozostałe krążki ze słupka 3. na  -ty krążek leżący na 2. słupku – wymaga to co najmniej   ruchów

a więc  

Aby wykazać, że   można przeprowadzić poniższe rozumowanie.

Aby móc ruszyć  -ty krążek, trzeba najpierw zdjąć wszystkie leżące na nim krążki, tak by po ich zdjęciu jeden ze słupków pozostał wolny (aby na jego „dno” mógł trafić  -ty krążek). A więc ze słupka 1 przekładamy krążki   na słupek 3. Ponieważ aż do momentu gdy na drążku 1 pozostanie tylko  -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   krążków (którego minimalna liczba ruchów wynosi  ). Na przełożenie krążka  -tego potrzeba co najmniej jeden ruch. Po jego przełożeniu znów potrzeba przełożyć krążki   – jest to oczywiście znów sytuacja   krążków (wymagająca co najmniej   ruchów).

A więc  

co w połączeniu z górnym ograniczeniem na   daje równość

 

Postać jawna wzoru na liczbę ruchów

edytuj

Powyższe równanie rekurencyjne można w łatwy sposób przekształcić do postaci jawnej, tj. nie korzystającej z rekursji:

 
 

Niech  

Wtedy

 

jest to równanie określające ciąg geometryczny o ilorazie równym 2 takie, że

 

Po powrocie do   otrzymujemy

 

Zastosowanie

edytuj

Mimo swojego wieku łamigłówka jest stale tematem prac matematyków i znane są jej bardziej rozbudowane wersje np. z więcej niż trzema słupkami.

 
Hanoi przy dowolnym układzie krążków. Jaki jest pierwszy ruch?

Bardziej wymagająca myślenia wersja polega na znalezieniu najkrótszej drogi do ułożenia przypadkowo ułożonych krążków na wyznaczony stos. Takie zadanie przypomina sytuację mnicha, który kontynuuje układanie stosu w miejscu, w którym jego poprzednik przerwał.[1]

W psychologii łamigłówka ta jest jednym z testów na kojarzenie.

Zobacz też

edytuj

Przypisy

edytuj
  1. Wieże Hanoi. 1999-08-21. [dostęp 2020-01-08]. (pol. • ang. • niem.).

Linki zewnętrzne

edytuj