Floyd ' s Algoritm de detectare a ciclului | Determinarea punctului de plecare al ciclului

Puteți face referire la „Detectarea începutului unei bucle în lista legată individual” , aici este un extras:

Distanța parcursă de slowPointer înainte de întâlnirea $ = x + y $

Distanța parcursă de fastPointer înainte de întâlnirea $ = (x + y + z) + y = x + 2y + z $

Deoarece fastPointer călătorește cu dublă viteza slowPointer și timpul este constant pentru ambele când ajungeți la punctul de întâlnire. Deci, utilizând relația simplă de viteză, timp și distanță (slowPointer a parcurs jumătate din distanță):

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

Prin urmare, mutând slowPointer la începutul listei conectate și făcând ambele slowPointer și fastPointer pentru a muta câte un nod la rând, ambele au aceeași distanță de parcurs .

Vor ajunge în punctul în care începe bucla în lista legată.

Comentarii

• Aici ați presupus că se vor întâlni după o rotație. Pot exista cazuri (în care ciclul este mic) în care s-ar putea întâlni după un anumit nr. de rotații.
• @JotWaraich imaginea nu este reprezentativă pentru toate cazurile; totuși, logica rămâne valabilă
• acesta este cel mai simplu răspuns despre acest algoritm din întregul Internet
• Nu ‘ nu sunt foarte sigur dacă această dovadă este corectă. Distanța parcursă de indicatorul lent trebuie să fie (x + (y + z) * α + y) și distanța parcursă de indicatorul rapid ar trebui să fie (x + (y + z) * β + y) unde α și β sunt numărul de cicluri parcurse de indicatorul lent și rapid. Dovada pare să eșueze cu această adăugare,
• @ hashcode55 da, sunt de acord cu dvs. acest lucru nu este clar pentru mine

Am văzut răspunsul acceptat ca dovadă și în altă parte. Cu toate acestea, deși este ușor de tras, este incorect. Ceea ce dovedește este

$ x = z $ (ceea ce este în mod evident greșit, iar diagrama o face să pară plauzibilă datorită modului în care este schițată).

Ce vrei cu adevărat a demonstra este (folosind aceleași variabile descrise în diagrama din răspunsul acceptat de mai sus):

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

$ (y + z) $ este lungimea buclei, $ L $

deci, ceea ce vrem să dovedim este:

$ z = x \ mod \ L $

Sau că z este congruent cu x (modulul L)

Următoarea dovadă are mai mult sens pentru mine:

Punct de întâlnire, $ M = x + y $

$ 2 (x + y) = M + kL $, unde $ k $ este o constantă.Practic, distanța parcursă de indicatorul rapid este de $ x + y $ plus un multiplu de lungime a buclei, $ L $

$ x + y = kL $

$ x = kL – y $

Ecuația de mai sus demonstrează că $ x $ este același cu un multiplu de lungime a buclei, $ L $ minus $ y $. Deci, dacă indicatorul rapid începe la punctul de întâlnire, $ M $ sau la $ x + y $, atunci va ajunge la începutul buclei.

Comentarii

• Nu ‘ nu știu de ce acest răspuns este subevaluat. Aceasta pare a fi cea mai formală dovadă.
• @ I8Din nou dacă x = z este greșit, atunci logica în deplasarea rapidă a indicatorului înapoi la punctul de pornire & mutați ambele rapid & indicatorul lent pentru a găsi începutul buclei nu ar funcționa ‘. Nu înțeleg ce ați vrut să înțelegeți prin x = z este greșit, vă rog să explicați cum este? coada ”(x mare) și un cerc foarte mic (z mic). Folosind modulul suntem corecti din punct de vedere formal, vrem doar să dovedim că x% L == z, cu alte cuvinte indicatorul care călătorește în cercul care așteaptă să se alăture celuilalt poate face câte bucle vrea, atâta timp cât ultimii pași (adică restul după buclă) vor duce la începutul cercului în sine.
• este grozav !!
• Pentru cei dintre voi care încă nu ‘ nu înțelegeți de ce x = k * L – y duce la z = x mod L. De la x = k * L – y — > x = (k – 1) * L + L – y și acum puteți spune că L – y trebuie să fie z. Acum, veți obține x = (k – 1) * L + z

Spuneți că există $ l $ elemente înainte ca bucla să înceapă și $ n $ elemente în buclă. Și $ e_l $ este primul element al buclei care se vede atunci când traversăm lista legată. Când vom spune ” un element $ x $ cu pași înainte de $ e $ „, asta va însemna că putem ajunge la acel element făcând pași $ x $ din $ e $ .

Acum, când Tr (broasca țestoasă) ajunge la $ e_l $ , după $ l $ iterații, să zicem, Hr (Hare) este cu $ x $ pași înaintea $ e_l $ . Deoarece Hr a parcurs pașii $ 2l $ până atunci ( $ l $ pași înainte de buclă), deci:

$ x = l \ bmod n $ .

În fiecare iterație viitoare, Tr și Hr vor progresa cu 1 și respectiv 2 pași, astfel încât fiecare iterație își va crește ” decalajul ” cu 1. Deci se vor întâlni după $ nx $ iterații suplimentare, când decalajul lor va deveni $ x + (nx) = n $ . Deci, elementul de întâlnire $ M $ va fi cu $ nx $ pași înainte de $ e_l $ . Asta înseamnă că, pasul cu $ x $ pași după $ M $ ne va aduce din nou la $ e_l $ . Scopul nostru este să localizăm $ e_l $ .

Deci, atunci când începem cu o referință Tr la $ M $ și o altă referință Hr în capul listei de linkuri și progresați amândoi câte un pas la rând, după $ l $ iterații :

• Hr va fi cu $ l $ pași înainte de cap, care este $ e_l $ .

• Tr va fi $ (l \ bmod n) $ înaintea $ M $ , adică $ x $ pași înaintea $ M $ , care este $ e_l $ .

Astfel când au întâlnit, știm că este $ e_l $ .

Consultați acest articol pentru detalii. Acolo veți găsi o metodă ușor modificată pentru a localiza $ e_l $ .

Am găsit răspunsul pe stackoverflow. Mulțumesc dacă cineva se uită la asta pentru mine. Și pentru cei care ca mine au dorit o explicație, vă rugăm să consultați: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Răspunsul ales la întrebare, explică aceasta!

De asemenea, cred că răspunsul de sus este incomplet și, deși unele dintre celelalte explicații sunt, de asemenea, bune, am o altă versiune fără MOD pentru a arăta același lucru, ceea ce este poate mai ușor pentru unii oameni.

Aceeași configurare, considerați $ X \ ge 0 $ distanța înainte de buclă, $ N \ le \ text {mărimea listei} $ fiind dimensiunea buclei (cantitatea $ y + z $ în imagine), iar punctul de întâlnire să fie $ Y $ în Buclă. În acest moment, observați că am făcut și $ X + Y \ le N $ .

Acum, indicatorul lent călătorește $ X + Y + pN $ , unde $ p $ este un număr întreg arbitrar. Apoi, indicatorul rapid a călătorit $ 2 (X + Y + pN) $ .

Acum, susțineți că se întâlnesc la $ Y $ .

Dovadă :

Dacă se întâlnesc la $ Y $ , trebuie să fie că indicatorul mai rapid a călătorit exact $ qN $ mai mult decât indicatorul mai lent, unde $ q $ este un număr întreg . Apoi avem: $$ \ text {distance difference =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Dar $ Y $ aveam un punct de întâlnire arbitrar în buclă, deci putem alege pur și simplu $ X + Y = N $ , care se menține ca $ X + Y \ le N $ .

Prin urmare, avem: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ ceea ce este adevărat dacă $ p + 1 = q $ . Acum, deoarece atât $ p $ , cât și $ q $ sunt numere întregi arbitrare, putem alege doar minimul acel $ p = 0, q = 1 $ , care corespunde: $$ \ text {distanța parcursă de indicatorul lent} = X + Y + pN = X + Y $$ și $$ \ text {distanța parcursă prin pointer rapid} = (X + Y + pN) + qN = X + Y + N $$ astfel încât indicatorul rapid, la prima întâlnire cu indicatorul lent, a călătorit exact cu $ N $ mai mult.

Broasca țestoasă și iepurele sunt doi indicatori care sunt inițializați cu valoarea „topului” listei. În fiecare ciclu al buclei, iepurele crește cu 2 obiecte incrementale, în timp ce broasca țestoasă crește cu unul. Dacă în orice moment, iepurele este egal cu iepurele, a fost detectată o buclă. Dacă iepurele este egal cu sfârșitul, nu se găsește o buclă.

Această postare o explică mai bine rând cu rând:

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