Cách tìm các nhóm mẫu trong mảng boolean?

Question

Với mảng giá trị Boolean 2D, tôi muốn tìm tất cả các mẫu bao gồm ít nhất 2 cột và ít nhất 2 hàng. Vấn đề là hơi gần với việc tìm kiếm cliques in a graph.

Trong ví dụ bên dưới, các ô màu xanh lá cây đại diện cho các bit "đúng", màu xám là "sai". Mẫu 1 chứa cols 1,3,4 và 5 và hàng 1 và 2. Mẫu 2 chỉ chứa các cột 2 và 4 và các hàng 2,3,4.

Ý tưởng kinh doanh đằng sau điều này là tìm mẫu tương tự giữa các nhóm người dùng mạng xã hội khác nhau. Trong số hàng thực tế có thể lên đến 3E7 và số lượng cột tối đa 300.

Không thể thực sự tìm ra giải pháp khác ngoài kết hợp lực lượng vũ phu.

Vui lòng tư vấn tên riêng của sự cố, vì vậy tôi có thể đọc thêm hoặc tư vấn giải pháp thanh lịch.

Answer 1

Đây là (tương đương) yêu cầu tất cả bicliques (đồ thị con đa hướng hoàn chỉnh) lớn hơn một kích thước nhất định trong biểu đồ hai chân. Ở đây các hàng là các đỉnh của một phần A của biểu đồ, và các cột là đỉnh của phần B khác, và có một cạnh giữa u \ trong A và v \ trong B bất cứ khi nào ô ở hàng u, cột v có màu xanh lá cây.

Mặc dù bạn nói rằng bạn muốn tìm tất cả các mẫu, bạn có thể chỉ muốn tìm các mẫu tối đa - đó là các mẫu không thể mở rộng để trở thành các mẫu lớn hơn bằng cách thêm nhiều hàng hoặc cột hơn. (Nếu không, đối với bất kỳ mẫu nào có c> = 2 cột và r> = 3 hàng, bạn cũng sẽ lấy lại nhiều hơn 2^(c-2) * 2^(r-3) mẫu không tối đa có thể được tạo thành bằng cách xóa một số hàng hoặc cột.)

Nhưng thậm chí chỉ liệt kê các mẫu tối đa có thể mất thời gian theo số mũ của hàng và cột, giả sử rằng P! = NP. Đó là vì vấn đề tìm kiếm mẫu tối đa (tức là lớn nhất có thể), về tổng số ô xanh, has been proven to be NP-complete: nếu có thể liệt kê tất cả các mẫu tối đa trong thời gian đa thức, thì chúng ta có thể làm như vậy, và chọn lớn nhất, do đó giải quyết vấn đề NP-hoàn chỉnh này trong thời gian đa thức.