Wieże Hanoi

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

od lewej: wieża A, bufor, wieża B

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

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 można 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

1 Pochodzenie
2 Algorytm
- 2.1 Rozwiązanie rekurencyjne
- 2.2 Rozwiązanie iteracyjne
3 Równanie na ilość ruchów
- 3.1 Dowód
4 Postać jawna wzoru na ilość ruchów
5 Zastosowanie

[edytuj] Pochodzenie

Zagadka Wież Hanoi stała się znana w XIX wieku dzięki matematykowi Édouard Lucasowi, który proponował zagadkę dla 8 krążków. Do sprzedawanego zestawu była dołączona (prawdopodobnie wymyślona przez Lucas'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 sekund, czyli około 584542 milionów lat. Dla porównania: Wszechświat ma około 13700 mln lat.

[edytuj] Algorytm

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

nazywamy słupki: A, B, C
niech n będzie liczbą krążków, które chcemy przenieść ze słupka A na słupek B posługując się słupkiem C jako buforem

[edytuj] Rozwiązanie rekurencyjne

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

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

przykładowa implementacja w Pythonie:

def hanoi(n,A,B,C):
    """słupki A,B,C są listami"""
    if n > 0:
        hanoi(n-1,A,C,B)     # rekurencyjnie przekładamy n-1 krążków z A na C
        B.insert(0,A.pop(0)) # przekładamy jeden krążek z A na B
        hanoi(n-1,C,B,A)     # rekurencyjnie przekładamy n-1 krążków z A na B

W nauczaniu informatyki algorytm rozwiązywania wież Hanoi jest często pierwszym przykładem algorytmu rekurencyjnego.

[edytuj] Rozwiązanie iteracyjne

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

przenies najmniejszy krążek na kolejny słupek (poruszając się w prawo, gdy dojdziemy do słupka C w następnym ruchu używamy słupka A)
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.

[edytuj] Równanie na ilość ruchów

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

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

[edytuj] Dowód

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

w pierwszym kroku przekładamy n-1 krążków na jeden słupek (BSO 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 krażki ze słupka 3go na n-ty krążek leżący na 2gim słupku - wymaga to co najmniej L(n-1) ruchów

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

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

Aby móc ruszyć n-ty krążek, tzeba 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 1go przekładamy krążki $1,2,\cdots n-1$ na słupek 3ci. Ponieważ aż do momentu gdy na krąż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 ilość 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).