Wieża Hanoi: Zasada rekurencyjna z dowodowo optymalnym rozwiązaniem

Zasady i rekurencyjna perspektywa

Trzy wahadła, N dysków o różnej wielkości stosowanych na najmniejszym wierzchołku na pierwsze wahadło. Przenieś każdy disk do trzeciego wahadla, jeden po drugim, nie umieszczając większego diska na mniejszym. Édouard Lucas stworzył zagadnienie w 1883 roku, opakowane w legende o monach w Wietnamie przenoszących 64 złote dyski. To, co sprawia, że jest ulubionym przykładem nauczycielskim, to fakt, że optymalne rozwiązanie wynika bezpośrednio z rekurencyjnego podejścia do rozwiązywania problemu, a nie z jakiegokolwiek inteligentnego wyszukiwania.

Aby przenieść N dysków z wahadła A na wahadło C używając wahadła B jako dodatkowego, zauważ, że najniższy disk nie może się poruszyć, dopóki każdy disk powyżej nie zostanie usunięty. Jedynym miejscem, gdzie mogą znaleźć się N-1 mniejsze dyski, pozostawiając najniższy disk wolny, jest całe wahadło dodatkowe. Ta obserwacja stanowi cały algorytm:

function hanoi(n, from, to, via) {
  if (n === 0) return;
  hanoi(n - 1, from, via, to);   // move top n-1 disks out of the way
  moveDisk(from, to);            // move the (now exposed) largest disk
  hanoi(n - 1, via, to, from);   // move the n-1 disks onto the largest
}
hanoi(N, 'A', 'C', 'B');

Dlaczego liczba ruchów wynosi dokładnie 2^N - 1

Oznaczmy M(n) jako minimalną liczbę ruchów potrzebnych do przeniesienia n dysków. Powyższa rekurencja przesuwa n-1 dyski dwukrotnie (raz w bok, raz na końcową patkę) oraz wykonuje jedną pojedynczą operację dla największego dysku, co daje M(n) = 2·M(n-1) + 1, przy czym M(0)=0. Rozwijając to: M(n) = 2·(2·M(n-2)+1)+1 = 4·M(n-2)+3 = ... = 2ⁿ·M(0) + (2ⁿ-1) = 2ⁿ-1. Można również udowodnić, że ta liczba jest optymalna, a nie tylko osiągalna, używając prostego argumentu wymiany: największy disk musi przesunąć się co najmniej raz, a przed tym każdym inny dysk musi już być poza nim i poza końcową patką, co wraz z indukcją wymaga co najmniej M(n-1) ruchów - dlatego M(n) ≥ 2·M(n-1)+1 jako dolna granica, pasująca dokładnie do rekurencyjnej konstrukcji.

Dla N=64 złotych dysków, jak w legencie Lucasa, to daje 2⁶⁴-1 ≈ 1,8×10¹⁹ ruchów. W przypadku jednego ruchu na sekundę zakończenie byłoby trwało dłużej niż obecnie estymowana wiek wszechświata - zagadka jest standardową metodą, aby fizycznie podkreślić wzrost wykładniczy, ponieważ dodanie tylko jednego dysku więcej zawsze dokładnie podwójuje pozostałą pracę plus jeden ruch.

Sekwencja ruchów ma piękną wzorcową strukturę binarną

Znajdź numer k dla ruchu k, licząc od 1 do 2ⁿ-1. Okazuje się, że dysk, który porusza się w ruchie k, jest wyznaczony jedynie przez reprezentację binarną k: dysk, który porusza się w ruchie k, to pozycja najniższej ustawionej bitu w reprezentacji binarnej k (licząc od 1), czyli jeden więcej niż liczba zer na końcu reprezentacji binarnej k. Ruch 1 (binarnie 1) porusza dysk 1; ruch 2 (binarnie 10) porusza dysk 2; ruch 4 (binarnie 100) porusza dysk 3; ruch 6 (binarnie 110) ponownie porusza dysk 2. To daje całkowicie nie-rekurencyjowy sposób na generowanie tego samego optymalnego rozwiązania - iteruj k od 1 do 2ⁿ-1, wyodrębnij najniższy ustawiony bit i porusz ten dysk w jedynym legalnym kierunku dostępny dla niego (każdy dysk porusza się cyklicznie między trzema szpilami, a dla N parzystych vs nieparzystych najmniejszy dysk cykluje A→C→B→A lub A→B→C→A odpowiednio) - i to jest piękna ilustracja tego, jak definicja rekurencyjna i kombinatoryczne manewry bitowe mogą obliczać dokładnie tą samą strukturę.

Zagadnienie czterech wężyków i hipoteza Frame-Sterta

Dodanie czwartego węża powinno zrobić zagadnienie bardziej proste, a tak jest - jednak liczba idealnych ruchów dla wersji z czterema wężami, znana jako liczby Frame-Sterta, została dowiedziana tylko w 2014 roku (przez Bouscha), co o wiele dekad przesunęło się w stosunku do oryginalnej propozycji rekurencyjnej strategii przez Frame'a i Sterta w 1941 roku. Idea polega na tym, aby przenieść idealnie wybrany przedrostek najmniejszych dysków do dodatkowego węża używając wszystkich czterech węży, a następnie przenieść pozostałe większe dyski do docelowej stosu korzystając z klasycznego algorytmu z trzema wężami (ponieważ teraz jeden wąż jest zajęty przedrostkiem), a na koniec przenieść przedrostek z powrotem na zakończony stos używając ponownie wszystkich czterech węży. Znalezienie idealnej punktu podziału wymaga próby każdego możliwego rozmiaru przedrostka i przyjęcia najmniejszego, ale przez długi czas nikt nie mógł udowodnić, że strategia bardziej inteligentna, nie oparta na przedrostkach, nigdy nie będzie lepsza - rzadki przypadek prostego zagadnienia dla dzieci z otwartą zagadką badawczą przetrwującą ponad 70 lat.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Tower of Hanoi — Recursive Solver & 2ⁿ−1 Moves i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.