如何在布尔数组中找到模式组？

Question

如何在布尔数组中找到模式组？

arraysalgorithmpattern-matchingnpclique

7

给定一个布尔值的二维数组，我想要找到至少由两列和两行组成的所有模式。这个问题与在图中找到团有些相似。

在下面的示例中，绿色单元格表示“true”位，灰色单元格表示“false”。模式1包含列1、3、4和5以及行1和2。模式2仅包含列2和4，以及行2、3、4。

example

这个业务的想法是在各种社交网络用户群体中找到相似模式。在现实世界中，行数可以高达3E7，列数可以高达300。

除了蛮力匹配，确实找不出其他解决方案。

请建议问题的正确名称，以便我能够阅读更多信息，或者提供一种优雅的解决方案。

- Serge

1

如果数组对称，并且所有对角线条目都为true，则必须查找对应于图中clique的对称全真子数组。由于确定最大clique（或补集中的最大独立集）是NP难问题，因此该问题也是NP难问题。这并不意味着它在实践中不能完成，但它表明您应提供有关数组特定信息而不是希望获得快速通用算法。 - Douglas Zare

@DouglasZare，感谢您的评论。数组不对称。行代表用户，位表示独立属性，这些属性因研究而异。例如，b1“拥有高等教育”，b2“喜欢页面X”，b3“喜欢页面Y”等。JuanLopes，通过“模式”，我指的是适用于超过2个用户的多个“on”列的集合。 - Serge

1

是的，我明白你的数组不对称。然而，如果有一个快速、通用的算法，它也适用于对称矩阵，因此它将能够快速解决NP难问题。这是一个重要的提示，表明你不会找到一个快速、通用的算法，你需要使用特定矩阵的属性。例如，也许你知道每一行只包含少量真实值，或者除了少数之外都是如此。像这样的东西可能被一个算法所利用，这个算法对于你的问题来说是快速的，同时不必快速解决NP难问题。 - Douglas Zare

1

@AlexandruBarbarosie：非常遗憾，它比O(n^3)更糟糕，因为您必须考虑行（和列）的所有子集。将某些行添加到解决方案中可以减少其包含的列集，反之亦然，因此贪婪算法不起作用。 - j_random_hacker

@Serge：我只是粗略地浏览了那篇论文，但他们谈到了一种具有二次“延迟”的算法——这意味着生成下一个最大模式需要O(n^2)的时间，而不是所有的最大模式（我确信有些图族的双团数量渐进地超过O(n^2)，如果是真的，那么生成它们所需的时间是不可能是O(n^2)）。 - j_random_hacker

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

这相当于在二分图中查找所有大于某个大小的bicliques（完全二分子图）。这里的行是图的一部分A的顶点，列是另一部分B的顶点，并且当行u、列v处的单元格为绿色时，u \in A和v \in B之间存在一条边。

尽管您要查找所有模式，但您可能只想找到最大的模式——也就是说，不能通过添加更多行或列来扩展成更大模式的模式。（否则，对于任何具有c >= 2列和r >= 3行的模式，您还将得到超过2 ^（c-2）* 2 ^（r-3）个非最大模式，可以通过删除某些行或列来形成。）

但即使仅列出最大模式，也可能需要指数级时间才能完成，假设P != NP。这是因为在绿色单元格总数方面找到最大（即最大可能的）模式的问题已被证明是NP完全问题：如果有可能在多项式时间内列出所有最大模式，则我们可以简单地这样做并选择最大的，从而在多项式时间内解决这个NP完全问题。