Floyd ' s Algoritmo di rilevamento del ciclo | Determinazione del punto di partenza del ciclo

Puoi fare riferimento a “Rilevamento dellinizio di un ciclo in un elenco collegato singolarmente” , ecco un estratto:

Distanza percorsa da slowPointer prima di incontrare $ = x + y $

Distanza percorsa da fastPointer prima di incontrare $ = (x + y + z) + y = x + 2y + z $

Poiché fastPointer viaggia con raddoppia la velocità di slowPointer e il tempo è costante per entrambi quando raggiungono il punto di incontro. Quindi, utilizzando la semplice relazione di velocità, tempo e distanza (slowPointer ha percorso metà della distanza):

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

Quindi spostando slowPointer allinizio dellelenco collegato e impostando entrambi slowPointer e fastPointer per spostare un nodo alla volta, hanno entrambi la stessa distanza da coprire .

Arriveranno al punto in cui inizia il ciclo nellelenco collegato.

Commenti

• Qui hai ipotizzato che si incontreranno dopo una rotazione. Ci possono essere casi (in cui il ciclo è piccolo) in cui potrebbero incontrarsi dopo un certo no. di rotazioni.
• @JotWaraich limmagine non è rappresentativa di tutti i casi; la logica tuttavia è ancora valida
• questa è la risposta più diretta su questo algoritmo in tutta Internet
• Non ‘ non ne sono molto sicuro se questa prova è corretta. La distanza percorsa dal puntatore lento dovrebbe essere (x + (y + z) * α + y) e la distanza percorsa dal puntatore veloce dovrebbe essere (x + (y + z) * β + y) dove α e β sono il numero di cicli attraversati dal puntatore lento e veloce. La prova sembra fallire con questa aggiunta,
• @ hashcode55 sì sono daccordo con te questo non mi è chiaro

Ho visto la risposta accettata come prova anche altrove. Tuttavia, sebbene sia facile lamentarsi, non è corretto. Ciò che dimostra è

$ x = z $ (il che è ovviamente sbagliato e il diagramma lo fa sembrare plausibile per il modo in cui è disegnato).

Quello che vuoi veramente provare è (utilizzando le stesse variabili descritte nel diagramma nella risposta accettata sopra):

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

$ (y + z) $ è la lunghezza del ciclo, $ L $

quindi, quello che vogliamo dimostrare è:

$ z = x \ mod \ L $

O che z sia congruente ax (modulo L)

La seguente dimostrazione ha più senso per me:

Punto dincontro, $ M = x + y $

$ 2 (x + y) = M + kL $, dove $ k $ è una costante.Fondamentalmente, la distanza percorsa dal puntatore veloce è $ x + y $ più qualche multiplo della lunghezza del loop, $ L $

$ x + y = kL $

$ x = kL – y $

Lequazione precedente dimostra che $ x $ è uguale a un multiplo della lunghezza del ciclo, $ L $ meno $ y $. Quindi, se il puntatore veloce inizia nel punto di incontro, $ M $ o $ x + y $, finirà allinizio del ciclo.

Commenti

• Non ‘ so perché questa risposta è sottovalutata. Questa sembra essere la prova più formale.
• @ I8Again se x = z è sbagliato, allora la logica per riportare il puntatore veloce al punto di partenza & sposta entrambi & puntatore lento per trovare linizio del ciclo non ‘ funzionerebbe. Non capisco cosa intendevi per x = z è sbagliato, per favore spiegami comè?
• @divine x = z è sbagliato perché implica che entrambi sono uguali, ma è accettabile avere un ” coda ”(x grande) e un cerchio molto piccolo (z piccola). Usando il modulo siamo formalmente corretti, vogliamo solo provare che x% L == z, in altre parole il puntatore che viaggia nel cerchio in attesa di unirsi allaltro può fare tanti loop quanti ne vuole, purché gli ultimi passaggi (cioè il resto dopo il ciclo) porteranno allinizio del cerchio stesso.
• questo è fantastico !!
• Per quelli di voi che non lhanno ancora fatto ‘ t capire perché x = k * L – y porta a z = x mod L. Da x = k * L – y — > x = (k – 1) * L + L – y e poi ora puoi dire che L – y deve essere z. Ora ottieni x = (k – 1) * L + z

Dì che ci sono $ l $ elementi prima dellinizio del ciclo e $ n $ nel ciclo. E $ e_l $ è il primo elemento del ciclo che viene visualizzato quando attraversiamo lelenco collegato. Quando diremo ” un elemento $ x $ passi prima di $ e $ “, ciò significa che possiamo raggiungere quellelemento facendo $ x $ passaggi da $ e $ .

Ora, quando Tr (tortoise) raggiunge $ e_l $ , dopo $ l $ iterazioni, ad esempio, Hr (Hare) è $ x $ passi avanti rispetto a $ e_l $ . Poiché Hr ha completato $ 2l $ passaggi in totale ( $ l $ passaggi prima del ciclo), quindi:

$ x = l \ bmod n $ .

In ogni iterazione futura, Tr e Hr avanzeranno di 1 e 2 passaggi rispettivamente, quindi ogni iterazione aumenterà il loro ” gap ” di 1. Quindi si incontreranno dopo $ nx $ ulteriori iterazioni, quando il loro divario diventerà $ x + (nx) = n $ . Quindi, lelemento riunione $ M $ sarà $ nx $ passi avanti rispetto a $ e_l $ . Ciò significa che, eseguire $ x $ passaggi dopo $ M $ ci porterà di nuovo a $ e_l $ . Il nostro obiettivo è individuare $ e_l $ .

Quindi, quando iniziamo con un riferimento Tr in $ M $ e un altro riferimento Hr allinizio dellelenco collegato e avanzare entrambi 1 passaggio alla volta, dopo $ l $ iterazioni :

• Hr sarà $ l $ passi avanti rispetto alla testa, che è $ e_l $ .

• Tr sarà $ (l \ bmod n) $ passaggi prima di $ M $ , ovvero $ x $ passi prima di $ M $ , che è $ e_l $ .

Così quando hanno met, sappiamo che è $ e_l $ .

Vedi questo articolo per dettagli. Lì troverai un metodo leggermente modificato per individuare $ e_l $ .

Ho trovato la risposta su stackoverflow. Grazie se qualcuno stava esaminando questo per me. E per chi come me desiderava una spiegazione, fare riferimento a: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list La risposta scelta alla domanda, spiega esso!

Penso anche che la risposta principale sia incompleta e, sebbene alcune delle altre spiegazioni siano valide, ne ho unaltra versione senza MOD per mostrare la stessa cosa, che forse è più facile per alcune persone.

La stessa configurazione, considera $ X \ ge 0 $ la distanza prima del loop, $ N \ le \ text {size of list} $ è la dimensione del loop (la quantità $ y + z $ nellimmagine) e il punto di incontro sarà $ Y $ nel Loop. A questo punto, nota che abbiamo anche creato $ X + Y \ le N $ .

Ora, il puntatore lento viaggia $ X + Y + pN $ , dove $ p $ è un numero intero arbitrario. Quindi il puntatore veloce ha viaggiato $ 2 (X + Y + pN) $ .

Ora, noi afferma di incontrarsi a $ Y $ .

Prova :

Se si incontrano a $ Y $ , deve essere che il puntatore più veloce ha viaggiato esattamente $ qN $ più del puntatore più lento, dove $ q $ è un numero intero . Quindi abbiamo: $$ \ text {differenza di distanza =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Tuttavia, $ Y $ era un punto di incontro arbitrario nel ciclo, quindi possiamo scegliere semplicemente $ X + Y = N $ , che vale come $ X + Y \ le N $ .

Pertanto, abbiamo: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ che è vero se $ p + 1 = q $ . Ora, poiché sia $ p $ e $ q $ sono numeri interi arbitrari, possiamo semplicemente scegliere il minimo che $ p = 0, q = 1 $ , che corrisponde a: $$ \ text {distanza percorsa da slow pointer} = X + Y + pN = X + Y $$ e $$ \ text {distanza percorsa dal puntatore veloce} = (X + Y + pN) + qN = X + Y + N $$ così il puntatore veloce, alla prima volta che incontrava il puntatore lento, ha viaggiato esattamente $ N $ in più.

La tartaruga e la lepre sono due puntatori che vengono inizializzati con il valore della “cima” della lista. In ogni ciclo del ciclo, la lepre aumenta di 2 elementi incrementali, mentre la tartaruga aumenta di uno. Se in qualsiasi momento la lepre è uguale alla lepre, è stato rilevato un loop. Se la lepre è uguale alla fine, non viene trovato un ciclo.

Questo post lo spiega meglio riga per riga:

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