Floyds Zykluserkennungsalgorithmus | Bestimmung des Startpunkts des Zyklus

Question

Ich suche Hilfe beim Verständnis von Floyds Zykluserkennungsalgorithmus. Ich habe die Erklärung zu Wikipedia (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 mich jedoch nicht vorstellen, dass sich der Beginn des Zyklus, wenn sich die Schildkröte- und Hase -Zeiger zum ersten Mal treffen, durch die Verschiebung der Schildkrötenzeiger wieder auf den Start und dann sowohl Schildkröten- als auch Hase -Stufe nach dem anderen bewegt werden kann. Der Punkt, an dem sie sich zum ersten Mal treffen, ist der Beginn des Zyklus.

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

Answer 1

Ich fand die Antwort auf Stackoverflow. Danke, wenn jemand das für mich untersucht hat. Und für diejenigen, die mich mögen, wollten eine Erklärung, beziehen Sie sich bitte an: https://stackoverflow.com/questions/3952805/proof-lof-detecting-tartof-cycle-in-linked-list Die gewählte Antwort auf die Frage erklärt sie!

Answer 2

Sie können sich beziehen "Start einer Schleife in einzig verknüpfter Liste erkennen", Hier ist ein Auszug:

Entfernung ab slowPointer vor dem Treffen $ = x+y $

Entfernung ab fastPointer vor dem Treffen $ = (x + y + z) + y $ = x + 2y + z

Seit fastPointer reist mit doppelt die Geschwindigkeit von slowPointer, und Zeit ist konstant für beide, wenn die Treffpunkt Punkte erreicht. Also durch Verwendung einfacher Geschwindigkeit, Zeit- und Entfernungsbeziehung (slowPointer fuhr die halbe Entfernung):

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

Daher durch Bewegung slowPointer um mit der verknüpften Liste zu beginnen und beides zu machen slowPointer und fastPointer einen Knoten nach dem anderen zu bewegen, Sie haben beide gleiche Entfernung zu bedecken.

Sie erreichen an dem Punkt, an dem die Schleife in der verlinkten Liste beginnt.

Answer 3

Ich habe die akzeptierte Antwort auch anderswo als Beweis gesehen. Obwohl es leicht zu grok ist, ist es falsch. Was es beweist, ist

$ x = z $ (was offensichtlich falsch ist, und das Diagramm lässt es nur plausibel erscheinen, weil es skizziert wird).

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

$ z = x mod (y + z) $

$ (y + z) $ ist die Schleifenlänge, $ l $

Also, was wir beweisen wollen, ist:

$ z = x mod l $

Oder dass Z mit X übereinstimmt (Modulo L)

Der Beweis für mich ist sinnvoller:

Treffpunkt, $ m = x + y $

$ 2 (x + y) = m + kl $, wobei $ k $ einige konstant ist. Grundsätzlich beträgt die vom schnelle Zeiger zurückgelegte Entfernung $ x + y $ plus ein Vielfaches der Schleifenlänge $ l $

$ x + y = kl $

$ x = kl - y $

Die obige Gleichung beweist, dass $ x $ das gleiche wie ein Vielfaches der Schleifenlänge ist, $ l $ minus $ y $. Wenn also der schnelle Zeiger am Treffpunkt startet, $ m $ oder bei $ x + y $, wird er zu Beginn der Schleife enden.