Wieże Hanoi
Z Wikipedii
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 |
[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 Lucasa) 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 542 milionów lat. Dla porównania: Wszechświat ma około 13 700 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 C 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:
- 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 ilości krążków. Jeśli ilość 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 ilość 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)
[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:
[edytuj] Dowód
Łatwo pokazać, że :
- 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 3. na n-ty krążek leżący na 2. słupku - wymaga to co najmniej L(n-1) ruchów
a więc .
Aby wykazać, że 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 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 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 - jest to oczywiście znów sytuacja n-1 krążków (wymagająca co najmniej L(n-1) ruchów).
A więc
co w połączeniu z górnym ograniczeniem na L(n) daje równość
[edytuj] Postać jawna wzoru na liczbę ruchów
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 L(n) otrzymujemy
[edytuj] Zastosowanie
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.
W psychologii łamigłówka ta jest jednym z testów na kojarzenie.
[edytuj] Zobacz też