Floyd ' s Cyclusdetectie-algoritme | Het beginpunt van cyclus

U kunt verwijzen naar “Detectie van het begin van een lus in een enkelvoudig gelinkte lijst” , hier is een uittreksel:

Afgelegde afstand door slowPointer voordat $ = x + y $

Afgelegde afstand door fastPointer voordat $ = (x + y + z) + y = x + 2y + z $

Aangezien fastPointer reist met dubbele de snelheid van slowPointer, en tijd is constant voor beide wanneer ze het ontmoetingspunt bereiken. Dus door een eenvoudige relatie tussen snelheid, tijd en afstand te gebruiken (slowPointer de halve afstand afgelegd):

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

Door slowPointer naar het begin van de gelinkte lijst te verplaatsen en beide slowPointer en fastPointer om één knooppunt tegelijk te verplaatsen, ze moeten allebei dezelfde afstand afleggen .

Ze zullen het punt bereiken waar de lus begint in de gelinkte lijst.

Opmerkingen

• Hier heb je aangenomen dat ze elkaar na één rotatie zullen ontmoeten. Er kunnen gevallen zijn (waarbij de cyclus klein is) waarin ze elkaar na een bepaald nee kunnen ontmoeten. van rotaties.
• @JotWaraich de afbeelding is niet representatief voor alle gevallen; de logica geldt echter nog steeds
• dit is het meest ongecompliceerde antwoord over dit algoritme op het hele internet
• Ik ‘ ben niet erg zeker als dit bewijs klopt. Afstand afgelegd door langzame wijzer moet (x + (y + z) * α + y) zijn en de afstand afgelegd door de snelle wijzer moet (x + (y + z) * β + y) zijn, waarbij α en β het getal zijn van cycli die door de langzame en snelle wijzer worden doorlopen. Het bewijs lijkt te falen met deze toevoeging,
• @ hashcode55 ja ik ben het met je eens, dit is mij niet duidelijk

Ik heb het geaccepteerde antwoord ook elders als bewijs gezien. Hoewel het gemakkelijk te groken is, is het onjuist. Wat het bewijst is

$ x = z $ (wat duidelijk onjuist is, en het diagram maakt het gewoon aannemelijk door de manier waarop het is geschetst).

Wat je echt wilt bewijzen is (met dezelfde variabelen als beschreven in het diagram in het geaccepteerde antwoord hierboven):

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

$ (y + z) $ is de lengte van de lus, $ L $

dus wat we willen bewijzen is:

$ z = x \ mod \ L $

Of dat z congruent is met x (modulo L)

Het volgende bewijs is logischer voor mij:

Ontmoetingspunt, $ M = x + y $

$ 2 (x + y) = M + kL $, waarbij $ k $ een constante is.In feite is de afstand die door de snelle aanwijzer wordt afgelegd $ x + y $ plus een veelvoud van de luslengte, $ L $

$ x + y = kL $

$ x = kL – y $

De bovenstaande vergelijking bewijst dat $ x $ hetzelfde is als een veelvoud van de luslengte, $ L $ minus $ y $. Dus als de snelle aanwijzer begint bij het ontmoetingspunt, $ M $ of bij $ x + y $, dan zal hij eindigen aan het begin van de lus.

Opmerkingen

• Ik weet niet ‘ waarom dit antwoord onderschat wordt. Dit lijkt het meest formele bewijs te zijn.
• @ I8Als x = z fout is, dan logica om de snelle pointer terug te verplaatsen naar het startpunt & beweeg beide snelle & langzame aanwijzer om het begin van de lus te vinden zou niet ‘ werken. ik begrijp niet wat je bedoelde met x = z is verkeerd, leg alsjeblieft uit hoe dat is?
• @divine x = z is fout omdat het impliceert dat beide gelijk zijn, maar het is acceptabel om een zeer lange ” staart ”(grote x) en een heel kleine cirkel (kleine z). Door de modulo te gebruiken hebben we formeel gelijk, we willen alleen bewijzen dat x% L == z, met andere woorden de wijzer die in de cirkel reist en wacht om zich bij de andere aan te sluiten, zoveel lussen kan maken als hij wil, zolang als de laatste stappen (d.w.z. de rest na het herhalen) zullen leiden tot het begin van de cirkel zelf.
• dit is geweldig !!
• Voor degenen onder jullie die het nog steeds niet deden ‘ begrijp niet waarom x = k * L – y leidt tot z = x mod L. Van x = k * L – y — > x = (k – 1) * L + L – y en dan kun je nu zeggen dat L – y z moet zijn. Nu krijg je x = (k – 1) * L + z

Zeg dat er $ l $ elementen voordat de lus begint en $ n $ elementen in de lus. En $ e_l $ is het eerste element van de lus dat wordt gezien wanneer we de gekoppelde lijst doorlopen. Wanneer we ” een element zeggen $ x $ stappen voor $ e $ “, dat betekent dat we dat element kunnen bereiken door $ x $ stappen te nemen van $ e $ .

Nu, wanneer Tr (schildpad) $ e_l $ bereikt, na $ l $ iteraties, bijvoorbeeld Hr (Hare) is $ x $ stappen voor $ e_l $ . Aangezien Hr tegen die tijd in totaal $ 2l $ stappen heeft genomen ( $ l $ stappen voorafgaand aan de lus), dus:

$ x = l \ bmod n $ .

In elke toekomstige iteratie zullen Tr en Hr vooruitgaan met 1 en 2 stappen, en dus zal elke iteratie hun ” gap ” met 1 vergroten. Ze ontmoeten elkaar dus na $ nx $ verdere iteraties, wanneer hun tussenruimte $ x + (nx) = n $ wordt. Het ontmoetingselement $ M $ zal dus $ nx $ stappen voorlopen op $ e_l $ . Dat betekent dat als u $ x $ stappen zet na $ M $ , ons weer naar $ e_l $ . Ons doel is om $ e_l $ te lokaliseren.

Dus als we beginnen met één referentie Tr op $ M $ en een andere referentie Hr bovenaan de gelinkte lijst, en ga beide stap voor stap vooruit, na $ l $ iteraties :

• Hr loopt $ l $ stappen voor op het hoofd, dat is $ e_l $ .

• Tr zijn $ (l \ bmod n) $ stappen voor $ M $ , dat wil zeggen $ x $ stappen voor $ M $ , dat is $ e_l $ .

Dus als ze voldaan, we weten dat het $ e_l $ is.

Zie dit artikel voor details. Daar vindt u een licht gewijzigde methode om $ e_l $ te lokaliseren.

Ik vond het antwoord op stackoverflow. Bedankt als iemand dit voor mij heeft onderzocht. En voor degenen die zoals ik een uitleg wilden, raadpleeg: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Het gekozen antwoord op de vraag, legt uit het!

Ik denk ook dat het bovenste antwoord onvolledig is, en hoewel sommige van de andere verklaringen ook goed zijn, heb ik een andere versie zonder MOD om hetzelfde te laten zien, wat voor sommige mensen misschien gemakkelijker is.

Dezelfde opzet, beschouw $ X \ ge 0 $ als de afstand vóór de lus, $ N \ le \ text {size of list} $ is de grootte van de lus (de hoeveelheid $ y + z $ in de afbeelding), en het ontmoetingspunt bevindt zich $ Y $ in de lus. Merk op dat we op dit moment ook $ X + Y \ le N $ hebben gemaakt.

Nu reist de langzame aanwijzer $ X + Y + pN $ , waarbij $ p $ een willekeurig geheel getal is. Daarna reisde de snelle aanwijzer $ 2 (X + Y + pN) $ .

Nu claim dat ze elkaar ontmoeten in $ Y $ .

Bewijs :

Als ze elkaar ontmoeten op $ Y $ , moet het zijn dat de snellere aanwijzer precies $ qN $ meer reisde dan de langzamere aanwijzer, waarbij $ q $ een geheel getal is . Dan hebben we: $$ \ text {afstandsverschil =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Maar we hadden $ Y $ als een willekeurig ontmoetingspunt in de lus, dus we kunnen eenvoudig $ X + Y = N kiezen $ , die geldt als $ X + Y \ le N $ .

Daarom hebben we: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ wat waar is als $ p + 1 = q $ . Aangezien zowel $ p $ en $ q $ willekeurige gehele getallen zijn, kunnen we gewoon het minimum kiezen, zodat dat $ p = 0, q = 1 $ , wat overeenkomt met: $$ \ text {afstand afgelegd door langzame wijzer} = X + Y + pN = X + Y $$ en $$ \ text {afgelegde afstand door snelle pointer} = (X + Y + pN) + qN = X + J + N $$ zodat de snelle wijzer, die de langzame wijzer voor het eerst ontmoette, precies $ N $ meer aflegde.

De schildpad en de haas zijn twee verwijzingen die worden geïnitialiseerd met de waarde van de “top” van de lijst. In elke cyclus van de lus neemt de haas toe met 2 incrementele items, terwijl de schildpad met één toeneemt. Als op enig moment de haas gelijk is aan de haas, is er een lus gedetecteerd. Als de haas gelijk is aan het einde, wordt er geen lus gevonden.

In dit bericht wordt het regel voor regel beter uitgelegd:

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