問題タブ [cycle-detection]

2つ以下のポインタを使用してリンクリストのループの開始を見つける方法はありますか？ すべてのノードにアクセスして、それを表示済みとしてマークし、最初のノードがすでに表示されていることを報告したくありません。これを行う他の方法はありますか？

辞書のプレースホルダーを置き換えて文字列を拡張したいとします。置換文字列には、プレースホルダーを含めることもできます。

たとえば、循環置換パターンがない限り、これは正常に機能します"c" => "#b#"。その後、メモリが使い果たされるまで、プログラムは無限ループにスローされます。

そのようなパターンを検出する簡単な方法はありますか? 置換間の距離が任意に長くなる可能性があるソリューションを探しています。a->b->c->d->f->a
理想的には、別の分析ではなく、ループ内でも解決策が発生することです。

隣接リストにサイクルがあるかどうかを確認する際に問題があります。隣接リストに少なくとも 1 つのサイクルが存在するかどうかをチェックする関数を作成したいと考えています。

私のプログラムに基づいています。まず、ルート ノードを入力する必要があります。続いて、ノードの数、グラフ内のノード、エッジの数、およびエッジを表す隣接リストを入力します。隣接リストの各エントリには、ノードのペアが含まれています。

サンプル入力:

上記のサンプル入力にはサイクルがあります: [ A --> B --> C --> A ]サイクルがあるかどうかを出力したい。

これはこれまでの私のプログラムです：

上記の私のプログラムには、サイクルをチェックする関数がまだありません。また、ルートノードのことを実装したい..誰かが上記の私のプログラムを改善できる場合は、私に答えて、信頼できるコードを教えてください. ありがとう！(初心者です！)

http://learn.yancyparedes.net/2012/03/strongly-connected-components-using-tarjans-algorithm/の実装を使用して、サイクル検出のための Tarjan のアルゴリズムを試しました。次のグラフがテストに使用されました:
ab
ac
ba
bc
cd
da
出力として、次の結果が得られました: Set 0: [c, b, a, d]

私の問題は、すべてのサイクルが必要であるため、この結果にセット [a,b] と [a,c,d] が含まれていないことです。すべてのサイクルを取得するように実装を変更する方法がある場合は、今ですか? または、この問題に対して別のアルゴリズムが存在しますか?

ありがとうございました！

この質問は、実装よりも効率的なアルゴリズムに関するものなので、コードは投稿しません。（質問を理解するのに本当に役立ちません）

質問を紹介すると、自動車のクラッシュレポートを計算するプログラムを開発しています。一連の「方程式」 (以降はEq、複数形は Eqs) を提供し、データを入力して通常は n 個の結果を取得します。

例: 対象空間 (x) を選択し、入力時間 (t)、加速度 (a)、初期速度 (v) を選択すると、x = (a*t)+((a*t^2)/2) になります。問題は、このEqs が vars と ecuation 自体よりも多くのものを含むオブジェクト内にあるということです。それをBo (busssines オブジェクトの話です。

そのため、BO は非常に大きく (そしてそうである必要があります)、とりわけ、1 つの Bo は N 個の Eq を持つことができ、複数の結果が得られます。また、すべての Eq が入力として値の範囲を取ることができるため、うまくいきます.. . (2 つの変数で範囲を使用できると仮定しましょう。実際にはこれは制限されていません)、結果ごとに結果の表が作成されます (一部の Bos には 4 つの異なる結果があります)。範囲の Te ステップは、最初の範囲が 20、2 番目の範囲が 10 に制限されています。(1 つの Bo の 800 の結果にマッピングされる 4 つの結果を持つ Bo で)。

ところで、この Bos をそれぞれの結果とともに保存 (ファイルに保存) する必要があり、Var 入力は実行時に毎回計算することはできません (ecuation を保存し、var 入力を保存して、毎回結果を計算することができます)。 Bos はこれらの ecuations を変更することができ、ユーザーは以前の結果を保持する必要があるため、質問しないでください..

また、Bo の結果の 1 つを別の Bo の Eq 入力にインポートすることもできます。したがって、前の例 (Bo1 と呼びましょう) では、加速はそれを計算する別の Bo (Bo2) から発生する可能性があり、それを計算するために他のパラメーターを使用します。Bo2 の入力を変更すると、結果が変わるため、少なくとも 1 Bo1 の var が変化し、Bo1 の結果が変化します。これはカスケードできます (B3 からの B2 インポートなど)。そして、1 つの Bo は、N 個の他の Bo から N 個の変数をすべてインポートできます。

ポインターまたは参照型を使用できません (おそらく参照型を使用できますが、とにかく多くの作業が必要であり、さまざまなユーザーから以前に保存されたデータを操作する必要があり、参照が欠落しているオブジェクトなど)。

配列のコレクションを使用することにしました。各配列に格納されている {Id_of_Bo_Exporting, Id_Bo_importing,Id_Variable_of_Bo_Importing,..(特定の結果のエクスポートをマップする ids)} 配列は int です (最初の 2 は長い)。

あまり好きではありませんが、コードは問題なく動作しています。(読んでくれてありがとう) 質問はこれからです、私は約束します。

問題は、循環インポートをチェックする必要があることです。B3 が B2 からインポートし、B2 が B1 からインポートする場合、B3 (または B2) からの Bo1 のインポートを許可すべきではありません。これは無限ループにつながります (ループを停止することはできますが、そのインポートを許可する数学的な観点からのロジックではありません)。

インポートリストは最終的に非常に長くなる可能性があります

私は ArrayList< ArrayList< long>> のことを考えているので、インポートを追加するたびに、この「もの」に Ids を追加します。(arraylist の arraylist)

long の各配列は、最初の位置に「Bo id ヘッダー」を持ち、Bo がインポートされるたびに、新しい Id がそのリストに追加され、Bo をインポートする他のすべての Bo (インポートを作成するもの) が追加されます。

したがって、ユーザーが B1 から B9 を作成しようとすると、メソッドが検出し、B1 が独自のリストに追加され、許可されません。

実装はとても簡単です。（Javaを使用しましょう。いいえ、私は.netを使用しています。自分でプロジェクトを開始しませんでした）

例 {{}}

B1 は B2 からインポートします: { {B1,B2} }

B1 は B6 からインポートします: {{B1,B2, B6 }}

B4 からの B2 インポート: {{B1,B2,B6, B4 }, {B2,B4} }

B9 からの B4 インポート: {{B1,B2,B3,B4, B9 },{B2,B4, B9 }, {B4,B9 }}

B10 からの B3 インポート: {{B1,B2,B3,B4,B9, B10 },{B2,B4,B9},{B4,B9}, {B3,B10} }

long の各配列は、最初の位置に「Bo id ヘッダー」を持ち、Bo がインポートされるたびに、新しい Id がそのリストに追加され、Bo をインポートする他のすべての Bo (インポートを作成するもの) が追加されます。

したがって、ユーザーが B1 から B9 を作成しようとすると、メソッドが検出し、B1 が独自のリストに追加され、許可されません。

実装はとても簡単です。（Javaを使用しましょう。いいえ、私は.netを使用しています。自分でプロジェクトを開始しませんでした）

さて、質問 (ListSet などを使用して開始) は、これを行うためのより効率的な方法を考えることができますか? 両方のリスト (ユーザーによっては、インポートと iL が非常に速く大きくなる可能性があります)。キャプションはスピードです。

私は有向グラフ、つまり次数 nx n の行列を持っています。
サイクルに含まれる頂点とともに、そこに存在するすべてのサイクルを見つける必要があります。

次に例を示します。

出力は次のようになります。

m X n行または列で値の繰り返しがないサイズの行列が与えられた場合、サイクルを検出する効率的な方法はありますか?

たとえば、次のサンプル マトリックスがあります。

3 5 2 9 7 4
4 3 6 1 8 7
1 4 7 5 2 9
9 8 3 2 6 1
2 6 8 7 3 5

サイズ3の置換サイクルが少なくとも1つある：

3 5 2 9 7 4
4 8 3 1 6 7
1 4 7 5 2 9
9 6 8 2 3 1
2 3 6 7 8 5

行 2、4、および 5 の値 3、6、および 8 は、サイクルを形成します。

問題はカクロパズルに関するものです。それらを解決することとは関係ありませんが、特定のグリッドのレイアウトが不適切になるかどうかを検出しようとしています。行と列の合計は両方のレイアウトで同じであるため、並べ替えのサイクルはその特定のレイアウトを無効にします。

最近、私はインタビューに出席し、理解できない次の質問に出くわしました.

質問1：

私が読んだ証拠によると、カメは1ステップ移動し、ウサギは一度に2ステップ移動します。私はこれを理解し、うさぎは亀の2倍の速度で動くので、ある時点で会うでしょう。2 と 3 または 3 と 5 または 2 と 4 のようなランダムな値を持つことはできません。カメとウサギの値を選択するための条件は何ですか? ランダムな値を選択できますか?

質問2：

カメとウサギがループに入る条件はありますか? カメとウサギの値がそれぞれ 2 と 4 であるとします。そして、リンクされたリストは次のようになります

Tortoise がノード 3 でループに入り、Hare がノード 2 でループに入ると、ループ内で両者が出会うことはありません。では、カメとノウサギがループに入る条件はありますか?

それらが互いに出会うように選択されるべき限定された値はありますか?