Floyd ' s Algorytm wykrywania cyklu | Określenie punktu początkowego cyklu

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

Odległość pokonana przez slowPointer przed spotkaniem $ = x + y $

Odległość pokonana przez fastPointer przed spotkaniem $ = (x + y + z) + y = x + 2y + z $

Ponieważ fastPointer podróżuje z podwójna prędkość slowPointer, a czas jest stały dla obu, gdy dotrą na miejsce spotkania. Czyli używając prostej zależności prędkości, czasu i odległości (slowPointer przebył połowę odległości):

\ 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 *}

Dlatego przenosząc slowPointer na początek połączonej listy i ustawiając zarówno slowPointer i fastPointer, aby przesuwać jeden węzeł naraz, mają do pokonania tę samą odległość .

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

Komentarze

• Tutaj założyłeś, że spotkają się po jednej rotacji. Mogą być przypadki (gdzie cykl jest mały), w których mogą się spotkać po pewnym nie. obrotów.
• @JotWaraich obraz nie jest reprezentatywny dla wszystkich przypadków; logika jest jednak nadal aktualna
• to jest najprostsza odpowiedź na temat tego algorytmu w całym Internecie
• I ' nie jestem pewien czy ten dowód jest poprawny. Odległość pokonana przez małą wskazówkę powinna wynosić (x + (y + z) * α + y), a odległość przebyta przez szybki wskaźnik powinna wynosić (x + (y + z) * β + y), gdzie α i β to liczba cykli pokonanych przez powolną i szybką wskazówkę. Wydaje się, że ten dodatek zawodzi.
• @ hashcode55 tak, zgadzam się z tobą, to nie jest dla mnie jasne

Zaakceptowaną odpowiedź również widziałem w innym miejscu. Jednak chociaż jest to łatwe do zrozumienia, jest nieprawidłowe. Dowodzi to

$ x = z $ (co jest oczywiście błędne, a diagram po prostu sprawia, że wydaje się wiarygodny ze względu na sposób, w jaki jest naszkicowany).

Czego naprawdę chcesz udowodnić (używając tych samych zmiennych, które opisano na schemacie w akceptowanej odpowiedzi powyżej):

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

$ (y + z) $ to długość pętli, $ L $

więc chcemy udowodnić:

$ z = x \ mod \ L $

Albo że z jest przystające do x (modulo L)

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

Miejsce spotkania, $ M = x + y $

$ 2 (x + y) = M + kL $, gdzie $ k $ jest jakąś stałą.Zasadniczo odległość przebyta przez szybki wskaźnik to $ x + y $ plus pewna wielokrotność długości pętli, $ L $

$ x + y = kL $

$ x = kL – y $

Powyższe równanie dowodzi, że $ x $ to to samo, co pewna wielokrotność długości pętli, $ L $ minus $ y $. Tak więc, jeśli szybki wskaźnik zaczyna się w miejscu spotkania, $ M $ lub $ x + y $, to kończy się na początku pętli.

Komentarze

• Nie ' nie wiem, dlaczego ta odpowiedź jest niedoceniana. Wydaje się, że jest to najbardziej formalny dowód.
• @ I8Ponownie, jeśli x = z jest błędne, to logika w przesuwaniu szybkiego wskaźnika z powrotem do punktu początkowego & przesuń oba szybki & wolny wskaźnik do znalezienia początku pętli nie ' nie zadziała. nie rozumiem, co masz na myśli, mówiąc, że x = z jest błędne, wyjaśnij, dlaczego?
• @divine x = z jest błędne, ponieważ oznacza, że oba są równe, ale dopuszczalne jest posiadanie bardzo długiego „ ogon ”(duże x) i bardzo małe kółko (małe z). Używając modulo, jesteśmy formalnie poprawni, chcemy tylko udowodnić, że x% L == z, innymi słowy, wskaźnik, który porusza się po okręgu czekając na połączenie z drugim, może wykonać tyle pętli, ile chce, o ile ostatnie kroki (tj. reszta po zapętleniu) doprowadzą do samego początku kręgu.
• to świetnie !!
• Dla tych z Was, którzy jeszcze tego nie zrobili ' nie rozumiem, dlaczego x = k * L – y prowadzi do z = x mod L. Od x = k * L – y — > x = (k – 1) * L + L – y i teraz możesz powiedzieć, że L – y musi być z. Teraz otrzymujesz x = (k – 1) * L + z

Powiedz, że są $ l $ elementów przed rozpoczęciem pętli i $ n $ elementów w pętli. A $ e_l $ jest pierwszym elementem pętli, który jest widoczny, gdy przechodzimy przez połączoną listę. Kiedy powiemy ” element $ x $ kilka kroków przed $ e $ „, co oznacza, że możemy dotrzeć do tego elementu wykonując $ x $ kroków od $ e $ .

Teraz, gdy Tr (żółw) osiągnie $ e_l $ , po $ l $ iteracji, powiedzmy, Hr (Hare) to $ x $ kroków przed $ e_l $ . Ponieważ Hr wykonał do tego czasu łącznie 2l $ kroków ( $ l $ kroków przed pętlą), więc:

$ x = l \ bmod n $ .

W każdej przyszłej iteracji Tr i Hr będą się rozwijać o 1 i 2 kroki, więc każda iteracja zwiększy ich ” odstęp ” o 1. Tak więc spotkają się po $ nx $ dalszych iteracji, gdy ich przerwa zmieni się na $ x + (nx) = n $ . Tak więc element spotkania $ M $ będzie o $ nx $ kroki przed $ e_l $ . To oznacza, że przejście $ x $ kroków po $ M $ ponownie przeniesie nas do $ e_l $ . Naszym celem jest zlokalizowanie $ e_l $ .

Kiedy więc zaczniemy od jednego odwołania Tr w $ M $ i kolejną godzinę odniesienia na początku listy połączonej, a następnie postępuj w obu krokach po 1 kroku po $ l $ iteracjach :

• Hr będzie $ l $ kroków przed główką, czyli $ e_l $ .

• Tr będzie $ (l \ bmod n) $ kroków przed $ M $ , czyli $ x $ krok przed $ M $ , czyli $ e_l $ .

Zatem gdy mają met, wiemy, że to $ e_l $ .

Zobacz ten artykuł dla szczegółów. Znajdziesz tam nieco zmodyfikowaną metodę lokalizacji $ e_l $ .

Odpowiedź znalazłem w stackoverflow. Dzięki, jeśli ktoś się tym zajął. A dla tych, którzy podobnie jak ja chcieli wyjaśnienia, zapoznaj się z: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Wybrana odpowiedź na pytanie wyjaśnia to!

Myślę też, że pierwsza odpowiedź jest niekompletna i chociaż niektóre inne wyjaśnienia są również dobre, mam inne wersja bez MOD, aby pokazać to samo, co może być łatwiejsze dla niektórych osób.

Ta sama konfiguracja, rozważ $ X \ ge 0 $ jako odległość przed pętlą, $ N \ le \ text {size of list} $ to rozmiar pętli (ilość $ y + z $ na zdjęciu), a miejsce spotkania to $ Y $ w pętli. W tym miejscu zwróć uwagę, że utworzyliśmy również $ X + Y \ le N $ .

Teraz powolny wskaźnik porusza się $ X + Y + pN $ , gdzie $ p $ jest dowolną liczbą całkowitą. Następnie szybki wskaźnik przeleciał 2 USD (X + Y + pN) $ .

Teraz zgłosić , że spotkają się w $ Y $ .

Dowód :

Jeśli spotkają się w $ Y $ , musi to być że szybszy wskaźnik pokonał dokładnie $ qN $ więcej niż wolniejszy wskaźnik, gdzie $ q $ jest liczbą całkowitą . Następnie mamy: $$ \ text {różnica odległości =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Ale mieliśmy $ Y $ jako dowolne miejsce spotkania w pętli, więc możemy po prostu wybrać $ X + Y = N $ , który zawiera jako $ X + Y \ le N $ .

Mamy więc: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ , co jest prawdą, jeśli $ p + 1 = q $ . Ponieważ zarówno $ p $ , jak i $ q $ są dowolnymi liczbami całkowitymi, możemy po prostu wybrać minimum, więc że $ p = 0, q = 1 $ , co odpowiada: $$ \ text {odległość przebyta przez powolny wskaźnik} = X + Y + pN = X + Y $$ i $$ \ text {odległość przebyta przez szybki wskaźnik} = (X + Y + pN) + qN = X + Y + N $$ , więc szybki wskaźnik, po raz pierwszy napotkany na powolny wskaźnik, przebył dokładnie $ N $ więcej.

Żółw i zając to dwa wskaźniki, które są inicjalizowane wartością „góry” listy. W każdym cyklu pętli zając zwiększa się o 2 elementy, podczas gdy żółw zwiększa się o jeden. Jeśli w którymkolwiek momencie zając jest równy zającowi, wykryto pętlę. Jeśli zając równa się końcowi, pętla nie została znaleziona.

Ten post wyjaśnia to lepiej wiersz po wierszu:

https://www.thiscodeworks.com/floyd-s-cycle-detection-algorithm-aka-the-tortoise-and-the-hare-algorithms-logic-interesting/5e10a9b796432f6f7b798b29