Erklären Sie, wie das Finden des Zyklusstartknotens in der Zyklusverknüpfungsliste funktioniert.

161

Ich verstehe, dass das Treffen von Tortoise und Hare die Existenz einer Schleife abschließt, aber wie bringt es die Schildkröte zum Beginn der verknüpften Liste, während der Hase am Treffpunkt bleibt, gefolgt von einem Schritt nach dem anderen, damit sie sich am Anfang des Zyklus treffen?

Leidenschaftlicher Programmierer
quelle
Eine andere Erklärung: marcin-chwedczuk.github.io/…
csharpfolk
Die Menschen haben sich nicht darum gekümmert, über die ersten beiden Antworten auf diese Frage hinauszuschauen. Die dritte Antwort ist ziemlich gut.
displayName

Antworten:

80

Dies ist Floyds Algorithmus zur Zykluserkennung . Sie fragen nach der zweiten Phase des Algorithmus. Wenn Sie einen Knoten gefunden haben, der Teil eines Zyklus ist, wie findet man den Beginn des Zyklus?

Im ersten Teil von Floyds Algorithmus bewegt der Hase zwei Schritte für jeden Schritt der Schildkröte. Wenn sich Schildkröte und Hase jemals treffen, gibt es einen Zyklus, und der Treffpunkt ist Teil des Zyklus, aber nicht unbedingt der erste Knoten im Zyklus.

Wenn sich Schildkröte und Hase treffen, haben wir das kleinste i (die Anzahl der von der Schildkröte unternommenen Schritte) so gefunden, dass X i = X 2i . Es sei mu die Anzahl der Schritte, die von X 0 zum Beginn des Zyklus gelangen sollen, und Lambda die Länge des Zyklus. Dann ist i = mu + a Lambda und 2i = mu + b Lambda, wobei a und b ganze Zahlen sind, die angeben, wie oft die Schildkröte und der Hase den Zyklus durchlaufen haben. Das Subtrahieren der ersten Gleichung von der zweiten ergibt i = (ba) * Lambda, also ist i ein ganzzahliges Vielfaches von Lambda. Daher ist X i + mu = X mu . X i repräsentiert den Treffpunkt von Schildkröte und Hase. Wenn Sie die Schildkröte zurück zum Startknoten X bewegen0 , und lassen Sie die Schildkröte und den Hasen mit der gleichen Geschwindigkeit fortfahren, nach mu zusätzlichen Schritten hat die Schildkröte X mu erreicht , und der Hase hat X i + mu = X mu erreicht , so dass der zweite Treffpunkt den Beginn des bezeichnet Zyklus.

Jim Lewis
quelle
1
@ Jim Lewis Der Treffpunkt wird natürlich kein Ausgangspunkt sein, aber wie gesagt, wenn Sie einen dieser beiden Punkte an den Anfang der verknüpften Liste verschieben und beide mit derselben Geschwindigkeit verschieben, werden sie sich am Startpunkt des Zyklus treffen.
Leidenschaftlicher Programmierer
6
@ Jim Lewis Es wäre großartig, wenn Sie erklären könnten, wie sich i als Vielfaches der Schleifenlänge zu mu als Abstand zwischen dem ersten Treffpunkt und dem Beginn der Schleife ergibt.
Leidenschaftlicher Programmierer
7
@Passionate: Machen Sie mu Schritte vom Startpunkt bis zum X_muBeginn des Zyklus (per Definition von mu). Wenn Sie dann weitere Schritte ausführen, wobei i ein Vielfaches der Zykluslänge ist, landen Sie wieder beim Zyklusstart: X_mu + i= X_mu. Die Addition ist jedoch kommutativ. Dies entspricht dem Ausführen von i Schritten, um vom Start zum ersten Treffpunkt X_izu gelangen, und mu zusätzlichen Schritten, um zum X_muBeginn des Zyklus zurückzukehren.
Jim Lewis
2
@ankur: Der Treffpunkt ist X_i, und wir haben gezeigt (dritter Absatz in meiner Antwort), dass ich ein Vielfaches der Schleifenlänge sein muss. Nach mu weiteren Schritten nach dem Treffpunkt befinden Sie sich nun bei X_ (i + mu). Wir haben jedoch gezeigt, dass X_ (i + mu) = X_ (mu + i) = X_mu aufgrund dieser besonderen Eigenschaft von i, sodass mu Schritte am Treffpunkt vorbei zu X_mu führen müssen, dem Beginn des Zyklus. Grundsätzlich modulare Arithmetik plus die kommutative Eigenschaft der Addition.
Jim Lewis
28
Ich denke, es gibt ein kleines Problem in Ihrem Beweis. Da sich der Treffpunkt ian einem bestimmten Punkt des Zyklus befindet, sollte die Gleichung lauten i = mu + k + a*lambdaund 2i = mu + k + b*lambdawo kist die Anzahl der Schritte vom Zyklusstart bis zum Treffpunkt? Das Subtrahieren beider Gleichungen ergibt jedoch das gleiche Ergebnis.
Ivan Z. Siu
336

Lassen Sie mich versuchen, den unter http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare bereitgestellten Zykluserkennungsalgorithmus in meinen eigenen Worten zu erläutern .

Zeichnung

Wie es funktioniert

Lassen Sie uns eine Schildkröte und einen Hasen (Name der Zeiger) mit einem Zyklus auf den Anfang der Liste zeigen, wie in der obigen Abbildung.

Nehmen wir an, wenn wir die Schildkröte Schritt für Schritt bewegen und 2 Schritte gleichzeitig Hase, treffen sie sich schließlich zu einem bestimmten Zeitpunkt. Lassen Sie uns zeigen, dass zuallererst diese Hypothese wahr ist.

Die Abbildung zeigt eine Liste mit einem Zyklus. Der Zyklus hat eine Länge von nund wir sind zunächst mSchritte vom Zyklus entfernt. Nehmen wir auch an, der Treffpunkt ist nur kwenige Schritte vom Beginn des Zyklus entfernt und Schildkröte und Hase treffen sich, wenn die Schildkröte iinsgesamt Schritte unternommen hat. (Hare hätte bis dahin 2iinsgesamt Schritte unternommen.)

Die folgenden 2 Bedingungen müssen gelten:

1) i = m + p * n + k

2) 2i = m + q * n + k

Der erste sagt, dass die Schildkröte iSchritte bewegt und in diesen iSchritten zuerst zum Zyklus gelangt. Dann durchläuft es die Zykluszeiten pfür eine positive Zahl p. Schließlich geht es über kmehr Knoten, bis es auf Hasen trifft.

Ähnliches gilt für Hasen. Es bewegt 2iSchritte und in diesen 2iSchritten gelangt es zuerst zum Zyklus. Dann durchläuft es die Zykluszeiten qfür eine positive Zahl q. Schließlich geht es über kweitere Knoten, bis es auf Schildkröte trifft.

Da Hase mit der doppelten Geschwindigkeit der Schildkröte reist und die Zeit für beide konstant ist, wenn sie den Treffpunkt erreichen.

Durch die Verwendung einer einfachen Geschwindigkeits-, Zeit- und Entfernungsbeziehung

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

Unter m, n, k, p, q sind die ersten beiden Eigenschaften der gegebenen Liste. Wenn wir zeigen können, dass es mindestens einen Satz von Werten für k, q, p gibt, der diese Gleichung wahr macht, zeigen wir, dass die Hypothese korrekt ist.

Ein solcher Lösungssatz lautet wie folgt:

p = 0

q = m

k = m n - m

Wir können überprüfen, ob diese Werte wie folgt funktionieren:

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn.

Für dieses Set iist

i = m + p n + k

=> m + 0 * n + mn - m = mn.

Natürlich sollten Sie sehen, dass dies nicht unbedingt das kleinstmögliche ist. Mit anderen Worten, Schildkröte und Hase haben sich vielleicht schon oft getroffen. Da wir jedoch zeigen, dass sie sich mindestens einmal treffen, können wir sagen, dass die Hypothese richtig ist. Sie müssten sich also treffen, wenn wir einen von ihnen um einen Schritt und den anderen um zwei Schritte gleichzeitig bewegen würden.

Nun können wir zum zweiten Teil des Algorithmus übergehen, in dem der Beginn des Zyklus ermittelt wird.

Zyklusbeginn

Sobald sich Schildkröte und Hase treffen, setzen wir die Schildkröte wieder an den Anfang der Liste und halten den Hasen dort, wo sie sich getroffen haben (was k Schritte vom Zyklusbeginn entfernt ist).

Die Hypothese ist, dass, wenn wir sie mit der gleichen Geschwindigkeit bewegen lassen (1 Schritt für beide), das erste Mal, dass sie sich wieder treffen, der Zyklus beginnt.

Lassen Sie uns diese Hypothese beweisen.

Nehmen wir zunächst an, ein Orakel sagt uns, was m ist.

Wenn wir sie dann m + k Schritte bewegen lassen, müsste die Schildkröte an dem Punkt ankommen, an dem sie sich ursprünglich getroffen haben (k Schritte vom Zyklusbeginn entfernt - siehe Abbildung).

Zuvor haben wir das gezeigt m + k = (q - 2p) n.

Da m + k Schritte ein Vielfaches der Zykluslänge n sind, würde Hase in der Zwischenzeit die Zykluszeiten (q-2p) durchlaufen und zum gleichen Punkt zurückkehren (k Schritte vom Zyklusbeginn entfernt).

Anstatt sie m + k Schritte bewegen zu lassen, würde die Schildkröte am Zyklusbeginn ankommen, wenn wir sie nur m Schritte bewegen lassen. Hase wäre k Schritte vor dem Abschluss von (q-2p) Rotationen. Da es k Schritte vor dem Zyklusbeginn begann, musste der Hase am Zyklusbeginn ankommen.

Dies erklärt, dass sie sich zum ersten Mal nach einigen Schritten zu Beginn des Zyklus treffen müssten (zum ersten Mal, weil die Schildkröte erst nach m Schritten im Zyklus ankam und nie einen Hasen sehen konnte, der sich bereits darin befand der Kreislauf).

Jetzt wissen wir, dass die Anzahl der Schritte, die wir benötigen, um sie zu bewegen, bis sie sich treffen, die Entfernung vom Anfang der Liste bis zum Beginn des Zyklus ist, m. Natürlich muss der Algorithmus nicht wissen, was m ist. Es bewegt nur Schildkröte und Hase Schritt für Schritt, bis sie sich treffen. Der Treffpunkt muss der Zyklusstart sein und die Anzahl der Schritte muss der Abstand (m) zum Zyklusbeginn sein. Angenommen, wir kennen die Länge der Liste, können wir auch die Länge des Zyklus des Subtrahierens von m von der Listenlänge berechnen.

CEGRD
quelle
1
Ich denke nicht, dass es wahr ist, dass wenn sie sich treffen, dies der Ausgangspunkt ist, siehe Kommentar unten: stackoverflow.com/a/19209858/1744146 <br> Bitte lassen Sie mich wissen, wenn ich falsch
liege
Der erste Teil der Erklärung ist einwandfrei. Aber der zweite Teil hat meines Wissens einen Fehler. Sie nehmen an, dass "ein Orakel m sagt", aber wenn m bekannt ist, haben Sie bereits den Beginn des Zyklus. Wie können Sie einfach die Antwort annehmen, wenn Sie nie wissen, wo der Beginn des Zyklus ist? Lass es mich wissen, bitte.
Gopichand
1
@ Gopichand Lies den letzten Absatz noch einmal ... du nimmst einfach an, dass es einige m gibt (wenn bereits bewiesen ist, dass es einen Zyklus gibt) .. aber du kennst den Wert von m nicht
Srinath
2
Das ist wirklich eine fantastische Erklärung. Dies ist derzeit wahrscheinlich die beste Erklärung im gesamten Internet.
Arlene Batada
2
Ihre Gleichung m + k = (q - 2p) nkann weiter vereinfacht werden m + k = q*n. Dies liegt daran, dass die Anzahl der Schleifen, die Schildkröten nehmen, immer Null ist, da der Hase die Schildkröte niemals überholen kann, ohne sie zu treffen. Denk darüber nach.
Arpit Jain
124

Verweisen Sie auf dieses Bild:

Geben Sie hier die Bildbeschreibung ein

Von slowPointer vor dem Treffen zurückgelegte Strecke = x + y

Mit fastPointer zurückgelegte Strecke vor dem Treffen = (x + y + z) + y = x + 2y + z

Da fastPointer mit der doppelten Geschwindigkeit von slowPointer fährt und die Zeit für beide konstant ist, wenn sie den Treffpunkt erreichen.

Durch Verwendung der einfachen Geschwindigkeits-, Zeit- und Entfernungsrelation 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z

Wenn Sie also slowPointer an den Anfang der verknüpften Liste verschieben und slowPointer und fastPointer jeweils einen Knoten verschieben, müssen beide dieselbe Entfernung zurücklegen .

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

Atul Yadav
quelle
10
Dies berücksichtigt nicht den Fall, dass fastPointer den Zyklus n-mal durchläuft, bevor slowPointer in den Zyklus eintritt. Verwenden Sie l, um die Länge des Zyklus anzugeben. Mit fastPointer zurückgelegte Strecke vor dem Treffen = (x + y + z) + y = x + 2y + nl + z. Und die resultierende Beziehung ist x = nl + z.
Jingguo Yao
@JingguoYao: Hier ist die Erklärung für diesen Fall.
DisplayName
2
Dieses Diagramm ist zu einfach. Der schnelle Zeiger kann sich viele Male durch den Zyklus bewegen, bevor der langsame Zeiger ihn erreicht.
Warren MacEvoy
70

Die einfache und unterbewertete Antwort des alten Mönchs erklärt das Finden des Zyklus, wenn der schnelle Läufer nur einen einzigen vollständigen Zyklus abschließt. In dieser Antwort erkläre ich den Fall, in dem ein schneller Läufer die Schleife mehrmals ausgeführt hat, bevor der langsame Läufer in die Schleife eintritt.


Verwenden des gleichen Bildes:Geben Sie hier die Bildbeschreibung ein

Nehmen wir an, der schnelle Läufer hat die Schleife m Mal gelaufen, bevor er sich langsam und schnell trifft. Dies bedeutet, dass:

  • Langsam zurückgelegte Strecke: x + y
  • Die Strecke läuft schnell vorbei: x + m (y + z) + y, dh extra y, wo sie sich treffen

Da schnell mit der doppelten Geschwindigkeit von langsam läuft und dass sie zur gleichen Zeit gelaufen sind, bedeutet dies, dass wir die Strecke schnell fahren, wenn wir die zurückgelegte Strecke verdoppeln. So,

  • 2 (x + y) = x + m (y + z) + y

Das Auflösen nach x ergibt,

x = (m - 1) (y + z) + z

Im realen Szenario würde dies bedeuten, dass x = (m - 1) vollständige Schleifenläufe + ein zusätzlicher Abstand z .

Wenn wir also einen Zeiger an den Anfang der Liste setzen und den anderen am Treffpunkt belassen, führt das Verschieben mit der gleichen Geschwindigkeit dazu, dass der In-Loop-Zeiger m - 1 Läufe der Schleife abschließt und dann den anderen trifft Zeiger direkt am Schleifenanfang.

Anzeigename
quelle
7
Ein Zweifel ... wie ist garantiert, dass sich langsam und schnell treffen, bevor langsam mehr als einen Zyklus dauert?
Siraj
4
@siraj: Langsam läuft nicht in Zyklen, schnell würde, da es schneller als langsam läuft und vorher in die Schleife eintritt. Und es ist garantiert, dass sie sich treffen würden. Wenn langsam bei j + 1 und schnell bei j ist, treffen sie sich jetzt bei j + 2. Und wenn langsam bei j und schnell bei j + 1 ist, bedeutet dies, dass sie sich bereits bei j - 1 getroffen haben.
displayName
4
Die Mathematik funktioniert immer noch, wenn die langsame Schleife umgeht: x + (y + z) m + y = 2 (x + (y + z) n + y), wobei n die Anzahl der langsamen Schleifen ist, bevor sie sich treffen. Dies löst sich zu (m-2n-1) (y + z) + z = x. Was bedeutet, dass Sie am Treffpunkt beginnen, (m-2n-1) mal herumgehen, wieder am Treffpunkt sind und dann z gehen, Sie am Anfang der Schleife sind. Und um dies zu tun, ist es dasselbe wie am Kopfknoten zu beginnen und x Knoten zu gehen.
Mayas_Mom
1
@mayas_mom: Mathe mag funktionieren, aber langsam wird niemals in der Lage sein, die Schleife zu umgehen. Es wird immer entweder gleich zu Beginn oder irgendwo auf halbem Weg gefangen.
DisplayName
4
x = (m - 1) (y + z) + z Dies kann verallgemeinert werden, da die Schleifenlänge y + z ist und da nur die Position betroffen ist. Also x = ((m - 1) (y + z))% (y + z)) + z Was ist effektiv x = z;
Anhshul Garg
10

Es ist sehr sehr einfach. Sie können in Bezug auf die relative Geschwindigkeit denken. Wenn das Kaninchen zwei Knoten bewegt und die Schildkröte einen Knoten bewegt, bewegt das Kaninchen im Vergleich zur Schildkröte einen Knoten (nehmen Sie an, dass die Schildkröte in Ruhe ist). Wenn wir also einen Knoten in der zirkular verknüpften Liste verschieben, werden wir uns an diesem Punkt sicher wieder treffen.

Nachdem der verbundene Punkt in der kreisförmigen verknüpften Liste gefunden wurde, reduziert sich das Problem nun darauf, den Schnittpunkt zweier Probleme mit verknüpften Listen zu finden.

murali krish
quelle
8

Abbildung 1

Zum Zeitpunkt der ersten Kollision bewegte die Schildkröte m + k Schritte wie oben gezeigt. Der Hase bewegt sich doppelt so schnell wie die Schildkröte, was bedeutet, dass sich der Hase 2 (m + k) Schritte bewegt hat . Aus diesen einfachen Fakten können wir das folgende Diagramm ableiten.

Abbildung 1

An diesem Punkt bewegen wir die Schildkröte zurück zum Start und erklären, dass sich sowohl Hase als auch Schildkröte Schritt für Schritt bewegen müssen. Per Definition befindet sich die Schildkröte nach m Schritten am Anfang des Zyklus. Wo wird Hase sein?

Hase wird auch am Anfang des Zyklus sein. Dies geht aus der zweiten Grafik hervor: Als die Schildkröte zum Start zurückgebracht wurde, war der Hase k Schritte in seinem letzten Zyklus. Nach m Schritten hat der Hase einen weiteren Zyklus abgeschlossen und ist mit der Schildkröte zusammengestoßen.

skedastik
quelle
@WarrenMacEvoy Zu keinem Zeitpunkt habe ich vorgeschlagen, dass sie sich am Startpunkt treffen. Sie treffen sich zu Beginn des Zyklus wieder, wie die Zahlen deutlich zeigen.
Skedastik
5

Ansatz:

Es gibt zwei Hinweise:

  • Ein langsamer Zeiger, der jeweils einen Knoten bewegt.
  • Ein schneller Zeiger, der zwei Knoten gleichzeitig bewegt.

Wenn sich die beiden Zeiger treffen, zeigt dies, dass es eine Schleife gibt. Sobald sie sich getroffen haben, zeigt einer der Knoten auf den Kopf und lässt dann jeweils einen Knoten nach dem anderen fortfahren. Sie treffen sich zu Beginn der Runde.

Begründung: Wenn zwei Personen eine Kreisbahn hinuntergehen, eine mit der doppelten Geschwindigkeit der anderen, wo treffen sie sich? Genau dort, wo sie angefangen haben.

Angenommen, der schnelle Läufer hat in einer Schrittrunde einen Vorsprung von kSchritten n. wo werden sie sich treffen Genau bei n-kSchritten. Wenn der langsame Läufer (n-k)Schritte zurückgelegt hat, hätte der schnelle Läufer k+2(n-k)Schritte zurückgelegt. ( dh k+2n-2kSchritte dh 2n-kSchritte ). dh (n-k)Schritte (Der Weg ist kreisförmig und wir sind nicht besorgt über die Anzahl der Runden, nach denen sie sich treffen; wir sind nur an der Position interessiert, an der sie sich treffen).

Wie kam der schnelle Läufer überhaupt zum Vorsprung k? Weil der langsame Läufer so viele Schritte brauchte, um den Start der Schleife zu erreichen. Der Beginn der Schleife ist also k Schritte vom Kopfknoten entfernt.

Hinweis: Der Knoten, an dem sich beide Zeiger getroffen haben, ist nur kwenige Schritte vom Beginn der Schleife entfernt (innerhalb der Schleife), und der Kopfknoten ist auch nur kwenige Schritte vom Beginn der Schleife entfernt. Wenn wir also einen Zeiger haben, der mit gleichem Tempo von 1 Schritt von diesen Knoten vorrückt, treffen sie sich am Anfang der Schleife.

Ich glaube es ist einfach. Bitte lassen Sie mich wissen, wenn ein Teil nicht eindeutig ist.

Aadith Ramia
quelle
4
Bitte posten Sie die vollständige Antwort hier anstatt nur einen Link, der in Zukunft brechen könnte
Leeor
4

Okay, nehmen wir an, der Hase und die Schildkröte treffen sich an einem Punkt, der k Schritte vom Beginn des Zyklus entfernt ist. Die Anzahl der Schritte vor Beginn des Zyklus beträgt mu und die Länge des Zyklus ist L.

Also jetzt am Treffpunkt ->

Von Schildkröte zurückgelegte Strecke = mu + a * L + k - Gleichung 1

(Schritte zum Erreichen des Zyklusbeginns + Schritte zum Abdecken von 'a'-Iterationen des Zyklus + k Schritte vom Beginn des Zyklus) (wobei a eine positive Konstante ist)

Vom Hasen zurückgelegte Strecke = mu + b * L + k - Gleichung 2

(Schritte zum Erreichen des Zyklusbeginns + Schritte zum Abdecken von 'b'-Iterationen des Zyklus + k Schritte vom Beginn des Zyklus) (wobei b eine positive Konstante ist und b> = a)

Die vom Hasen zurückgelegte zusätzliche Distanz ist also = Gleichung 2 - Gleichung 1 = (ba) * L.

Bitte beachten Sie, dass dieser Abstand auch dem Abstand der Schildkröte vom Startpunkt entspricht, da sich der Hase zweimal schneller bewegt als die Schildkröte. Dies kann mit 'mu + k' gleichgesetzt werden, was auch die Entfernung des Treffpunkts vom Anfang ist, wenn wir nicht mehrere Durchläufe des Zyklus einbeziehen.

Somit ist mu + k = (ba) * L.

Meine Schritte von diesem Punkt würden also zum Beginn des Zyklus zurückführen (da bereits k Schritte vom Beginn des Zyklus unternommen wurden, um den Treffpunkt zu erreichen). Dies kann im selben Zyklus oder in einem der nachfolgenden Zyklen geschehen. Wenn wir also die Schildkröte an den Anfang der verknüpften Liste bringen, werden mu Schritte benötigt, um den Startpunkt des Zyklus zu erreichen, und der Hase würde mu Schritte unternehmen, um auch den Beginn des Zyklus zu erreichen, und somit würden sich beide am treffen Startpunkt des Zyklus.

PS Ehrlich gesagt hatte ich die gleiche Frage wie das Originalplakat im Kopf und las die erste Antwort. Sie haben ein paar Dinge geklärt, aber ich konnte das Endergebnis nicht klar erreichen und habe versucht, es auf meine eigene Art und Weise zu tun fand es leichter zu verstehen.

Prateek Jassal
quelle
Sie treffen sich normalerweise nicht zu Beginn des Zyklus
Warren MacEvoy
3

Geben Sie hier die Bildbeschreibung ein Bildnachweis

Anrufentfernung Die Anzahl der Verbindungen, denen ein Zeiger folgt, und die Zeit die Anzahl der Iterationen, die der Algorithmus benötigt, um den langsamen Zeiger um eine Verbindung und den schnellen Zeiger um zwei Verbindungen zu bewegen. Vor einem Zyklus der Länge C befinden sich N Knoten, die mit dem Zyklusversatz k = 0 bis C-1 gekennzeichnet sind.

Um den Beginn des Zyklus zu erreichen, benötigt langsam N Zeit und Distanz. Dies bedeutet, dass schnell N Distanz im Zyklus benötigt (N um dorthin zu gelangen, N um sich zu drehen). Zum Zeitpunkt N ist also langsam beim Zyklusversatz k = 0 und schnell beim Zyklusversatz k = N mod C.

Wenn N mod C Null ist, stimmen langsam und schnell überein und der Zyklus wird zum Zeitpunkt N und der Zyklusposition k = 0 gefunden.

Wenn N mod C nicht Null ist, muss schnell jetzt langsam aufholen, was zum Zeitpunkt N C- (N mod C) Abstand im Zyklus ist.

Da sich schnell für jede langsame 1 bewegt und die Entfernung bei jeder Iteration um 1 verringert, dauert dies genauso viel zusätzliche Zeit wie die Entfernung zwischen schnell und langsam zum Zeitpunkt N, die C- (N mod C) ist. Da sich Slow von Offset 0 bewegt, ist dies auch der Offset, an dem sie sich treffen.

Wenn also N mod C Null ist, stoppt die Phase 1 nach N Iterationen zu Beginn des Zyklus. Andernfalls stoppt Phase 1 nach N + C- (N mod C) Iterationen am Offset C- (N mod C) in den Zyklus.

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

Ok, also Phase 2: langsam braucht N weitere Schritte, um zum Zyklus zu gelangen. An diesem Punkt liegt schnell (jetzt 1 pro Zeitschritt) bei (C- (N mod C) + N) mod C = 0. Sie treffen sich also zu Beginn des Zyklus nach Phase 2.

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

Der Vollständigkeit halber berechnet Phase 3 die Zykluslänge, indem sie sich noch einmal durch den Zyklus bewegt:

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}
Warren MacEvoy
quelle
Link zu Google Doc, um den Algorithmus zu simulieren: docs.google.com/spreadsheets/d/…
Warren MacEvoy
1
Beachten Sie, dass bei N <= C die Iteration nach C-Iterationen stoppt. In jedem Fall muss es in weniger als N + C Schritten anhalten und es ist unwahrscheinlich, dass es zu Beginn des Zyklus stoppt.
Warren MacEvoy
2

Reduzieren Sie das Problem auf ein Schleifenproblem und kehren Sie dann zum ursprünglichen Problem zurück

Ich finde die folgende Erklärung intuitiver.

  1. Nehmen Sie zwei Zeiger ( 1 = Schildkröte und 2 = Hase), die vom Kopf ausgehen ( O ), 1 hat eine Schrittlänge von 1 , 2 hat eine Schrittlänge von 2 . Denken Sie an den Moment, in dem 1 den Startknoten dieses Zyklus erreicht ( A ).

    Wir möchten die folgende Frage beantworten: "Wo ist 2, wenn 1 in A ist?" .

    Also OA = aist eine natürliche Zahl ( a >= 0). Es kann aber folgendermaßen geschrieben werden : a = k*n + b, wobei a, k, n, b are natural numbers:

    • n = die Zykluslänge
    • k >= 0 = konstant
    • 0 <= b <= n-1

    Es bedeutet das b = a % n.

    ZB: wenn a = 20und n = 8=> k = 2und b = 4weil 20 = 2*8 + 4.

    Die von 1 zurückgelegte Strecke beträgt d = OA = a = k*n + b. Aber gleichzeitig 2 Cover D = 2*d = d + d = OA + d = OA + k*n + b. Dies bedeutet, dass wenn 2 in A ist, es abdecken muss k*n + b. Wie Sie sehen können, kist die Anzahl der Runden, aber nach diesen Runden 2 wird b von A. Bisher fanden wir , wo 2 ist , wenn 1 in A. Nennen wir diesen Punkt ist B, wo AB = b.

    Geben Sie hier die Bildbeschreibung ein

  2. Jetzt reduzieren wir das Problem auf einen Kreis. Die Frage ist "Wo ist der Treffpunkt?" . Wo ist das C ?

    Geben Sie hier die Bildbeschreibung ein

    In jedem Schritt verringert 2 den Abstand von 1 mit 1(sagen wir Meter), weil 1 mit 2 weiter von 2 entfernt ist1 , gleichzeitig aber 2 um 1 näher an 1 heranrückt 2.

    Der Schnittpunkt ist also, wenn der Abstand zwischen 1 und 2 Null ist. Dies bedeutet, dass 2 den n - bAbstand verringert . Um dies zu erreichen, 1 machen n - bSchritte, während 2 machen 2*(n - b)Schritte.

    Der Schnittpunkt ist also n - bweit von A entfernt (im Uhrzeigersinn), da dies die Entfernung ist, die 1 zurücklegt, bis er auf 2 trifft . => der Abstand zwischen C und A ist CA = b, weil AC = AB + BC = n - bund CA = n - AC. Denken Sie nicht, dass AC = CAdie ACEntfernung keine triviale mathematische Entfernung ist, sondern die Anzahl der Schritte zwischen A und C (wobei A der Startpunkt und C der Endpunkt ist).

  3. Kehren wir nun zum ursprünglichen Schema zurück.

    Wir wissen das a = k*n + bund CA = b.

    Wir können 2 neue Zeiger 1 ' und 1' 'nehmen , wobei 1' vom Kopf ( O ) und 1 '' vom Schnittpunkt ( C ) beginnt .

    Während 1' geht von O nach A , 1 ‚‘ geht von C zu A und weiter bis zum Ende kRunden. So ist der Schnittpunkt A .

    Geben Sie hier die Bildbeschreibung ein

    Geben Sie hier die Bildbeschreibung ein

ROMANIA_engineer
quelle
2

Geben Sie hier die Bildbeschreibung ein

Wenn sich die Zeiger an einem Punkt P treffen, wie in der Figur gezeigt, ist der Abstand Z + Y Punkt P und X + Y ist auch Punkt P, was Z = X bedeutet. Aus diesem Grund bewegt man einen Zeiger von P und einen anderen vom Start (S) bis zu seiner Begegnung, was bedeutet, dass eine gleiche Entfernung (Z oder X) zum selben Punkt M (Entfernung Z von P und X von S) bewegt wird Beginn der Schleife. Einfach!

user9639921
quelle
1

Bei all den obigen Analysen habe ich versucht, eine kurze Analyse und ein Beispiel zu verfassen, um die Mathematik zu erklären, die alle anderen zu erklären versuchten. Auf geht's!

Analyse:

Wenn wir zwei Zeiger haben, einen schneller als den anderen, und sie zusammen verschieben, treffen sie sich schließlich wieder, um einen Zyklus anzuzeigen, oder null, um keinen Zyklus anzuzeigen.

Um den Startpunkt des Zyklus zu finden, lassen Sie ...

  1. m sei der Abstand vom Kopf zum Beginn des Zyklus;

  2. d die Anzahl der Knoten im Zyklus sein;

  3. p1 sei die Geschwindigkeit des langsameren Zeigers;

  4. p2sei die Geschwindigkeit des schnelleren Zeigers, z. 2 bedeutet Schritte durch zwei Knoten gleichzeitig.

    Beachten Sie die folgenden Iterationen:

 m = 0, d = 10:
 p1 = 1:  0  1  2  3  4  5  6  7  8  9 10 // 0 would the start of the cycle
 p2 = 2:  0  2  4  6  8 10 12 14 16 18 20

 m = 1, d = 10:
 p1 = 1: -1  0  1  2  3  4  5  6  7  8  9
 p2 = 2: -1  1  3  5  7  9 11 13 15 17 19

 m = 2, d = 10:
 p1 = 1: -2 -1  0  1  2  3  4  5  6  7  8
 p2 = 2: -2  0  2  4  6  8 10 12 14 16 18

Anhand der obigen Beispieldaten können wir leicht erkennen, dass die schnelleren und langsameren Zeiger, wenn sie sich treffen, nur wenige mSchritte vom Beginn des Zyklus entfernt sind. Um dies zu lösen, setzen Sie den schnelleren Zeiger wieder auf den Kopf und stellen Sie seine Geschwindigkeit auf die Geschwindigkeit des langsameren Zeigers ein. Wenn sie sich wieder treffen, ist der Knoten der Beginn des Zyklus.

Steve
quelle
1

sagen wir,

N[0] is the node of start of the loop, 
m is the number of steps from beginning to N[0].

Wir haben 2 Zeiger A und B, A läuft mit 1x Geschwindigkeit, B mit 2x Geschwindigkeit, beide beginnen am Anfang.

Wenn A N [0] erreicht, sollte B bereits in N [m] sein. (Hinweis: A verwendet m Schritte, um N [0] zu erreichen, und B sollte m Schritte weiter sein.)

Dann führt A k weitere Schritte aus, um mit B zu kollidieren, dh A ist bei N [k], B ist bei N [m + 2k] (Hinweis: B sollte für 2k Schritte ab N [m] ausgeführt werden)

Eine Kollision B bei N [k] bzw. N [m + 2k] bedeutet k = m + 2k, also k = -m

Um von N [k] zu N [0] zurückzukehren, benötigen wir m weitere Schritte.

Einfach gesagt, wir müssen nur m weitere Schritte ausführen, nachdem wir den Kollisionsknoten gefunden haben. Wir können einen Zeiger haben, der von Anfang an ausgeführt wird, und einen Zeiger, der vom Kollisionsknoten ausgeht. Sie treffen sich nach m Schritten bei N [0].

Daher lautet der Pseudocode wie folgt:

1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6
phdfong - Kenneth Fong
quelle
1

Ich denke nicht, dass es der Ausgangspunkt ist, wenn sie sich treffen. Aber ja, wenn sich der andere Zeiger (F) zuvor am Treffpunkt befand, befindet sich dieser Zeiger am Ende der Schleife anstelle des Starts der Schleife und des Zeigers (S), der am Anfang der Liste begonnen hat am Anfang der Schleife enden. für zB:

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8

Meet at :16

Start at :8

public Node meetNodeInLoop(){

    Node fast=head;
    Node slow=head;

    fast=fast.next.next;
    slow=slow.next;

    while(fast!=slow){

        fast=fast.next;
        fast=fast.next;

        if(fast==slow) break; 

        slow=slow.next;
    }

    return fast;

}

public Node startOfLoop(Node meet){

    Node slow=head;
    Node fast=meet;

    while(slow!=fast){
        fast=fast.next;
        if(slow==fast.next) break;
        slow=slow.next;
    }

    return slow;
}
MrA
quelle
1

Eine einfache Erklärung unter Verwendung der Idee der Relativgeschwindigkeit, die in der High School gelehrt wird - Vorlesungen Physik 101 / Kinematik.

Kreis in LinkedList

  1. Nehmen wir an, der Abstand vom Beginn der verknüpften Liste zum Beginn des Kreises beträgt xHopfen. Nennen wir den Kreisanfang als Punkt X(in Großbuchstaben - siehe Abbildung oben). Nehmen wir auch an, dass die Gesamtgröße des Kreises N Hopfen beträgt.

  2. Geschwindigkeit des Hasen = 2 * Geschwindigkeit der Schildkröte. Das ist also, 1 hops/secund 2 hops/secjeweils

  3. Wenn die Schildkröte den Anfang des Kreises erreicht X, muss der Hase xan der Stelle Yin der Figur weiter hüpfen . (Weil Hase doppelt so weit gereist ist wie die Schildkröte).

  4. Somit Länge des verbleibenden Bogen im Uhrzeigersinn von X zu Y wäre N-x. Dies ist auch die relative Entfernung, die zwischen dem Hasen und der Schildkröte zurückgelegt werden muss, damit sie sich treffen können . Nehmen wir an, diese relative Distanz wird in der Zeit zurückgelegt, t_mdh in der Zeit, um sich zu treffen. Relative Geschwindigkeit ist (2 hops/sec - 1 hops/sec)dh 1 hops/sec. Wenn wir also relative Entfernung = relative Geschwindigkeit X Zeit verwenden, erhalten wir t= N-xSek. Es wird also dauern N-x, bis der Treffpunkt sowohl für die Schildkröte als auch für den Hasen erreicht ist.

  5. Jetzt in N-xSekundenschnelle und mit 1 hops/secGeschwindigkeit wird die Schildkröte, die früher am Punkt war X, Nx-Hopfen abdecken, um den Treffpunkt zu erreichen M. Das bedeutet also den TreffpunktM an ist N-xHopfen entgegen den Uhrzeigersinn von X= (was weiter impliziert) => , dass es xAbstand von Punkt verbleibenden Mzu dem XUhrzeigersinn.

  6. Ist xaber auch die Entfernung zum Punkt Xvom Anfang der verknüpften Liste.

  7. Nun ist es uns egal, wie viele Hopfen xentsprechen. Wenn wir eine Schildkröte am Anfang der LinkedList und eine Schildkröte am Treffpunkt platzieren Mund sie hüpfen / laufen lassen, treffen sie sich am Punkt X, dem Punkt (oder Knoten), den wir benötigen.

Pranjal Mittal
quelle
1

Das Arbeiten mit einem Diagramm würde helfen. Ich versuche das Problem ohne Gleichungen zu erklären.

  1. Wenn wir Hase und Schildkröte im Kreis laufen lassen und Hase zweimal Schildkröte laufen lässt, wäre am Ende einer Runde für Hasenschildkröte die Hälfte. Am Ende von zwei Runden hätte die Hasenschildkröte eine Runde gefahren und beide treffen sich. Dies gilt für alle Geschwindigkeiten, z. B. wenn Hase dreimal läuft, Hase 1 Runde entspricht 1/3 der Schildkröte, sodass Hasenschildkröte am Ende von 3 Runden 1 Runde zurückgelegt hätte und sie sich treffen.
  2. Wenn wir sie nun m Schritte vor der Schleife starten, bedeutet dies, dass der schnellere Hase in der Schleife voraus startet. Wenn also die Schildkröte den Start der Schleife erreicht, ist der Hase m Schritte vor der Schleife und wenn sie sich treffen, sind es m Schritte vor dem Start der Schleife.
Shiva Kumar
quelle
1

-Es gibt k Schritte vor der Schleife. Wir wissen nicht, was k ist und müssen es nicht herausfinden. Wir können abstrakt mit nur k arbeiten.

--Nach k Schritten

----- T ist am Zyklusbeginn

----- H ist k Schritte in den Zyklus (er ging insgesamt 2k und damit k in die Schleife)

** Sie sind jetzt Loopsize - k voneinander entfernt

(Beachten Sie, dass k == K == mod (Schleifengröße, k) --eg Wenn ein Knoten 2 Schritte in einen 5-Knoten-Zyklus ist, sind es auch 7, 12 oder 392 Schritte, also wie groß der Zyklus ist, k k nicht Faktor in.

Da sie sich mit einer Geschwindigkeit von 1 Schritt pro Zeiteinheit einholen, weil sich einer doppelt so schnell bewegt wie der andere, treffen sie sich in Schleifengröße - k.

Dies bedeutet, dass k Knoten benötigt werden, um den Beginn des Zyklus zu erreichen, und daher der Abstand vom Kopf zum Zyklusstart und die Kollision zum Zyklusstart gleich sind.

Bewegen Sie nun nach der ersten Kollision T zurück zum Kopf. T und H treffen sich beim Zyklestart, wenn Sie sich mit einer Geschwindigkeit von jeweils 1 bewegen. (in k Schritten für beide)

Dies bedeutet, dass der Algorithmus ist:

  • von Kopfbewegung T = t.next und H.next.next bis sie kollidieren (T == H) (es gibt einen Zyklus)

// Kümmere dich um den Fall, dass k = 0 ist oder T und H sich am Kopf der Schleife treffen, indem du die Länge der Schleife berechnest

- Zählen Sie die Länge des Zyklus, indem Sie T oder H mit einem Zähler um ihn herum bewegen

- Bewegen Sie einen Zeiger T2 auf den Kopf der Liste

- Zeigerlänge der Zyklusschritte verschieben

- Bewegen Sie einen weiteren Zeiger H2 auf den Kopf

- Bewegen Sie T2 und H2 zusammen, bis sie sich zu Beginn des Zyklus treffen

das ist es!

Droiden-Teehaus
quelle
1

Es gibt bereits viele Antworten darauf, aber ich habe mir einmal ein Diagramm dafür ausgedacht, das für mich visuell intuitiver ist. Vielleicht kann es anderen Menschen helfen.

Die wichtigsten Aha-Momente für mich waren:

  • Teilen Sie T (Schildkröte) in T1 (Pre-Loop) und T2 (In-Loop). T = Schildkröte, H = Hase

  • Subtrahieren Sie T von H , wo sie sich visuell überlappen. Was bleibt , ( H - T = H‘ ) gleich T .

  • Die verbleibende Mathematik ist ganz einfach. Subtrahieren Sie von H, wo T sich visuell überlappt
mhelvens
quelle
-1

Ich weiß, dass es bereits eine akzeptierte Antwort auf dieses Problem gibt, aber ich werde trotzdem versuchen, auf flüssige Weise zu antworten. Annehmen :

The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. 
    Speed of tortoise : v
    Speed of hare     : 2*v 
    Point where both meet is at a distance 'x + b - k' from the starting point.

Nun, lassen Sie den Hasen und die Schildkröte nach der Zeit 't' von Anfang an treffen.

Beobachtungen:

Wenn, von der Schildkröte zurückgelegte Strecke = v * t = x + (bk) (sagen wir)

Dann ist die vom Hasen zurückgelegte Strecke = 2 * v * t = x + (b - k) + b (da der Hase den geschlungenen Teil bereits einmal durchlaufen hat)

Jetzt sind die Besprechungszeiten gleich.

=> x + 2 * b - k = 2 * (x + b - k)

=> x = k

Dies bedeutet natürlich, dass die Länge des Pfades, der nicht geloopt ist, der Entfernung des Startpunkts der Schleife von dem Punkt entspricht, an dem sich beide treffen.

n0nChun
quelle
Sie können nicht davon ausgehen, dass die Schildkröte genau x + bk gereist ist, als sie sich trifft. Ich verstehe auch nicht, wie du x + 2 * bk für die Entfernung des Hasen bekommen hast.
Plumenator
Weil der Hase den geschlungenen Teil schon einmal durchquert hätte, um die Schildkröte treffen zu müssen. Ich habe es dort nicht erklärt: /
n0nChun
-1

Es ist tatsächlich leicht zu beweisen, dass sich beide am Startpunkt treffen werden, wenn man die Mathematik hinter dem Treffpunkt berücksichtigt.
Zunächst sei m der Startpunkt des Zyklus in der verknüpften Liste und n die Länge des Zyklus. Damit sich der Hase und die Schildkröte treffen können, haben wir:

( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start)

Mathematischer ausgedrückt:

(2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n 

so treffen sie sich zum Zeitpunkt t, der ein Vielfaches der Zykluslänge sein sollte. Dies bedeutet, dass sie sich an einem Ort treffen, nämlich (t-m) modulo n = (0-m) modulo n = (-m) modulo n .

Kommen wir nun zu der Frage zurück: Wenn Sie einen Zeiger vom Anfang der verknüpften Liste und einen anderen vom Schnittpunkt bewegen, wird der Hase (der sich innerhalb des Zyklus bewegt) nach m Schritten zu einem Punkt kommen, der ist ((-m) + m) modulo n = 0 modulo nDas ist nichts anderes als der Startpunkt des Zyklus. Wir können also sehen, dass es nach m Schritten zum Beginn des Zyklus kommt und die Schildkröte ihn dort trifft, wenn sie m durchquert Schritte vom Beginn der verknüpften Liste .

Als Randnotiz können wir die Zeit ihres Schnittpunkts auch folgendermaßen berechnen: Die Bedingung t = 0 modulo nbesagt, dass sie sich zu einem Zeitpunkt treffen werden, der ein Vielfaches der Zykluslänge ist, und dass t auch größer als m sein sollte, als sie sich treffen würden der Kreislauf . Die benötigte Zeit ist also gleich dem ersten Vielfachen von n, das größer als m ist .

user1011
quelle
Sie treffen sich nicht unbedingt zu Beginn des Zyklus.
Warren MacEvoy