Algorytm wykrywania cyklu Floyda Określenie punktu początkowego cyklu

32

Szukam pomocy w zrozumieniu algorytmu wykrywania cyklu Floyda. Przeszedłem wyjaśnienie na Wikipedii ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Widzę, jak algorytm wykrywa cykl w czasie O (n). Nie jestem jednak w stanie wyobrazić sobie, że kiedy wskaźniki żółwia i zająca spotkają się po raz pierwszy, początek cyklu można ustalić, przesuwając wskaźnik żółwia z powrotem, aby rozpocząć, a następnie przesuwając zarówno żółwia, jak i zająca, o krok. Punktem, w którym spotykają się po raz pierwszy, jest początek cyklu.

Czy ktoś może pomóc, podając wyjaśnienie, które, mam nadzieję, różni się od tego na Wikipedii, ponieważ nie jestem w stanie go zrozumieć / wizualizować?

algorithms linked-lists

— Anurag Kapur
źródło

3

Znalazłem odpowiedź na stackoverflow. Dzięki, jeśli ktoś szukał tego dla mnie. A dla tych, którzy tak jak ja chcieli wyjaśnienia, zapoznaj się z: stackoverflow.com/questions/3952805 /... Wybiera wybraną odpowiedź na pytanie!

— Anurag Kapur

Cześć @Anurag. Tylko dla twojej informacji, Zrobiłem blogu na „Żółw i Zając” algorytm tutaj

— Kyle

Czy wiesz, dlaczego fastzmienna lub „zając” musi poruszać się z dwukrotnie większą prędkością niż żółw, a nie tylko jeden z przodu?

— devdropper87

Ładnie wyjaśnione w programie: javabypatel.blogspot.in/2015/12/detect-loop-in-linked-list.html

— Jayesh

47

Możesz odwołać się do „Wykrywanie początku pętli na pojedynczo połączonej liście” , oto fragment:

Przebyty dystans slowPointerprzed spotkaniem $= x+y$

fastPointer $=(x + y + z) + y$

Ponieważ fastPointerpodróżuje z podwójną prędkością slowPointer, a czas jest stały dla obu, gdy dotrą do miejsca spotkania. Używając prostej relacji prędkości, czasu i odległości ( slowPointerprzebytej połowy odległości):

\begin{aligned} 2) * dyst (slowPointer) & = dyst (fastPointer) \\ 2) (x + y) & = x + 2) y + z \\ 2) x + 2) y & = x + 2) y + z \\ x & = z \end{aligned}

$\begin{align*} 2*\operatorname{dist}(\text{slowPointer}) &= \operatorname{dist}(\text{fastPointer})\\ 2(x+y) &= x+2y+z\\ 2x+2y &= x+2y+z\\ x &= z \end{align*}$

W związku z tym, przechodząc slowPointerna początek listy połączonej i wykonując oba slowPointeroraz fastPointerprzesuwając jeden węzeł na raz, oba mają taką samą odległość do pokonania .

Dotrą do punktu, w którym pętla zaczyna się na połączonej liście.

— Stary mnich
źródło

2

Tutaj założyłeś, że spotkają się po jednym obrocie. Mogą wystąpić przypadki (w których cykl jest mały), w których mogą się spotkać po pewnym nie. rotacji.

— Navjot Waraich,

1

@JotWaraich obraz nie jest reprezentatywny dla wszystkich przypadków; logika jednak nadal obowiązuje

— denis631,

3

to najprostsza odpowiedź na temat tego algorytmu w całym Internecie

— Marshall X

7

Widziałem zaakceptowaną odpowiedź jako dowód również w innym miejscu. Jednak chociaż jest łatwy do odczytania, jest niepoprawny. Dowodzi tego

$x = z$

To, co naprawdę chcesz udowodnić, to (używając tych samych zmiennych, jak opisano na schemacie w zaakceptowanej odpowiedzi powyżej):

$z = x\ mod\ (y + z)$

$(y + z)$ $L$

więc chcemy udowodnić:

$z = x\ mod\ L$

Lub że z jest zgodne z x (modulo L)

Poniższy dowód ma dla mnie większy sens:

$M = x + y$

$2(x + y) = M + kL$ $k$ $x + y$ $L$

$x + y = kL$

$x = kL - y$

$x$ $L$ $y$ $M$ $x + y$

— l8 Znowu
źródło

0

Znalazłem odpowiedź na stackoverflow. Dzięki, jeśli ktoś szukał tego dla mnie. A dla tych, którzy tak jak ja chcieli wyjaśnienia, proszę zapoznać się z: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Wybrana odpowiedź na pytanie, wyjaśnia to!

— Anurag Kapur
źródło