Floyd ' s Syklusdeteksjonsalgoritme | Bestemme startpunktet for syklus

Du kan referere til «Oppdage start av en løkke i enkeltkoblet liste» , her er et utdrag:

Avstand tilbakelagt med slowPointer før du møter $ = x + y $

Avstand tilbakelagt med fastPointer før du møter $ = (x + y + z) + y = x + 2y + z $

Siden fastPointer reiser med dobbelt hastigheten på slowPointer, og tiden er konstant for begge når du når møtepunktet. Så ved å bruke enkel hastighet, tid og avstandsrelasjon (slowPointer reiste halvparten av distansen):

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

Derfor ved å flytte slowPointer til starten av den koblede listen, og lage begge slowPointer og fastPointer for å flytte en node av gangen, de har begge samme avstand til å dekke .

De kommer til det punktet der sløyfen starter i den koblede listen.

Kommentarer

• Her har du lagt til grunn at de vil møtes etter en turnus. Det kan være tilfeller (hvor syklusen er liten) der de kan møtes etter visst nei. av rotasjoner.
• @JotWaraich bildet er ikke representativt for alle tilfeller; logikken holder imidlertid fremdeles
• dette er det mest rett frem svaret om denne algoritmen på hele Internett
• Jeg ‘ er ikke veldig sikker hvis dette beviset er riktig. Avstand tilbakelagt med langsom peker skal være (x + (y + z) * α + y) og avstanden som ble reist med hurtigpekeren skal være (x + (y + z) * β + y) hvor α og β er tallet av sykluser krysset av den sakte og raske pekeren. Beviset ser ut til å mislykkes med dette tillegget,
• @ hashcode55 ja jeg er enig med deg dette er ikke klart for meg

Jeg har sett det aksepterte svaret som bevis andre steder også. Selv om det er lett å groke, er det imidlertid feil. Det det viser seg er

$ x = z $ (som åpenbart er galt, og diagrammet gjør det bare plausibelt på grunn av måten det er tegnet på).

Det du virkelig vil ha å bevise er (ved hjelp av de samme variablene som beskrevet i diagrammet i det aksepterte svaret ovenfor):

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

$ (y + z) $ er sløyfelengden, $ L $

så det vi ønsker å bevise er:

$ z = x \ mod \ L $

Eller at z er kongruent til x (modulo L)

Følgende bevis gir mer mening for meg:

Møtepunkt, $ M = x + y $

$ 2 (x + y) = M + kL $, hvor $ k $ er noe konstant.I utgangspunktet er avstanden med den hurtige pekeren $ x + y $ pluss noen multiplum av sløyfelengden, $ L $

$ x + y = kL $

$ x = kL – y $

Ovennevnte ligning viser at $ x $ er det samme som noen multiplum av sløyfelengden, $ L $ minus $ y $. Så hvis den raske pekeren starter på møtepunktet, $ M $ eller ved $ x + y $, vil den havne i starten av løkken.

Kommentarer

• Jeg vet ikke ‘ ikke hvorfor er dette svaret undervurdert. Dette ser ut til å være det mest formelle beviset.
• @ I8Fra igjen hvis x = z er feil, så flytt logikken i å flytte rask pekeren tilbake til startpunktet & rask & langsom peker for å finne starten på sløyfen ville ikke fungere ‘. jeg forstår ikke hva du mente med x = z er feil, vennligst forklar hvordan det er?
• @ divine x = z er feil fordi det antyder at begge er like, men det er akseptabelt å ha en veldig lang “ hale ”(stor x) og en veldig liten sirkel (liten z). Ved å bruke modulo er vi formelt riktig, vi vil bare bevise at x% L == z, med andre ord pekeren som beveger seg i sirkelen og venter på å bli med den andre, kan lage så mange løkker som den vil, så lenge de siste trinnene (dvs. resten etter sløyfing) vil føre til starten på selve sirkelen.
• dette er flott !!
• For de av dere som fremdeles ikke ‘ t forstå hvorfor x = k * L – y fører til z = x mod L. Fra x = k * L – y — > x = (k – 1) * L + L – y, og nå kan du fortelle at L – y må være z. Nå får du x = (k – 1) * L + z

Si at det er $ l $ elementer før loop starter og $ n $ elementer i loop. Og $ e_l $ er det første elementet i sløyfen som sees når vi krysser den koblede listen. Når vi vil si » et element $ x $ skritt foran $ e $ «, det vil si at vi kan nå det elementet tar $ x $ trinn fra $ e $ .

Nå når Tr (skilpadde) når $ e_l $ , etter $ l $ iterasjoner, si Hr (Hare) er $ x $ trinn foran $ e_l $ . Siden Hr har tatt totalt $ 2 $ $ trinn da ( $ l $ trinn før løkken), så:

$ x = l \ bmod n $ .

I hver fremtidig iterasjon vil Tr og Hr utvikle seg med 1 og 2 trinn, og slik vil hver iterasjon øke » gap » med 1. Så de møtes etter $ nx $ ytterligere iterasjoner når gapet deres blir $ x + (nx) = n $ . Møteelementet $ M $ vil være $ nx $ trinn foran $ e_l $ . Nå betyr det at å gå $ x $ trinn etter $ M $ igjen vil bringe oss til $ e_l $ . Målet vårt er å finne $ e_l $ .

Så når vi begynner med en referanse Tr på $ M $ og en annen referanse Hr i spissen for den koblede listen, og fortsett begge to trinn om gangen etter $ l $ iterasjoner :

• Hr vil være $ l $ skritt foran hodet, som er $ e_l $ .

• Tr vil være $ (l \ bmod n) $ trinn foran $ M $ , det vil si $ x $ trinn foran $ M $ , som er $ e_l $ .

Dermed når de har møtt, vi vet at det er $ e_l $ .

Se denne artikkelen for detaljer. Der finner du en litt modifisert metode for å finne $ e_l $ .

Jeg fant svaret på stackoverflow. Takk hvis noen så på dette for meg. Og for de som liker meg, vil du se: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Det valgte svaret på spørsmålet, forklarer den!

Jeg synes også toppsvaret er ufullstendig, og mens noen av de andre forklaringene også er gode, har jeg en annen versjon uten MOD for å vise det samme, noe som kanskje er lettere for noen mennesker.

Det samme oppsettet, vurder $ X \ ge 0 $ å være avstanden før sløyfen, $ N \ le \ text {size of list} $ er størrelsen på sløyfen (mengden $ y + z $ på bildet), og møtepunktet er $ Y $ i Loop. På dette punktet, legg merke til at vi også har laget $ X + Y \ le N $ .

Nå går den langsomme pekeren $ X + Y + pN $ , der $ p $ er et vilkårlig heltall. Deretter reiste rask peker $ 2 (X + Y + pN) $ .

Nå hevder at de møtes på $ Y $ .

Bevis :

Hvis de møtes på $ Y $ , må det være at den raskere pekeren reiste nøyaktig $ qN $ mer enn den langsommere pekeren, der $ q $ er et heltall . Så har vi: $$ \ text {distance difference =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Men vi hadde $ Y $ som et vilkårlig møtepunkt i løkken, så vi kan bare velge $ X + Y = N $ , som holder som $ X + Y \ le N $ .

Derfor har vi: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ som er sant hvis $ p + 1 = q $ . Siden både $ p $ og $ q $ er vilkårlige heltall, kan vi bare velge minimum så at $ p = 0, q = 1 $ , som tilsvarer: $$ \ text {avstand tilbakelagt med langsom peker} = X + Y + pN = X + Y $$ og $$ \ text {tilbakelagt avstand med hurtigpeker} = (X + Y + pN) + qN = X + Y + N $$ så den raske pekeren, for første gang møtte den langsomme pekeren, reiste nøyaktig $ N $ mer.

Skilpadden og haren er to pekere som initialiseres med verdien til «toppen» på listen. I hver syklus av løkken øker haren med 2 trinnvise gjenstander, mens skilpadden øker med en. Hvis haren på noe tidspunkt er lik haren, har det blitt oppdaget en løkke. Hvis haren er lik slutten, blir det ikke funnet en løkke.

Dette innlegget forklarer det bedre linje for linje:

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