algoritmo di rilevamento del ciclo di Floyd | Determinare il punto di partenza del ciclo

Question

Sto cercando aiuto capire algoritmo di rilevamento ciclo di Floyd. Ho passato con la spiegazione su wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Posso vedere come l'algoritmo rileva ciclo in O (n). Tuttavia, non sono in grado di visualizzare il fatto che una volta tartaruga e puntatori lepre incontrano per la prima volta, l'inizio del ciclo può essere determinata spostando tartaruga puntatore indietro per iniziare e poi si spostano sia tartaruga e passo uno lepre alla volta. Il punto in cui primo incontro è l'inizio del ciclo.

Qualcuno può aiutarmi, fornendo una spiegazione, si spera diverso da quello su wikipedia, come io sono in grado di capire / visualizzarla?

Answer 1

Ho trovato la risposta su StackOverflow. Grazie se qualcuno era alla ricerca in questo per me. E per chi, come me, ha voluto una spiegazione, si prega di fare riferimento a: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list la risposta scelta alla domanda, spiega tutto!

Answer 2

Si può fare riferimento a "Rilevazione inizio di un ciclo in lista concatenata" , ecco un estratto:

distanza percorsa dal slowPointer prima della riunione $ = x + y $

distanza percorsa dal fastPointer prima della riunione $ = (x + y + z) + y $ = X + 2y + z

Da fastPointer viaggia con doppia la velocità di slowPointer e Ora è costante sia quando la portata del punto di incontro. Quindi, utilizzando la velocità semplice, il tempo e la distanza relazione (slowPointer viaggiato 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 dell'inizio della lista collegata, e rendendo sia slowPointer e fastPointer spostare un nodo alla volta, hanno entrambi stessa distanza di copertura .

Si raggiungerà nel punto in cui i ciclo inizia nella lista collegata.

Answer 3

Ho visto la risposta accettata come prova anche altrove. Tuttavia, mentre la sua facile Grok, non è corretto. Che si rivela è

$ x = z $ (che è ovviamente sbagliato, e il diagramma solo rende plausibile dovuto al modo in cui è abbozzato).

Che cosa si vuole veramente dimostrare è (utilizzando le stesse variabili, come descritto nello schema nella risposta accettata sopra):

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

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

così, quello che vogliamo dimostrare è:

$ z = x \ mod \ L $

O che z è congruente a x (modulo L)

Dopo la prova ha più senso per me:

Punto di incontro, $ M = x + y $

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

$ x + y = kL $

$ x = KL - y $

L'equazione di cui sopra dimostra che $ x $ è uguale a un multiplo della lunghezza del ciclo, $ L $ meno $ y $. Quindi, se il puntatore si avvia velocemente al punto di incontro, $ M $ oa $ x + y $, allora finirà all'inizio del ciclo.