フロイドのサイクル検出アルゴリズム|サイクルの開始点を決定します

Question

私はフロイドのサイクル検出アルゴリズムを理解するのを助けています。私はウィキペディアで説明をしました（http://en.wikipedia.org/wiki/cycle_detection#tortoise_and_hare)

アルゴリズムがO（n）時間でサイクルを検出する方法を見ることができます。ただし、カメとうさぎのポインターが初めて会うと、カメのポインターを元に戻し、カメとうさぎの両方を一歩ずつ動かすことで、サイクルの開始を決定できるという事実を視覚化することはできません。彼らが最初に出会うポイントは、サイクルの始まりです。

私はそれを理解/視覚化することができないので、誰かがウィキペディアの説明とは異なる説明を提供することで助けることができますか？

Answer 1

Stackoverflowで答えを見つけました。誰かが私のためにこれを調べてくれたならありがとう。そして、私のような人が説明を望んでいたために、次を参照してください。 https://stackoverflow.com/questions/3952805/proof-of-retecting-the-start-of-cycle-in-linked-list 質問に対する選ばれた答えはそれを説明します！

Answer 2

参照できます 「単独でリンクされたリストでループの開始を検出する」, 、これが抜粋です：

距離が移動しました slowPointer 会う前に $ = x+y $

距離が移動しました fastPointer 会う前に $ =（x + y + z） + y $ = x + 2y + z

以来 fastPointer 一緒に旅行します ダブル の速度 slowPointer, 、 と 時間は一定です 会議ポイントに到達するときの両方のために。したがって、単純な速度、時間、距離の関係を使用することにより（slowPointer 半分の距離を移動しました）：

begin {align*} 2* operatorname {dist}（ text {ellopointer}）＆= operatorname {dist}（ text {fastpointer}） 2（x+y）＆= x+2y+z 2x+2y＆= x+2y+z x＆= z end {align*}

したがって、移動することによって slowPointer リンクリストを開始し、両方を作成します slowPointer と fastPointer 一度に1つのノードを移動するには、 どちらもカバーするのと同じ距離を持っています.

それらは、リンクされたリストからループが開始されるポイントで到達します。

Answer 3

受け入れられた答えも他の場所で証明として見てきました。ただし、簡単にグロックできますが、間違っています。それが証明するのは

$ x = z $（これは明らかに間違っており、図は、スケッチの方法でもっともらしいように見えます）。

あなたが本当に証明したいのは（上記の受け入れられた答えの図で説明されているのと同じ変数を使用して）です：

$ z = x mod （y + z）$

$（y + z）$はループの長さ、$ l $です

だから、私たちが証明したいのは次のとおりです。

$ z = x mod l $

またはそのzがx（modulo l）と一致しています

フォロー証明は私にとってより理にかなっています：

ミーティングポイント、$ m = x + y $

$ 2（x + y）= m + kl $、$ k $はある程度定数です。基本的に、高速ポインターによって移動する距離は$ x + y $とループの長さの複数のもの、$ l $です

$ x + y = kl $

$ x = kl -y $

上記の方程式は、$ x $がループ長の倍数、$ l $マイナス$ y $と同じであることを証明しています。したがって、高速ポインターがミーティングポイント（$ m $）または$ x + y $で始まると、ループの開始時に終了します。