ブール値の 2D 配列が与えられた場合、少なくとも 2 列と少なくとも 2 行で構成されるすべてのパターンを見つけたいと考えています。この問題は、グラフ内のクリークを見つけることにいくらか近いものです。
以下の例では、緑のセルは「真」のビットを表し、グレーは「偽」を表します。パターン 1 には列 1、3、4、5 と行 1、2 が含まれます。パターン 2 には列 2、4、行 2、3、4 のみが含まれます。
この背後にあるビジネス アイデアは、ソーシャル ネットワーク ユーザーのさまざまなグループ間で類似パターンを見つけることです。実際には、行数は 3E7 まで、列数は 300 までです。
ブルートフォースマッチング以外の解決策を実際に理解することはできません。
問題の適切な名前をアドバイスしてください。詳細を読むか、エレガントな解決策をアドバイスしてください。
これは、2 部グラフで特定のサイズよりも大きいすべてのbicliques (完全な 2 部部分グラフ)を要求する (と同等)ことです。ここで、行はグラフの一部 A の頂点であり、列は他の部分 B の頂点であり、行 u、列 v のセルが常に u \in A と v \in B の間にエッジがあります。緑の。
すべてのパターンを見つけたいと言っていますが、最大のパターン、つまり、行や列を追加しても拡張できないパターンだけを見つけたいと思うでしょう。(それ以外の場合、c >= 2 列および r >= 3 行の任意のパターンの場合、形成可能な 2^(c-2)*2^(r-3) を超える非最大パターンも返されます。行または列の一部を削除します。)
ただし、P != NP と仮定すると、最大パターンだけをリストするだけでも、行と列の数が指数関数的に増加する可能性があります。これは、緑色のセルの総数に関して、最大(つまり、可能な限り最大の) パターンを見つける問題が NP 完全であることが証明されているためです: 多項式時間ですべての最大パターンをリストすることが可能である場合、単純にそうすることができ、最大のものを選択することで、この NP 完全問題を多項式時間で解くことができます。