フロイドのサイクル検出アルゴリズムを理解するための助けを求めています。ウィキペディア（ http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare ）

アルゴリズムがO（n）時間でサイクルを検出する方法を確認できます。ただし、私は亀とうさぎのポインターが初めて出会ったら、サイクルの開始は、亀のポインターを最初に戻し、次に亀とウサギの両方を一度に1ステップずつ動かすことによって決定できます。最初の出会いはサイクルの始まりです。

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

コメント

  • stackoverflowで答えを見つけました。誰かがこれを調べてくれてありがとう。そして、私のような人が説明を求めている場合は、 stackov erflow.com/questions/3952805/ … 質問に対する選択された回答は、それを説明しています！
  • こんにちは@Anurag。ちなみに、'は"亀と野ウサギ"アルゴリズムここ
  • fast変数、または" hare "は、1つ先ではなく、亀の2倍の速度で移動する必要がありますか？
  • プログラム： javabypatel.blogspot.in/2015/12/detect-loop-in-linked-list.html

回答

「単一リンクリストでのループの開始の検出」、ここに抜粋があります：

ここに画像の説明を入力してください

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

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

fastPointerは double slowPointerの速度、および時間は一定です<ミーティングポイントに到達したときの両方のdivid = "2f2cdd3b8a">

。したがって、単純な速度、時間、距離の関係を使用することにより（slowPointerは半分の距離を移動しました）：

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

したがって、slowPointerをリンクリストの先頭に移動し、両方をslowPointerとfastPointerは、一度に1つのノードを移動します。どちらもカバーする距離は同じです。 。

リンクリストでループが開始するポイントに到達します。

コメント

  • ここでは、1回転後に会うと仮定しています。特定の番号の後に会う場合があります（サイクルが小さい場合）。回転の。
  • @JotWaraich画像はすべての場合を代表するものではありません。ただし、論理は依然として保持されます
  • これはインターネット全体でこのアルゴリズムに関する最も簡単な答えです
  • I 'よくわかりませんこの証明が正しければ。遅いポインターが移動する距離は（x +（y + z）*α+ y）であり、速いポインターが移動する距離は（x +（y + z）*β+ y）である必要があります。ここで、αとβは数値です。低速ポインタと高速ポインタが通過するサイクルの数。この追加では証明が失敗するようです。
  • @ hashcode55はい、これは私にはわかりません

回答

受け入れられた回答は他の場所でも証明として見ました。ただし、簡単に理解できますが、正しくありません。それが証明するのは

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

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

$ z = x \ mod \（y + z）$

$（y + z）$はループの長さ$ L $

なので、証明したいのは次のとおりです。

$ z = x \ mod \ L $

または、zがx（モジュロ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 $で開始する場合、ループの開始時に終了します。

コメント

  • この回答が過小評価されている理由がわかりません'。これが最も正式な証明のようです。
  • @ I8再びx = zが間違っている場合は、高速ポインタを開始点に戻すロジック&両方を移動しますループの開始を見つけるための高速&低速ポインタは'機能しません。 x = zの意味が間違っているのかわかりませんが、その理由を説明してください。
  • @divine x = zは、両方が等しいことを意味するため間違っていますが、非常に長くてもかまいません。テール」（大きなx）と非常に小さな円（小さなz）。正式に正しいモジュロを使用することにより、x％L == z、つまり、他のポインターと結合するのを待っている円内を移動するポインターが、必要な数のループを作成できることを証明したいだけです。最後のステップ（つまり、ループ後の残り）は、サークル自体の開始につながります。
  • これは素晴らしいです!!
  • まだ行っていない人のために' x = k * L –yがz = x modLにつながる理由を理解していません。x= k * L –y — > xから=（k –1）* L + L –yすると、L –yはzでなければならないことがわかります。これで、x =（k –1）* L + z

回答

あると言う<ループが開始する前のspanclass = "math-container"> $ l $ 要素と、ループ内の $ n $ 要素。また、 $ e_l $ は、リンクリストをトラバースするときに表示されるループの最初の要素です。 "要素 $ x $ が $ eの一歩先を行くと言うとき$ "つまり、 $ x $ ステップで $ e $ 。

これで、Tr（トータス）が $ e_l $ に到達すると、 $ l $ の繰り返し、たとえば、Hr（Hare）は $ x $ ステップ前に $ e_l $ 。 Hrはそれまでに合計 $ 2l $ ステップを実行したため（ループの前に $ l $ ステップ）、したがって：

$ x = l \ bmod n $ 。

今後の各反復で、TrとHrは次のように進行します。それぞれ1ステップと2ステップであるため、反復ごとに"ギャップ"が1増加します。したがって、 $ nx $ の反復、ギャップが $ x +（nx）= n $ になる場合。したがって、会議要素の $ M $ は、 $ nx $ ステップ前になります。 -container “> $ e_l $ 。つまり、 $ M $ の後に $ x $ ステップを実行すると、再び $ e_l $ 。私たちの目標は、 $ e_l $ を見つけることです。

したがって、で1つの参照Trから始めると、 $ M $ とリンクリストの先頭にある別の参照Hrを使用し、 $ l $ を繰り返した後、両方を一度に1ステップずつ進めます。 ：

  • Hrは頭の $ l $ ステップ先になります。これは $ e_l $ 。

  • Trは $（l \ bmod n）$ ステップになります $ M $ の前、つまり $ x $ の前の $ M $ 、つまり $ e_l $ 。

したがって、会った、それは $ e_l $ であることがわかっています。

この記事を参照詳細については。ここに、 $ e_l $ を見つけるためのわずかに変更されたメソッドがあります。

回答

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

回答

また、一番上の回答は不完全だと思います。他の説明もいくつかありますが、別の説明があります。同じことを表示するMODのないバージョン。これは、おそらく一部の人にとっては簡単です。

同じ設定で、 $ X \ ge 0 $ がループの前の距離。 $ N \ le \ text {size of list} $ はループのサイズです（数量 $ y + z $ ）、待ち合わせ場所はループ内の $ Y $ です。この時点で、 $ X + Y \ le N $ も作成したことに注意してください。

これで、低速ポインタが $ X + Y + pN $ 、ここで $ p $ は任意の整数です。次に、高速ポインタが $ 2（X + Y + pN）$ を移動しました。

これで、 が $ Y $ で会うと主張します。

証明：

$ Y $ で会う場合は、速いポインタは遅いポインタよりも正確に $ qN $ 移動しました。ここで、 $ q $ は整数です。 。次に、次のようになります。 $$ \ text {distance Difference =} 2（X + Y + pN）-（X + Y + pN）= X + Y + pN $$ 。ただし、 $ Y $ はループ内の任意のミーティングポイントであるため、 $ X + Y = Nを選択するだけで済みます。 $ は、 $ X + Y \ le N $ として保持されます。

したがって、次のようになります。 $$ X + Y + pN = N + pN =（p + 1）N = qN $$ これは、 $ p + 1 = qの場合に当てはまります。 $ 。これで、 $ p $ と $ q $ はどちらも任意の整数であるため、最小値を選択するだけで済みます。その $ p = 0、q = 1 $ は、次のように対応します。 $$ \ text {低速ポインタが移動した距離} = X + Y + pN = X + Y $$ および $$ \ text {高速ポインタが移動した距離} =（X + Y + pN）+ qN = X + Y + N $$ なので、最初に低速ポインタに出会った高速ポインタは、正確に $ N $ 以上移動しました。

回答

亀とうさぎは、リストの「トップ」の値で初期化される2つのポインターです。ループの各サイクルで、ウサギは2アイテムずつ増加し、カメは1アイテムずつ増加します。いずれかの時点で、うさぎがうさぎと等しい場合、ループが検出されています。うさぎが終わりに等しい場合、ループは見つかりません。

この投稿では、行ごとに説明しています。

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です