2

これが他の場所で回答されている場合は申し訳ありませんが、限られたアルゴリズム用語を使用してまだ見つけていません。;)

私の状況は次のとおりです。さまざまな数のデータ要素があり、それぞれが他のデータ要素に対してテストされ、互換性が判断されています。互換性は、2 次元配列 (真理値表?) に相当するものに格納されます。私の目標は、組み合わせ内のすべての要素が他の要素と互換性がある、これらのデータ要素のすべての可能な組み合わせを生成することです。

たとえば、要素 1 (4 のうち) が要素 2 および 4 と互換性があり、要素 2 が要素 1、3 および 4 と互換性があり、要素 3 が要素 2 と互換性があり、要素 4 が要素 1 と 2 と互換性がある場合、私の真理値表は次のようになります。次のようになります。

1) {1,1,0,1}
2) {1,1,1,1}
3) {0,1,1,0}
4) {1,1,0,1}

これから必要な組み合わせは次のとおりです。
1,2,4
1,2
1,4
1
2,3
2,4
2
3
4

私のアプローチは多くの状況でうまく機能しますが、データ セットによっては、要素数が 5000 を超えると、ひどく行き詰まることがあります。2 つ目の課題は、実行時間を 5 秒から 3 時間にするパターンを特定することです...

ブール配列を見るだけで、もっと簡単な解決策があるに違いないと感じます-おそらく誰かにちなんで名付けられたアルゴリズムです。上記から推測できるように、私は必ずしも質問の仕方を知りません。;)

御時間ありがとうございます！

4

2 に答える 2

4

あなたが持っているのは真理値表ではなく「隣接行列」であり、隣接行列が表現されているグラフの「完全に接続されたサブグラフ」をすべて探していると思います。完全に接続されたサブグラフは、メモリが機能する場合、「クリーク」としても知られています。私はあなたが何を探しているのかよくわかりません。以前の回答者の1人が示したように、あなたの言葉とあなたのマトリックスの間にいくつかの矛盾があります。

それらの用語をグーグルで調べてください。今ここで、頭や図書館からこのようなものを掘り出すには遅すぎます。

グラフは対称であることに注意してください。つまり、「1が2と互換性がある場合」、必然的に「2は1と互換性があります」。これで、データストレージ要件が半分になりました（データストレージの要件がより複雑になり、マトリックスの上半分または下半分を保存することは、多くの場合、必要なスペースよりも気が遠くなります）。また、「1は1と互換性がある」という考えを表現するために、主対角線に沿って1を付ける必要があると思います。最終的には、自分自身とのみ互換性のある要素がいくつかあると思います。

悲しいことに、グラフでクリークを見つけることはNPですが、5000x5000要素のみの行列の場合、ブルートフォースナイーブアルゴリズムはコンパイル型言語でそれほど長くはかからないはずです。

よろしく

マーク

于 2009-08-19T22:33:17.623 に答える
1

基本的に、式を論理和の正規形に還元しようとしています。一般に、この問題は NP 完全です。ごめん。^_^

于 2009-08-19T21:59:49.390 に答える