ここで言及した元のボールとバスケットの問題に加えて：ボールとバスケットの問題アルゴリズム？
少し違う問題があります。
まだ N 人がいて、無制限のボールを持っていますが、今回はバスケットを持っていません。
問題は：
無制限のボールと M 個の異なるバスケットを持つ N 人の人がいます。人々はバスケットにボールを投げます。
同じバスケットにボールを投げている人々のグループを見つけたいです。
人 A はバスケット 1 、2、4、、6、7、14、51、32 に投げます 人 B はバスケット 3、4、6、7、14、15、16、64、43 に投げます 人 C はバスケット 3、 4、6、7、5、87、42、32、52、55 . . . 等
この例では、人物 A と B はよくつながっている可能性があり (友人としましょう) (4,6,7,14 共通)、C も彼らとつながっている可能性がありますが、あまりつながっていません。(4、6、7共通)
非常に大規模な人々のデータベースから、そのような 4 ～ 5 人のグループを見つけたいと考えています。
ジャクソンのアイデアが始まりです。
クリークを見つけたら、すべてのエッジのバスケットの交差によって、各クリークに共通のバスケット セットを定義します。(エッジのバスケットは、このエッジのノードによって表される人々に共通のバスケットです)。共通バスケット集合が X より大きい場合にのみ、このクリークは実際に接続されたグループを表します。
たとえば、元の質問では、エッジは次のようになります。
A-B: weight=4, baskets=[4,6,7,14]
A-C: weight=3, baskets=[4,6,7]
B-C: weight=4, baskets=[3,4,6,7]
3 未満で剪定すると、これはクリークであり、共通バスケット セット = [4,6,7] であることがわかります。
ジャクソンの回答へのコメントで示した例では、共通のバスケットセットは空になるため、これらの人が実際には接続されていないことがわかります。
わかりました、私の最初のアイデアです。これを加重グラフとしてモデル化します。人を頂点にして、カゴをシェアすることでリンクを作る。複数のバスケットを共有している場合は、共有するバスケットごとにリンクの重みを増やします。したがって、あなたの例では、A と B の間のエッジの重みは 4 になります。
次に、グループ内の全員がどれだけ友好的でなければならないかを決定し、その値よりも重みが小さいエッジを切り取り、結果のグラフでクリークを探すことができます。