我有一个非常大的 N x P 二进制矩阵，我想找到两个集合 R 和 C，其中包含构成最大可能密集(非稀疏，由只有 1's) 子矩阵，它至少满足 |R| 的特定大小和|C|。索引不一定是连续的。例如，对于最小值 |R|=3 |C|=2，对于下面的矩阵，我想输出 R = {1,2,3} C = {2,5}。
0 1 1 0 1
1 1 0 1 1
0 1 0 1 1
有什么好的算法可以做到这一点吗？
我的一个想法是将其建模为优化问题，我不知道这样的问题是否可以用 AMPL 编写以与任何开源求解器一起使用，例如，类似的东西(不确定如何准确表述):
但我怀疑它是 NP 困难的或者需要幂集搜索。或者这个问题也可以被看作是一个邻接矩阵并试图找到一个最大集团？欢迎任何想法!
最佳答案
我最终意识到这个问题可以重新表述为二分图，然后最大尺寸子矩阵就相当于二分图中的最大边biclique，这是一个NP完全问题。我在R包中找到了BiMax实现biclust很有用!
关于algorithm - 在大型稀疏矩阵中查找大型非稀疏子矩阵，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28974240/