Floyd ' s Zykluserkennungsalgorithmus | Bestimmen des Startpunkts des Zyklus

Sie können sich auf „Erkennen des Starts einer Schleife in einer einfach verknüpften Liste“ , hier ist ein Auszug:

Von slowPointer zurückgelegte Strecke, bevor $ = x + y $

Zurückgelegte Strecke von fastPointer vor dem Treffen mit $ = (x + y + z) + y = x + 2y + z $

Da fastPointer mit double die Geschwindigkeit von slowPointer und Zeit ist konstant für beide, wenn sie den Treffpunkt erreichen. Verwenden Sie also eine einfache Geschwindigkeits-, Zeit- und Entfernungsrelation (slowPointer legte die halbe Strecke zurück):

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

Verschieben Sie daher slowPointer zum Anfang der verknüpften Liste und machen Sie beide slowPointer und fastPointer, um jeweils einen Knoten zu verschieben. Beide müssen dieselbe Entfernung zurücklegen .

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

Kommentare

• Hier haben Sie angenommen, dass sie sich nach einer Umdrehung treffen. Es kann Fälle geben (in denen der Zyklus klein ist), in denen sie sich nach einer bestimmten Anzahl treffen können. von Rotationen.
• @JotWaraich das Bild ist nicht für alle Fälle repräsentativ; Die Logik gilt jedoch immer noch.
• Dies ist die direkteste Antwort zu diesem Algorithmus im gesamten Internet.
• Ich ‚ bin nicht sehr sicher wenn dieser Beweis richtig ist. Die vom langsamen Zeiger zurückgelegte Entfernung sollte (x + (y + z) * α + y) betragen, und die vom schnellen Zeiger zurückgelegte Entfernung sollte (x + (y + z) * β + y) betragen, wobei α und β die Zahl sind von Zyklen, die vom langsamen und schnellen Zeiger durchlaufen werden. Der Beweis scheint mit diesem Zusatz zu scheitern.
• @ hashcode55 Ja, ich stimme Ihnen zu. Dies ist mir nicht klar.

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

$ x = z $ (was offensichtlich falsch ist und das Diagramm es aufgrund der Art und Weise, wie es skizziert ist, nur plausibel erscheinen lässt).

Was Sie wirklich wollen zu beweisen ist (unter Verwendung der gleichen Variablen wie im Diagramm in der oben akzeptierten Antwort beschrieben):

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

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

. Wir möchten also Folgendes beweisen:

$ z = x \ mod \ L $

Oder dass z zu x kongruent ist (Modulo L)

Der folgende Beweis ist für mich sinnvoller:

Treffpunkt, $ M = x + y $

$ 2 (x + y) = M + kL $, wobei $ k $ eine Konstante ist.Grundsätzlich beträgt die vom schnellen 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 $ dasselbe ist wie ein Vielfaches der Schleifenlänge, $ L $ minus $ y $. Wenn der schnelle Zeiger also am Treffpunkt $ M $ oder bei $ x + y $ beginnt, endet er am Anfang der Schleife.

Kommentare

• Ich ‚ weiß nicht, warum diese Antwort unterschätzt wird. Dies scheint der formalste Beweis zu sein.
• @ I8Wenn x = z falsch ist, bewegt sich die Logik beim Zurückbewegen des schnellen Zeigers zum Startpunkt & beide Ein schneller & langsamer Zeiger zum Finden des Starts der Schleife würde ‚ nicht funktionieren. Ich verstehe nicht, was du mit x = z gemeint hast. Bitte erkläre, wie das ist.
• @divine x = z ist falsch, weil es impliziert, dass beide gleich sind, aber es ist akzeptabel, eine sehr lange Zeit zu haben. “ Schwanz “(großes x) und ein sehr kleiner Kreis (kleines z). Mit dem Modulo, das wir formal korrekt sind, wollen wir nur beweisen, dass x% L == z, mit anderen Worten, der Zeiger, der sich im Kreis bewegt und darauf wartet, sich dem anderen anzuschließen, so viele Schleifen machen kann, wie er will, solange Die letzten Schritte (dh der Rest nach dem Schleifen) führen zum Beginn des Kreises.
• das ist großartig !!
• Für diejenigen unter Ihnen, die noch nicht ‚ verstehe nicht, warum x = k * L – y zu z = x mod L führt. Von x = k * L – y — > x = (k – 1) * L + L – y und dann können Sie jetzt sagen, dass L – y z sein muss. Jetzt erhalten Sie x = (k – 1) * L + z

Angenommen, es gibt $ l $ -Elemente vor dem Start der Schleife und $ n $ -Elemente in der Schleife. Und $ e_l $ ist das erste Element der Schleife, das beim Durchlaufen der verknüpften Liste angezeigt wird. Wenn wir “ sagen, tritt ein Element $ x $ vor $ e $ „, das heißt, wir können dieses Element erreichen, indem wir $ x $ Schritte von $ e $ .

Wenn Tr (Schildkröte) nun $ e_l $ nach $ l $ -Iterationen, sagen wir, Hr (Hare) ist $ x $ Schritte vor $ e_l $ . Da Hr bis dahin insgesamt $ 2l $ Schritte ausgeführt hat ( $ l $ Schritte vor der Schleife), Also:

$ x = l \ bmod n $ .

In jeder zukünftigen Iteration werden Tr und Hr um fortschreiten 1 bzw. 2 Schritte, und so erhöht jede Iteration ihre “ Lücke “ um 1. Sie treffen sich also nach $ nx $ weitere Iterationen, wenn ihre Lücke zu $ x + (nx) = n $ wird. Das Besprechungselement $ M $ ist also $ nx $ Schritte vor $ e_l $ . Wenn Sie also $ x $ Schritte nach $ M $ ausführen, gelangen Sie wieder zu $ e_l $ . Unser Ziel ist es, $ e_l $ zu finden.

Wenn wir also mit einer Referenz Tr bei beginnen $ M $ und eine weitere Referenz Hr am Anfang der verknüpften Liste und führen Sie beide Schritt für Schritt nach $ l $ -Iterationen fort :

• Hr ist $ l $ Schritte vor dem Kopf, der $ e_l $ .

• Tr sind $ (l \ bmod n) $ Schritte vor $ M $ , dh $ x $ vor $ M $ , das ist $ e_l $ .

Also, wenn sie haben erfüllt, wissen wir, dass es $ e_l $ ist.

Siehe diesen Artikel für Details. Dort finden Sie eine leicht modifizierte Methode, um $ e_l $ zu finden.

Ich denke auch, dass die Top-Antwort unvollständig ist, und obwohl einige der anderen Erklärungen auch gut sind, habe ich eine andere Version ohne MOD, um dasselbe anzuzeigen, was für manche Leute vielleicht einfacher ist.

Das gleiche Setup, betrachten Sie $ X \ ge 0 $ als der Abstand vor der Schleife, $ N \ le \ text {Größe der Liste} $ ist die Größe der Schleife (die Menge $ y + z $ im Bild) und der Treffpunkt ist $ Y $ in der Schleife. Beachten Sie an dieser Stelle, dass wir auch $ X + Y \ le N $ erstellt haben.

Nun bewegt sich der langsame Zeiger $ X + Y + pN $ , wobei $ p $ eine beliebige Ganzzahl ist. Dann reiste der schnelle Zeiger $ 2 (X + Y + pN) $ .

Nun behaupten , dass sie sich bei $ Y $ treffen.

Beweis :

Wenn sie sich bei $ Y $ treffen, muss es sein dass der schnellere Zeiger genau $ qN $ mehr als der langsamere Zeiger reiste, wobei $ q $ eine ganze Zahl ist . Dann haben wir: $$ \ text {Distanzdifferenz =} 2 (X + Y + pN) – (X + Y + pN) = X + Y + pN $$ . Aber wir hatten $ Y $ als willkürlichen Treffpunkt in der Schleife, also können wir einfach $ X + Y = N wählen $ , das als $ X + Y \ le N $ gilt.

Daher haben wir: $$ X + Y + pN = N + pN = (p + 1) N = qN $$ was wahr ist, wenn $ p + 1 = q $ . Da sowohl $ p $ als auch $ q $ beliebige Ganzzahlen sind, können wir einfach das Minimum auswählen dass $ p = 0, q = 1 $ , was entspricht: $$ \ text {mit dem langsamen Zeiger zurückgelegte Strecke} = X + Y + pN = X + Y $$ und $$ \ text {mit dem schnellen Zeiger zurückgelegte Strecke} = (X + Y + pN) + qN = X. + Y + N $$ , sodass der schnelle Zeiger beim ersten Treffen mit dem langsamen Zeiger genau $ N $ mehr zurücklegte.

Die Schildkröte und der Hase sind zwei Zeiger, die mit dem Wert „oben“ in der Liste initialisiert werden. In jedem Zyklus der Schleife erhöht sich der Hase um 2 inkrementelle Gegenstände, während sich die Schildkröte um eins erhöht. Wenn der Hase zu irgendeinem Zeitpunkt dem Hasen entspricht, wurde eine Schleife erkannt. Wenn der Hase dem Ende entspricht, wird keine Schleife gefunden.

In diesem Beitrag wird dies Zeile für Zeile besser erklärt:

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