Floyd ' s Cyklusdetekteringsalgoritme | Bestemmelse af startpunktet for cyklus

Du kan henvise til “Registrering af start af en sløjfe i en enkelt sammenkædet liste” , her er et uddrag:

Afstand tilbagelagt med slowPointer inden møde $ = x + y $

Afstand tilbagelagt med fastPointer inden møde $ = (x + y + z) + y = x + 2y + z $

Da fastPointer rejser med dobbelt hastigheden på slowPointer, og tiden er konstant for begge, når de når mødestedet. Så ved at bruge simpel hastighed, tid og afstandsrelation (slowPointer tilbagelagt halvdelen af afstanden):

\ 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 at flytte slowPointer til starten af den sammenkædede liste og lave begge slowPointer og fastPointer for at flytte en node ad gangen, de har begge samme afstand til at dække .

De når det punkt, hvor sløjfen starter på den linkede liste.

Kommentarer

• Her har du antaget, at de mødes efter en rotation. Der kan være tilfælde (hvor cyklussen er lille), hvor de måske mødes efter bestemt nej. af rotationer.
• @JotWaraich billedet er ikke repræsentativt for alle tilfælde; logikken holder dog stadig
• dette er det mest ligefremme svar om denne algoritme på hele Internettet
• Jeg ‘ er ikke meget sikker hvis dette bevis er korrekt. Den tilbagelagte afstand med langsom markør skal være (x + (y + z) * α + y), og den tilbagelagte afstand med den hurtige markør skal være (x + (y + z) * β + y) hvor α og β er antallet af cyklusser, der krydses af den langsomme og hurtige markør. Beviset synes at mislykkes med denne tilføjelse,
• @ hashcode55 ja jeg er enig med dig, dette er ikke klart for mig

Jeg har også set det accepterede svar som et bevis andetsteds. Selvom det er let at grok, er det imidlertid forkert. Hvad det beviser er

$ x = z $ (hvilket naturligvis er forkert, og diagrammet gør det bare plausibelt på grund af den måde, det er skitseret).

Hvad du virkelig vil have at bevise er (ved hjælp af de samme variabler som beskrevet i diagrammet i det accepterede svar ovenfor):

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

$ (y + z) $ er sløjfelængden, $ L $

så hvad vi vil bevise er:

$ z = x \ mod \ L $

Eller at z er kongruent til x (modulo L)

Følgende bevis giver mig mere mening:

Mødested, $ M = x + y $

$ 2 (x + y) = M + kL $, hvor $ k $ er noget konstant.Dybest set er den tilbagelagte afstand med den hurtige markør $ x + y $ plus nogle multiplum af sløjfelængde, $ L $

$ x + y = kL $

$ x = kL – y $

Ovenstående ligning beviser, at $ x $ er den samme som et eller flere multiple af sløjfelængder, $ L $ minus $ y $. Så hvis den hurtige markør starter ved mødestedet, $ M $ eller ved $ x + y $, ender den i starten af sløjfen.

Kommentarer

• Jeg ved ‘ ikke, hvorfor er dette svar undervurderet. Dette ser ud til at være det mest formelle bevis.
• @ I8Fortsæt hvis x = z er forkert, så logik i at flytte hurtig markør tilbage til startpunktet & flyt begge hurtig & langsom markør for at finde starten på sløjfen ville ‘ ikke fungere. jeg forstår ikke, hvad du mente med x = z er forkert, vær venlig at forklare, hvordan det er?
• @ divine x = z er forkert, fordi det indebærer, at begge er ens, men det er acceptabelt at have en meget lang “ hale ”(stor x) og en meget lille cirkel (lille z). Ved at bruge modulo er vi formelt korrekte, vi vil bare bevise, at x% L == z, med andre ord markøren, der bevæger sig i cirklen og venter på at slutte sig til den anden, kan lave så mange løkker, som den vil, så længe de sidste trin (dvs. resten efter looping) vil føre til starten af selve cirklen.
• dette er fantastisk !!
• For dem af jer, der stadig 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 så kan du nu fortælle, at L – y skal være z. Nu får du x = (k – 1) * L + z

Sig der er $ l $ elementer før sløjfen starter og $ n $ elementer i sløjfen. Og $ e_l $ er det første element i sløjfen, der ses, når vi krydser den sammenkædede liste. Når vi siger ” et element $ x $ skridt foran $ e $ “, det vil sige, vi kan nå det element, der tager $ x $ trin fra $ e $ .

Nu når Tr (skildpadde) når $ e_l $ efter $ l $ iterationer, siger Hr (Hare) er $ x $ skridt foran $ e_l $ . Da Hr har taget i alt $ 2l $ trin inden da ( $ l $ trin inden sløjfen), så:

$ x = l \ bmod n $ .

I hver fremtidig iteration vil Tr og Hr udvikle sig med 1 og 2 trin, og således øger hver iteration deres ” hul ” med 1. Så de mødes efter $ nx $ yderligere iterationer, når deres hul bliver $ x + (nx) = n $ . Så mødeelementet $ M $ vil være $ nx $ trin foran $ e_l $ . Nu betyder det, at træde $ x $ trin efter $ M $ igen bringer os til $ e_l $ . Vores mål er at finde $ e_l $ .

Så når vi starter med en reference Tr ved $ M $ og en anden reference Hr i spidsen for den linkede liste, og fremskridt med dem begge 1 ad gangen efter $ l $ iterationer :

• Hr vil være $ l $ skridt foran hovedet, hvilket er $ e_l $ .

• Tr vil være $ (l \ bmod n) $ trin foran $ M $ , dvs. $ x $ skridt foran $ M $ , hvilket er $ e_l $ .

Således når de har mødt, vi ved, at det er $ e_l $ .

Se denne artikel for detaljer. Der finder du en let modificeret metode til at finde $ e_l $ .

Jeg synes også, at det øverste svar er ufuldstændigt, og mens nogle af de andre forklaringer også er gode, har jeg en anden version uden MOD for at vise det samme, hvilket måske er lettere for nogle mennesker.

Den samme opsætning, overvej $ X \ ge 0 $ at være afstanden før sløjfen, $ N \ le \ text {størrelse på listen} $ er størrelsen på sløjfen (mængden $ y + z $ på billedet), og mødestedet er $ Y $ i sløjfen. På dette tidspunkt skal du bemærke, at vi også har lavet $ X + Y \ le N $ .

Nu bevæger den langsomme markør $ X + Y + pN $ , hvor $ p $ er et vilkårligt heltal. Derefter rejste hurtig markør $ 2 (X + Y + pN) $ .

Nu hævder at de mødes i $ Y $ .

Bevis :

Hvis de mødes i $ Y $ , skal det være at den hurtigere markør rejste nøjagtigt $ qN $ mere end den langsommere markør, hvor $ q $ er et heltal . Så har vi: $$ \ text {distance difference =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Men vi havde $ Y $ som et vilkårligt mødested i sløjfen, så vi kan bare vælge $ X + Y = N $ , der holder som $ X + Y \ le N $ .

Derfor har vi: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ hvilket er sandt, hvis $ p + 1 = q $ . Da både $ p $ og $ q $ er vilkårlige heltal, kan vi bare vælge minimum så at $ p = 0, q = 1 $ , hvilket svarer til: $$ \ text {afstand tilbagelagt med langsom markør} = X + Y + pN = X + Y $$ og $$ \ text {tilbagelagt afstand med hurtig markør} = (X + Y + pN) + qN = X + Y + N $$ så den hurtige markør, der første gang mødte den langsomme markør, rejste nøjagtigt $ N $ mere.

Skildpadden og haren er to pegepinde, der initialiseres med værdien for “toppen” på listen. I hver sløjfecyklus stiger haren med 2 trin, mens skildpadden stiger med en. Hvis haren på et tidspunkt er lig med haren, er der registreret en løkke. Hvis haren er lig med slutningen, findes der ikke en løkke.

Dette indlæg 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