1

カメとウサギのアルゴリズムを使用したサイクル検出のウィキペディアの実装を行っていました。Ruby言語を使用して、これが私が実装したものです：

def tortoise_and_hare(シーケンス)
  亀 = 1
  うさぎ= 2
  while シーケンス[亀] != シーケンス[ウサギ]
    カメ += 1
    うさぎ += 2
  終わり

  # 最初の繰り返しの開始インデックスを見つける
  idx = 0
  亀 = 0
  while シーケンス[亀] != シーケンス[ウサギ]
    カメ += 1
    うさぎ += 1
    idx += 1
  終わり

  # インデックス idx から始まるサイクルの長さを見つける
  長さ = 1
  ウサギ＝カメ＋1
  while シーケンス[亀] != シーケンス[ウサギ]
    うさぎ += 1
    長さ += 1
  終わり

  [idx、長さ]
終わり

シーケンス = [2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1]
idx、長さ = tortoise_and_hare(sequence)
pシーケンス[idx、長さ]

これは正しく機能しており、[6, 3, 1]. 今、

  1. シーケンスを にトリミングすると[2, 0, 6, 3, 1, 6, 3, 1]、空のセットが返されます。
  2. 問題は 2 番目のループにあることがわかります。サイクルに繰り返し文字がある場合、アルゴリズムは間違った答えを返します。例、 を [2, 0, 6, 3, 1, 6, 6, 3, 1, 6, 6, 3, 1, 6]返しますが[6, 3, 1]、 である必要があります[6, 3, 1, 6]。問題は 3 番目のループにあることがわかります。

だから私は私の質問は次のとおりだと思います：

  1. アルゴリズムはウィキペディア標準に掲載されていますか?
  2. 私の2番目のケースは間違っていますか? サイクル検出とは、私の試験ではない非常に長いシーケンスを意味することを知っていますが、それでもサイクルがあります。
  3. ケースが正しければ、アルゴリズムを改善し、上記で指摘した 2 つの問題を解決するにはどうすればよいでしょうか?

最初の問題の2番目のループを変更しようとしました（アルゴリズムが失敗するのに十分なほど小さいシーケンスをトリミングしました）が、うまくいきました：

  # 最初の繰り返しの開始インデックスを見つける
  idx = 0
  亀 = 0
  while シーケンス[亀] != シーケンス[ウサギ]
    カメ += 1
    うさぎ += 1
    ウサギ > sequence.length - 1 の場合、ウサギ = カメ
    idx += 1
  終わり
  1. 間違っているように見えますか、場合によっては失敗する可能性がありますか?
  2. 2番目の問題（文字の繰り返し）に対して何ができますか？

別のエレガントな正規表現ベースのソリューションを思いつきましたが、上記のアルゴリズムについてもっと知りたいと思っています。

好奇心のための正規表現ソリューション：/(?<cycle>(\d+\s)+(\d+))\s\k<cycle>/

編集：繰り返し文字を検出できない理由がわかりました。しかし、この状況で役立つ可能性のある他のアルゴリズムはありますか?

4

1 に答える 1

0

答えは、コードは問題ありませんが、サンプル セットが小さすぎるということです。このアルゴリズムは、可能な限り短い量のデータでサイクルを見つけることを主張していません。

リンクしたページのデータ セットの定義は、無限のデータ セットを生成するプロセスを定義します。ドメインは無制限ですが、範囲は有限であるため、このデータは最終的に繰り返す必要があります。

範囲に応じて、サイクルを決定するためにこのアルゴリズムで必要とされるデータの量は増減します。あなたはもはやそれを十分に提供していません。

私が行く解決策は？最初の数字を挿入することから始めて、範囲内の各数字と見つけた位置のマップを作成します。繰り返しを見つけるとすぐに、サイクルが見つかりました。1 番目のインスタンスの位置から 2 番目のインスタンスの直前の位置まで。これにより、線形の実行時間と N*M のメモリ使用量が得られます。N=リストのサイズ M=値の範囲

必要な perl (さびた perl) 正規表現は次のとおりです。

$data = "1 2 3 4 5 3 4 5"; 
if ($data =~ /(?<c>\d).*?(\k<c>)/) {
    print substr($data, $-[1], $-[2]-$-[1])."\n";
} elsif {
    print "NO\n";
}

これに関する最悪の実行時間は n^2 であり、1 桁の数値に対してのみ機能すると思います (簡単に修正できます) が、より単純です。

于 2013-06-20T08:18:28.120 に答える