Wie finde ich Mustergruppen im booleschen Array?

Question

Bei einem 2D-Array von booleschen Werten möchte ich alle Muster finden, die aus mindestens 2 Spalten und mindestens 2 Zeilen bestehen. Das Problem liegt nahe bei cliques in a graph.

Im Beispiel unten stellen grüne Zellen "echte" Bits dar, Graustufen sind "falsch". Muster 1 enthält Spalten 1, 3, 4 und 5 und Zeilen 1 und 2. Muster 2 enthält nur Spalten 2 und 4 und Zeilen 2, 3, 4.

Geschäftsidee dahinter findet Ähnlichkeit Muster unter den verschiedenen Gruppen von Nutzern sozialer Netzwerke. In der realen Welt kann die Anzahl der Zeilen bis zu 3E7 und die Anzahl der Spalten bis zu 300 reichen.

Kann nicht wirklich eine Lösung außer Brute-Force-Matching herausfinden.

Bitte geben Sie den richtigen Namen des Problems an, damit ich mehr lesen oder eine elegante Lösung empfehlen kann.

Answer 1

Dies ist (äquivalent) für alle bicliques (komplette zweiteilige Teilgraphen) größer als eine bestimmte Größe in einem zweiteiligen Graphen. Hier sind die Zeilen die Eckpunkte von einem Teil A des Graphen, und die Spalten sind die Eckpunkte des anderen Teils B, und es gibt eine Kante zwischen u \ in A und v \ in B immer dann, wenn die Zelle in Zeile u, Spalte v ist grün.

Obwohl Sie sagen, dass Sie alle Muster finden möchten, möchten Sie wahrscheinlich nur maximale diejenigen finden, die nicht erweitert werden können, um größere Muster durch Hinzufügen von mehr Zeilen oder Spalten zu werden. (Andernfalls erhalten Sie für jedes Muster mit c> = 2 Spalten und r> = 3 Zeilen auch die mehr als 2^(c-2) * 2^(r-3) nicht-maximalen Muster, die gebildet werden können durch Löschen einiger Zeilen oder Spalten.)

Aber selbst die Auflistung nur der maximalen Muster kann exponentiell in der Anzahl der Zeilen und Spalten sein, unter der Annahme, dass P! = NP. Das ist, weil das Problem der Suche nach einem Maximum (dh größtmöglichen) Muster, in Bezug auf die Gesamtzahl der grünen Zellen, has been proven to be NP-complete: wenn es möglich wäre, alle maximalen Muster in polynomieller Zeit aufzulisten, dann könnten wir es einfach tun, und wähle den größten und lösche damit dieses NP-vollständige Problem in Polynomialzeit.