Żółw i zając znajdują pętlę bez zapamiętywania odwiedzonych miejsc
Jeśli kolejne stany tworzą sekwencję, która w pewnym momencie wpada w cykl, pętlę można wykryć bez przechowywania całej historii. Metoda „żółwia i zająca”, powszechnie kojarzona z algorytmem Floyda, prowadzi dwa wskaźniki po tej samej sekwencji: wolny wykonuje jeden krok, szybki dwa. Gdy oba znajdą się już w cyklu, szybszy wskaźnik zbliża się do wolniejszego o jedną pozycję na krok w arytmetyce modulo długość cyklu, więc w końcu muszą się spotkać. Zamiast zbioru wszystkich odwiedzonych stanów potrzebne są tylko dwa bieżące stany i stała ilość dodatkowej pamięci.
Pętla może być ukryta w zwykłej sekwencji
Wyobraź sobie funkcję, która każdemu stanowi przypisuje dokładnie jeden następny stan. Zaczynamy od x0, potem obliczamy x1=f(x0), x2=f(x1) i tak dalej. Jeśli liczba możliwych stanów jest skończona, w końcu któryś stan może się powtórzyć. Od tej chwili dalsza sekwencja również zaczyna się powtarzać: powstaje „ogon” prowadzący do cyklu i sama pętla.
Najprostszy sposób wykrycia powtórki to zapisywać wszystkie odwiedzone stany w zbiorze. Gdy trafimy na wartość już widzianą, wiemy, że istnieje cykl. Metoda działa, ale pamięć rośnie wraz z liczbą kroków. Tortoise-and-hare robi coś znacznie dziwniejszego: nie pamięta historii. Utrzymuje tylko dwa punkty poruszające się po tej samej deterministycznej sekwencji.
Dlaczego szybszy wskaźnik musi dogonić wolniejszy
„Żółw” wykonuje jeden krok funkcji na iterację, a „zając” dwa. Zanim oba wejdą do cyklu, ich pozycje mogą wyglądać dowolnie. Kiedy jednak już znajdują się na pętli długości L, interesuje nas tylko ich względne przesunięcie modulo L. Zając zyskuje jeden krok względem żółwia w każdej iteracji, więc różnica pozycji zmienia się o jeden modulo L. Po najwyżej L takich zmianach różnica musi stać się zerem — wskaźniki spotkają się.
Materiały MIT wykorzystujące tę technikę przy omawianiu faktoryzacji Pollarda pokazują dokładnie tę intuicję: gdy wolniejszy wskaźnik wejdzie w cykl, szybszy będzie nadrabiał względem niego jedną pozycję, aż oba trafią na ten sam stan. Nie potrzeba tablicy „odwiedzono”. Potrzebna jest możliwość wielokrotnego obliczania następnego stanu i porównania dwóch stanów.
Spotkanie mówi „cykl istnieje”, ale można dowiedzieć się więcej
Samo pierwsze spotkanie wykrywa pętlę. Standardowa odmiana algorytmu pozwala następnie znaleźć również miejsce, w którym sekwencja po raz pierwszy wchodzi do cyklu. Jeden wskaźnik ustawia się ponownie na początku sekwencji, drugi pozostawia w punkcie spotkania, a następnie oba przesuwa po jednym kroku. Odpowiednia zależność długości ogona i liczby obiegów sprawia, że spotkają się przy wejściu do cyklu. Można też osobno zmierzyć długość pętli.
To rozszerzenie jest użyteczne m.in. przy analizie struktur połączonych oraz iterowanych funkcji. Najważniejsza oszczędność pozostaje ta sama: liczba przechowywanych wskaźników nie rośnie z długością przebytej drogi.
Stała pamięć w zamian za specyficzną strukturę problemu
Nie jest to uniwersalny algorytm wykrywania dowolnych cykli w dowolnym grafie. Działa w modelu, w którym z każdego stanu wynika jeden następny stan — tak jak przy przechodzeniu wskaźnikiem `next` po liście lub przy iterowaniu funkcji. Gdy węzeł ma wiele możliwych następców, potrzebne są inne techniki grafowe.
Właśnie to ograniczenie czyni przykład wartościowym. Algorytm uzyskuje niezwykłą oszczędność pamięci nie przez cudowną sztuczkę, lecz przez wykorzystanie silnej własności danych. Jeśli problem można sprowadzić do „funkcjonalnego grafu”, dwie prędkości wystarczają, by informacja o cyklu ujawniła się przez samo spotkanie wskaźników.
Sztuczka działa dlatego, że każdy stan ma jednego następcę
Metody żółwia i zająca nie należy mylić z ogólnym algorytmem wykrywania cykli w dowolnym grafie. Jej siła bierze się z bardzo szczególnej struktury: z każdego stanu przechodzimy deterministycznie do dokładnie jednego następnego stanu. Sekwencja ma więc postać ścieżki, która albo trwa dalej, albo wpada w pętlę. Dwa wskaźniki mogą poruszać się po tej samej jednej trajektorii bez zapamiętywania całej historii. W zwykłym grafie z wieloma możliwymi krawędziami taki argument nie wystarcza i stosuje się inne techniki, np. znaczniki odwiedzonych wierzchołków. Ograniczenie jest częścią elegancji algorytmu: stała pamięć jest możliwa dzięki wykorzystaniu dodatkowej struktury problemu.
Ten sam mechanizm przydaje się w algorytmach faktoryzacji
Materiały MIT o faktoryzacji pokazują żółwia i zająca w kontekście metody Pollarda rho. Tam kolejne wartości powstają przez wielokrotne stosowanie tej samej funkcji modulo liczba, więc z powodu skończonej liczby możliwych reszt sekwencja musi w końcu wejść w cykl. Nie chodzi o to, że sama detekcja cyklu rozkłada liczbę na czynniki. Pozwala jednak porównywać odpowiednio odległe punkty trajektorii bez przechowywania całej historii i wykorzystywać ich różnice do szukania nietrywialnego wspólnego dzielnika. To ciekawy przykład, jak bardzo ogólna technika strukturalna wędruje między problemami: ten sam układ dwóch wskaźników może wykrywać pętle w listach, analizować iteracje funkcji i stanowić element algorytmu teorii liczb. Wspólna jest nie dziedzina, lecz geometryczna struktura sekwencji.