Floyd's Cycle Detection Algorithmus | Bestimmung des Startpunktes des Zyklus

Ich suche Hilfe beim Verständnis von Floyds Algorithmus zur Zykluserkennung. Ich habe die Erklärung auf Wikipedia durchgearbeitet ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare )

Ich kann sehen, wie der Algorithmus den Zyklus in O (n) -Zeit erkennt. Ich kann mir jedoch nicht vorstellen, dass der Beginn des Zyklus bestimmt werden kann, wenn sich die Schildkröten- und Hasenzeiger zum ersten Mal treffen, indem der Schildkrötenzeiger zum Start zurückbewegt wird und dann Schildkröte und Hase schrittweise nacheinander bewegt werden. Der Punkt, an dem sie sich zum ersten Mal treffen, ist der Beginn des Zyklus.

Kann jemand mit einer Erklärung helfen, die sich hoffentlich von der auf Wikipedia unterscheidet, da ich sie nicht verstehen / visualisieren kann?

Sie können sich auf "Erkennen des Starts einer Schleife in einer einfach verknüpften Liste" beziehen. Hier ist ein Auszug:

Zurückgelegte Strecke slowPointervor dem Treffen $= x+y$

fastPointer $=(x + y + z) + y$

Da fastPointerreist man mit doppelter Geschwindigkeit slowPointer, und die Zeit ist für beide konstant, wenn sie den Treffpunkt erreichen. Also mit einfachen Verhältnissen von Geschwindigkeit, Zeit und Entfernung ( slowPointerzurückgelegte halbe Strecke):

Daher durch Bewegen slowPointerder verketteten Liste zu beginnen, und beide zu machen slowPointerund fastPointereinen Knoten zu einer Zeit zu bewegen, sie haben beide dieselbe Strecke zurücklegen .

Sie erreichen den Punkt, an dem die Schleife in der verknüpften Liste beginnt.

Ich habe die akzeptierte Antwort auch an anderer Stelle als Beweis gesehen. Es ist zwar leicht zu fassen, aber falsch. Was es beweist, ist

$x = z$

Was Sie wirklich beweisen möchten, ist (unter Verwendung der gleichen Variablen wie im Diagramm in der akzeptierten Antwort oben beschrieben):

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

$(y + z)$$L$

Was wir also beweisen wollen, ist:

$z = x\ mod\ L$

Oder dass z kongruent zu x ist (Modulo L)

Der folgende Beweis macht für mich mehr Sinn:

$M = x + y$

$2(x + y) = M + kL$$k$$x + y$$L$

$x + y = kL$

$x = kL - y$

$x$$L$$y$$M$$x + y$

Ich habe die Antwort auf stackoverflow gefunden. Vielen Dank, wenn jemand nach mir gesucht hat. Und für diejenigen, die wie ich eine Erklärung wollten, lesen Sie bitte: https://stackoverflow.com/questions/3952805/proof-of-detecting-the-start-of-cycle-in-linked-list Die gewählte Antwort auf die Frage, erklärt es!