Jak znaleźć grupy wzorów w tablicy boolowskiej?

Question

Biorąc pod uwagę tablicę 2D wartości logicznych, chcę znaleźć wszystkie wzorce, które składają się z co najmniej 2 kolumn i co najmniej 2 rzędów. Problem jest nieco bliski znalezienia cliques in a graph.

W poniższym przykładzie zielone komórki reprezentują "prawdziwe" bity, szarości to "fałsz". Wzór 1 zawiera kols 1,3,4 i 5 oraz wiersze 1 i 2. Wzór 2 zawiera tylko kolumny 2 i 4 oraz wiersze 2,3,4.

firm Ideą jest znalezienie wzorów podobieństwa między różnymi grupami użytkowników sieci społecznych. W rzeczywistości liczba wierszy może wzrosnąć do 3E7, a liczba kolumn do 300.

Nie można znaleźć rozwiązania innego niż brutalne dopasowanie siły.

Proszę podać poprawną nazwę problemu, abym mógł przeczytać więcej lub doradzić eleganckie rozwiązanie.

Answer 1

To jest (odpowiednik) z prośbą o wszystkie bicliques (pełne, dwuczęściowe podgrafy) większe niż określony rozmiar na wykresie dwudzielnym. Tutaj wiersze są wierzchołkami jednej części A wykresu, a kolumny są wierzchołkami drugiej części B, a istnieje granica między u \ w A i v \ w B, gdy komórka w wierszu u, kolumna v jest zielony.

Chociaż można powiedzieć, że chcesz znaleźć wszystkie wzorce, prawdopodobnie chcesz tylko znaleźć tylko maksymalnych z nich - to znaczy, wzory, które nie mogą zostać rozszerzone, by stać się większe wzory dodając więcej wierszy lub kolumn. (W przeciwnym razie, dla dowolnego wzoru z c> = 2 kolumnami i r> = 3 wierszami, otrzymasz także więcej niż 2^(c-2) * 2^(r-3) nie-maksymalnych wzorów, które mogą być utworzone poprzez usunięcie niektórych wierszy lub kolumn.)

Jednak nawet wyliczenie tylko maksymalnych wzorców może zająć wykładniczy czas w liczbie wierszy i kolumn, przy założeniu, że P! = NP. To dlatego, że problem ze znalezieniem maksymalnego(tj. Największego możliwego) wzoru, pod względem całkowitej liczby zielonych komórek, has been proven to be NP-complete: gdyby możliwe było wylistowanie wszystkich maksymalnych wzorców w czasie wielomianowym, moglibyśmy po prostu to zrobić, i wybierz największy, rozwiązując w ten sposób problem NP-zupełny w czasie wielomianowym.