Floyd ' s Cykeldetekteringsalgoritm | Fastställande av startpunkten för cykel

Du kan hänvisa till ”Upptäcka start av en slinga i enstaka länkad lista” , här är ett utdrag:

Avstånd med slowPointer innan mötet $ = x + y $

Avstånd med fastPointer innan $ = (x + y + z) + y = x + 2y + z $

Eftersom fastPointer reser med dubbel hastigheten för slowPointer, och tiden är konstant för båda när de når mötesplatsen. Så genom att använda enkel hastighet, tid och avståndsrelation (slowPointer reste halva avståndet):

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

Därav genom att flytta slowPointer till början av länkad lista och göra båda slowPointer och fastPointer för att flytta en nod i taget, de har båda samma avstånd att täcka .

De når den punkt där slingan börjar i den länkade listan.

Kommentarer

Jag har sett det accepterade svaret som bevis också någon annanstans. Men medan det är lätt att grok, är det felaktigt. Vad det visar är

$ x = z $ (vilket uppenbarligen är fel och diagrammet gör det bara troligt på grund av hur det är ritat).

Vad du verkligen vill ha att bevisa är (med samma variabler som beskrivs i diagrammet i det accepterade svaret ovan):

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

$ (y + z) $ är slinglängden, $ L $

så vad vi vill bevisa är:

$ z = x \ mod \ L $

Eller att z är kongruent till x (modulo L)

Följande bevis är mer meningsfullt för mig:

Mötesplats, $ M = x + y $

$ 2 (x + y) = M + kL $, där $ k $ är något konstant.I grund och botten är avståndet med den snabba pekaren $ x + y $ plus några multipel av slinglängden, $ L $

$ x + y = kL $

$ x = kL – y $

Ovanstående ekvation visar att $ x $ är samma som någon multipel av slinglängden, $ L $ minus $ y $. Så om den snabba pekaren börjar vid mötesplatsen, $ M $ eller vid $ x + y $, kommer den att hamna i början av slingan.

Kommentarer

• Jag vet inte ’ jag vet inte varför detta svar underskattas. Detta verkar vara det mest formella beviset.
• @ I8Fortsätt om x = z är fel då logiken i att flytta snabbpekaren tillbaka till startpunkten & flytta båda snabb & långsam pekare för att hitta början på slingan skulle inte fungera ’. Jag förstår inte vad du menade med x = z är fel, snälla förklara hur det är?
• @ divine x = z är fel eftersom det innebär att båda är lika, men det är acceptabelt att ha en mycket lång “ svans ”(stor x) och en mycket liten cirkel (liten z). Genom att använda modulen är vi formellt korrekta, vi vill bara bevisa att x% L == z, med andra ord pekaren som färdas i cirkeln och väntar på att gå med i den andra kan göra så många loopar som den vill, så länge som de sista stegen (dvs resten efter looping) leder till själva cirkeln.
• det här är fantastiskt !!
• För er som fortfarande inte ’ t förstår varför x = k * L – y leder till z = x mod L. Från x = k * L – y — > x = (k – 1) * L + L – y och nu kan du säga att L – y måste vara z. Nu får du x = (k – 1) * L + z

Säg att det finns $ l $ element innan slingan startar och $ n $ element i slingan. Och $ e_l $ är det första elementet i slingan som ses när vi korsar den länkade listan. När vi säger ” ett element $ x $ steg före $ e $ ”, det betyder att vi kan nå det elementet med $ x $ steg från $ e $ .

Nu när Tr (sköldpadda) når $ e_l $ , efter $ l $ iterationer, säg, Hr (Hare) är $ x $ steg före $ e_l $ . Eftersom Hr har tagit totalt $ 2l $ steg då ( $ l $ steg före slingan), så:

$ x = l \ bmod n $ .

I varje framtida iteration fortsätter Tr och Hr med 1 respektive 2 steg, och så ökar varje iteration deras ” gap ” med 1. Så de möts efter $ nx $ ytterligare iterationer när deras gap blir $ x + (nx) = n $ . Så möteselementet $ M $ kommer att vara $ nx $ steg före $ e_l $ . Nu betyder det att steg $ x $ steg efter $ M $ leder oss igen till $ e_l $ . Vårt mål är att hitta $ e_l $ .

Så när vi börjar med en referens Tr vid $ M $ och en annan referens Hr i huvudet på den länkade listan, och fortsätt dem båda ett steg i taget efter $ l $ iterationer :

• Hr kommer att vara $ l $ steg före huvudet, vilket är $ e_l $ .

• Tr kommer att vara $ (l \ bmod n) $ steg före $ M $ , det vill säga $ x $ steg före $ M $ , vilket är $ e_l $ .

Således när de har träffade, vi vet att det är $ e_l $ .

Se den här artikeln för detaljer. Där hittar du en något modifierad metod för att hitta $ e_l $ .

Jag hittade svaret på stackoverflow. Tack om någon tittade på det här för mig. Och för dem som gillar mig ville ha en förklaring hänvisar vi till: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Det valda svaret på frågan förklarar den!

Jag tycker också att det översta svaret är ofullständigt, och även om en del av den andra förklaringen också är bra, har jag en annan version utan MOD för att visa samma sak, vilket kanske är lättare för vissa människor.

Samma inställning, överväg att $ X \ ge 0 $ är avståndet före slingan, $ N \ le \ text {storlek på listan} $ är storleken på slingan (kvantiteten $ y + z $ på bilden) och mötesplatsen är $ Y $ i Loop. Lägg märke till att vi också har gjort $ X + Y \ le N $ .

Nu rör sig den långsamma pekaren $ X + Y + pN $ , där $ p $ är ett godtyckligt heltal. Sedan reste snabbpekaren $ 2 (X + Y + pN) $ .

Nu hävda att de träffas på $ Y $ .

Bevis :

Om de möts i $ Y $ måste det vara att den snabbare pekaren reste exakt $ qN $ mer än den långsammare pekaren, där $ q $ är ett heltal . Sedan har vi: $$ \ text {distansskillnad =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Men vi hade $ Y $ som en godtycklig mötesplats i slingan, så vi kan välja helt enkelt $ X + Y = N $ , som finns som $ X + Y \ le N $ .

Därför har vi: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ vilket är sant om $ p + 1 = q $ . Eftersom både $ p $ och $ q $ är godtyckliga heltal kan vi bara välja lägsta så att $ p = 0, q = 1 $ , vilket motsvarar: $$ \ text {avstånd med lång pekare} = X + Y + pN = X + Y $$ och $$ \ text {avstånd med snabb pekare} = (X + Y + pN) + qN = X + Y + N $$ så den snabba pekaren, som första gången mötte den långsamma pekaren, reste exakt $ N $ mer.

Sköldpaddan och haren är två pekare som initialiseras med värdet på ”toppen” i listan. I varje kretslopp ökar haren med 2 steg i steg, medan sköldpaddan ökar med en. Om hare vid något tillfälle är lika med hare har en slinga upptäckts. Om haren är lika med slutet hittas inte en slinga.

Detta inlägg förklarar det bättre rad för rad:

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