問題タブ [cycle-detection]

少し前に、この Python 実装の Pollard-Brent アルゴリズムを Clojure に移植しました。それは機能し、高速にも機能します。それは問題ではありません。また、同一の非ランダム シード値とステッピング関数を指定すると、Python コードのウサギとカメの位置が正確に再現されます。

しかし、私がそれに取り組んでいる間、カメとウサギが、ブレントの論文 (またはウィキペディア、またはその他の参照) のアルゴリズムの説明に基づいて期待したのとまったく同じように動かないことに気が付かずにはいられませんでした。の選択)。

具体的には、カメがウサギの位置にテレポートした後、ウサギdistanceはステップ数だけ前に進み、さらにステップdistance数だけ進みます。また、Brent-Pollard アルゴリズムでは、中間値も重要です。ただし、このコードは 2 番目の「パス」のステップのみを保存します。

Python コードの 6 行目から 18 行目と私のコメントは次のとおりです。

私は今日、自分のコードに戻って、単純化されたバージョンをモックアップしてインデックスを表示することで、確実にテストすることにしました。これらは現在のコードによって与えられたインデックスです:

現在のバージョン:

その間、これは私がアルゴリズムに期待することです：

期待される出力:

「予想される」バージョンは、アルゴリズムに組み込まれた場合、Clojure で読みやすくなりますが、平均で 2 倍の時間がかかります (これは、インデックスを見ると理にかなっています)。

私の質問:

1. 期待される出力は、ブレントのアルゴリズムの「正規」バージョンですか?
2. 現在のバージョンはまだブレントのアルゴリズムの正しい実装ですか?
3. うさぎのパスに完全に連続したインデックスが含まれていないにもかかわらず、現在のバージョンが機能するのはなぜですか?

私はツリーサイクルの検出を探していて、このPHPコードにたどり着きました:

クレジット: https://gist.github.com/jmullan/450465/77bdaa2a57e73ecee8ca6d9449aad3f74b379ca5

これは、ツリーのようなデータ構造の線形サイクルを完全に検出しますが、使用するアルゴリズムやコード (配列参照) がどのように機能するかを理解できません。

それがどのアルゴリズムであるかを説明または指摘することで、誰かが助けてくれますか?

ありがとう。

Depth First Search (DFS)以外の有向グラフでサイクルを検出するために、 union-find アルゴリズムを適用できますか?

無向グラフの検出サイクルに和集合検索アルゴリズムを適用できることはわかっています。