2

まず第一に、私はJavaの初心者なので、これが可能かどうかさえわかりません! 基本的に、私はリレーショナルデータの巨大な（300万以上）データソースを持っています（つまり、AはB + C + Dと友達であり、BはD + G + Zと友達です（ただし、Aではありません-つまり、相互的ではありません）など）。この (必ずしも接続されていない) 有向グラフ内のすべてのサイクルを検索します。

Finding all cycles in graphというスレッドを見つけました。これは、少なくとも表面的には、私が求めていることを実行するように見える、Donald Johnson の (基本的な) サイクル検出アルゴリズムを示しています (試してみます火曜日に仕事に戻ったら、その間に聞いても問題ないと思います!)。

Johnson のアルゴリズムの Java 実装のコード (そのスレッド) をざっとスキャンしたところ、関係のマトリックスが最初のステップのように見えたので、私の質問は次のとおりだと思います。

a) Java は 3+million*3+million 行列を処理できますか? (A-friends-with-B を 2 値疎行列で表すことを計画していました)

b) 最初の問題として、すべての接続されたサブグラフを見つける必要がありますか?それとも、循環探索アルゴリズムが互いに素なデータを処理しますか?

c) これは実際に問題の適切な解決策ですか? 「基本」サイクルについての私の理解では、下のグラフでは、ABCDEF を選択するのではなく、ABF、BCD などを選択しますが、タスクを考えると、それは世界の終わりではありません。

    E
   / \
  D---F
 / \ / \
C---B---A

d) 必要に応じて、関係の相互性を強制することで問題を単純化できます。つまり、A-friends-with-B <==> B-friends-with-A です。本当に必要な場合は、データ サイズを削減することもできますが、現実的には、常に 1mil マーク前後になります。

z) これは P タスクですか、それとも NP タスクですか?! 私は噛むことができる以上に噛んでいますか？

ありがとうございました。アンディ

4

3 に答える 3

2

あなたが行っていることは、データ マイニングで非常によく研究されている問題に似ています。これは、アソシエーション ルール マイニングまたはより一般的に頻繁に行われるアイテムセット マイニングとして知られています。アイテムセット マイニングを頻繁に行うことで得られるものは、実際に行っていることよりも少し具体的ですが、より有用です。

私たちはクローズド・フリークエンシー・アイテムセット・マイニングを使用します。これが行うことは、誰もがお互いに友達である友達のすべてのグループを見つけることです。

私は今これを言います.Javaはあなたがやりたいことをすることができません. それほど多くのメモリをロードすることはできず、合理的な時間内にそのデータを処理するには効率的ではありません。C/C++ を使用する必要があります。閉じた頻度の高い項目セット マイナーである LCM を使用することをお勧めしますが、データ量が多いため、サポートをかなり高く設定する必要もあります。

検討すべきもう 1 つのことは、Large Graph Mining を読むことです。これもかなり大きな研究分野ですが、Java は役に立ちません。また、データ内のすべてのサイクルを見つけることはできません (非常にまばらでない限り)。それらの数が多すぎます。それらは重複していて、あまり意味がありません。最大のサイクルのいくつかを見つけることができるかもしれません。

于 2010-05-30T17:53:51.617 に答える
0

c) これは実際に問題の適切な解決策ですか? 「基本」サイクルについての私の理解では、下のグラフでは、ABCDEF を選択するのではなく、ABF、BCD などを選択しますが、タスクを考えると、それは世界の終わりではありません。

    E
   / \
  D---F
 / \ / \
C---B---A

いいえ。Donald Johnson の論文の意味での「初等」は単純を意味します。つまり、ノードが円内に 2 回現れることはありません。つまり、アルゴリズムは を選択AFBCDBAしませんが、 を選択しABCDEFます。

d) 必要に応じて、関係の相互性を強制することで問題を単純化できます。つまり、A-friends-with-B <==> B-friends-with-A です。本当に必要な場合は、データ サイズを削減することもできますが、現実的には、常に 1mil マーク前後になります。

無向グラフには（単純ではない）サイクルのベクトル空間があります（これには優れた基礎などがあります）が、それが役立つかどうかはわかりません。

z) これは P または NP タスクですか?

これは列挙問題であり、それ自体は P にも NP にもありません。

于 2010-05-30T16:33:27.573 に答える
0

すべてのサイクルを見つけることは合理的ではありません。指数関数的な数のサイクルがあり、すべてが互いに重なり合っています。

P または NP に関しては、最も遅い部分は実際には各サイクルを列挙しています (非常に多くのサイクルが存在する可能性があるため)。サイクルがない場合、線形アルゴリズムが存在します。

たぶん、実際にグラフを二重接続されたコンポーネントに分割したいですか? http://en.wikipedia.org/wiki/Biconnected_componentを参照

また、グラフを行列に格納することはほとんど合理的ではありません。理論的には良さそうですが、実際には拡張できません。代わりに隣接リストを使用してください ( http://en.wikipedia.org/wiki/Adjacency_list )

于 2010-05-30T16:47:22.543 に答える