如何在布尔数组中找到模式组？
给定一个布尔值的二维数组，我想查找所有由至少2列和至少2行组成的模式。 这个问题有点接近于在图中找到派系。
在下面的例子中，绿色单元表示“真”位，灰色是“假”。 模式1包含列1,3,4和5以及行1和2.模式2仅包含列2和列4以及行2,3,4。
这背后的商业理念是发现各种社交网络用户群体之间的相似模式。 在现实世界中，行数可以达到3E7，并且列数可以达到300。
除了蛮力匹配以外，无法真正找出解决方案。
请指出问题的正确名称，以便我可以阅读更多内容，或者给出一个优雅的解决方案。
这是（相当于）在双向图中要求大于特定大小的所有biclique（完全二部分子图）。 在这里，行是图的一个部分A的顶点，列是另一个部分B的顶点，并且每当行u，列v处的单元在A中的u 和B中的v 之间存在边是绿色的。
虽然你说你想查找所有模式，但你可能只想找到最大的模式 - 也就是说，通过添加更多的行或列，无法扩展为更大模式的模式。 （否则，对于c> = 2列且r> = 3行的任何模式，您还将返回超过2 ^（c-2）* 2 ^（r-3）个可形成的非最大模式通过删除一些行或列。）
但是，即使列出最大模式，假设P！= NP，也可以在行数和列数上花费时间指数。 这是因为根据绿色细胞总数找到最大（即最大可能）模式的问题已被证明是NP完全的：如果可以在多项式时间中列出所有最大模式，那么我们可以简单地这样做，并选择最大的，从而在多项式时间内解决这个NP完全问题。
链接地址: http://www.djcxy.com/p/84779.html