Floyd ' s Algoritmus detekce cyklu | Určení počátečního bodu cyklu

Můžete se podívat na „Zjištění začátku smyčky v jednotlivě propojeném seznamu“ , zde je výňatek:

Vzdálenost ujetá slowPointer před setkáním $ = x + y $

vzdálenost ujetá fastPointer před setkáním $ = (x + y + z) + y = x + 2y + z $

Protože fastPointer cestuje s zdvojnásobte rychlost slowPointer a času konstantní pro oba, když se dostanete na místo setkání. Takže pomocí jednoduchého vztahu rychlosti, času a vzdálenosti (slowPointer urazil poloviční vzdálenost):

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

Proto přesunutím slowPointer na začátek propojeného seznamu a vytvořením obou slowPointer a fastPointer k přesunutí jednoho uzlu po druhém, oba mají stejnou vzdálenost .

Dostanou se do bodu, kde smyčka začíná v propojeném seznamu.

Komentáře

• Zde jste předpokládali, že se setkají po jedné rotaci. Mohou nastat případy (kdy je cyklus malý), kdy se mohou setkat po určitém ne. rotací.
• @JotWaraich obrázek není reprezentativní ve všech případech; logika však stále platí
• toto je nejpřímější odpověď na tento algoritmus v celém internetu
• I ‚ nejsem si moc jistý pokud je tento důkaz správný. Vzdálenost uražená pomalým ukazatelem by měla být (x + (y + z) * α + y) a vzdálenost uražená rychlým ukazatelem by měla být (x + (y + z) * β + y), kde α a β jsou čísla cyklů projetých pomalým a rychlým ukazatelem. Zdá se, že tento doplněk selhal,
• @ hashcode55 ano, souhlasím s vámi, toto mi není jasné

Přijatou odpověď jsem viděl jako důkaz i jinde. Přestože je snadné jej uchopit, je nesprávný. To, co dokazuje, je

$ x = z $ (což je zjevně špatné a díky diagramu to vypadá, že je to věrohodné vzhledem k tomu, jak je načrtnuto).

Co opravdu chcete prokázat je (pomocí stejných proměnných, jaké jsou popsány v diagramu v přijaté odpovědi výše):

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

$ (y + z) $ je délka smyčky, $ L $

takže chceme dokázat:

$ z = x \ mod \ L $

Nebo že z je shodné s x (modulo L)

Následující důkaz mi dává větší smysl:

Místo setkání, $ M = x + y $

$ 2 (x + y) = M + kL $, kde $ k $ je nějaká konstanta.V zásadě je vzdálenost uražená rychlým ukazatelem $ x + y $ plus nějaký násobek délky smyčky, $ L $

$ x + y = kL $

$ x = kL – y $

Výše uvedená rovnice dokazuje, že $ x $ je stejné jako nějaký násobek délky smyčky, $ L $ minus $ y $. Pokud tedy rychlý ukazatel začíná v místě setkání, $ M $ nebo $ x + y $, skončí na začátku smyčky.

Komentáře

• Nevím ‚ nevím, proč je tato odpověď podceňována. To se zdá být nejformálnějším důkazem.
• @ I8Again, pokud je x = z špatné, pak logika v pohybu rychlého ukazatele zpět do počátečního bodu & přesuňte oba rychlý & pomalý ukazatel k nalezení začátku smyčky by ‚ nefungoval. Nechápu, co jste mysleli tím, že x = z je špatné, vysvětlete prosím, jak to je?
• @divine x = z je špatné, protože to znamená, že oba jsou si rovni, ale je přijatelné mít velmi dlouhý “ ocas “(velké x) a velmi malý kruh (malý z). Použitím modulo jsme formálně správní, chceme jen dokázat, že x% L == z, jinými slovy ukazatel, který cestuje v kruhu a čeká na připojení k druhému, může vytvořit tolik smyček, kolik chce, pokud poslední kroky (tj. zbytek po smyčce) povedou k zahájení samotného kruhu.
• to je skvělé !!
• Pro ty z vás, kteří ještě neudělali ‚ nerozumí tomu, proč x = k * L – y vede k z = x mod L. Od x = k * L – y — > x = (k – 1) * L + L – y a pak teď můžete říct, že L – y musí být z. Nyní získáte x = (k – 1) * L + z

Řekněme, že existuje $ l $ prvky před zahájením smyčky a $ n $ prvky ve smyčce. A $ e_l $ je prvním prvkem smyčky, který je vidět, když procházíme propojeným seznamem. Když řekneme “ prvek $ x $ , kroky před $ e $ „, to znamená, že se k tomuto prvku můžeme dostat pomocí $ x $ kroků z $ e $ .

Nyní, když Tr (želva) dosáhne $ e_l $ , po $ l $ iterace, řekněme, Hr (Hare) je $ x $ kroky před $ e_l $ . Jelikož do té doby Hr podnikl $ 2l $ kroky ( $ l $ kroky před smyčkou), takže:

$ x = l \ bmod n $ .

V každé budoucí iteraci bude Tr a Hr postupovat o 1 a 2 kroky, takže každá iterace zvýší jejich “ mezeru “ o 1. Takže se setkají po $ nx $ další iterace, kdy se jejich mezera změní na $ x + (nx) = n $ . Takže prvek schůzky $ M $ bude $ nx $ kroky před $ e_l $ . To nyní znamená, že krokování $ x $ kroků po $ M $ nás opět přivede na $ e_l $ . Naším cílem je najít $ e_l $ .

Takže když začneme s jednou referencí Tr na $ M $ a další referenční Hr v čele propojeného seznamu a postupujte oba po 1 kroku po iteracích $ l $ :

• Hr bude $ l $ kroky před hlavou, což je $ e_l $ .

• Tr bude $ (l \ bmod n) $ kroků před $ M $ , tj. $ x $ kroky před $ M $ , což je $ e_l $ .

Tedy pokud mají splněny, víme, že je to $ e_l $ .

Viz tento článek pro detaily. Zde najdete mírně upravenou metodu k vyhledání $ e_l $ .

Odpověď jsem našel na stackoverflow. Díky, pokud to někdo pro mě hledal. A pro ty, kteří jako já chtěli vysvětlení, přečtěte si: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Vybraná odpověď na otázku vysvětluje to!

Také si myslím, že hlavní odpověď je neúplná, a zatímco některá další vysvětlení jsou také dobrá, mám další verze bez MOD, která zobrazuje stejnou věc, což je pro některé lidi snad jednodušší.

Stejné nastavení považujte za $ X \ ge 0 $ vzdálenost před smyčkou, $ N \ le \ text {velikost seznamu} $ je velikost smyčky (množství $ y + z $ na obrázku) a místo setkání bude $ Y $ ve smyčce. V tomto okamžiku si všimněte, že jsme také vytvořili $ X + Y \ le N $ .

Nyní pomalý ukazatel cestuje $ X + Y + pN $ , kde $ p $ je libovolné celé číslo. Pak cestoval rychlý ukazatel $ 2 (X + Y + pN) $ .

Nyní jsme tvrdí , že se setkají na $ Y $ .

Důkaz :

Pokud se setkají na $ Y $ , musí to být že rychlejší ukazatel cestoval přesně $ qN $ více než pomalejší ukazatel, kde $ q $ je celé číslo . Pak máme: $$ \ text {distance difference =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Ale měli jsme $ Y $ jako libovolný bod setkání ve smyčce, takže si můžeme vybrat jednoduše $ X + Y = N $ , které platí jako $ X + Y \ le N $ .

Proto máme: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ což je pravda, pokud $ p + 1 = q $ . Nyní, protože $ p $ a $ q $ jsou libovolná celá čísla, můžeme zvolit pouze minimum, takže že $ p = 0, q = 1 $ , což odpovídá: $$ \ text {vzdálenost ujetou pomalým ukazatelem} = X + Y + pN = X + Y $$ a $$ \ text {ujetá vzdálenost rychlým ukazatelem} = (X + Y + pN) + qN = X + Y + N $$ , takže rychlý ukazatel, který se poprvé setkal s pomalým ukazatelem, cestoval přesně $ N $ více.

Želva a zajíc jsou dva ukazatele, které jsou inicializovány hodnotou „horní části“ seznamu. V každém cyklu smyčky se zajíc zvyšuje o 2 přírůstkové položky, zatímco želva se zvyšuje o jednu. Pokud se v jakémkoli okamžiku zajíc rovná zajíci, byla detekována smyčka. Pokud se zajíc rovná konci, smyčka nebyla nalezena.

Tento příspěvek to vysvětluje lépe řádek po řádku:

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