图松弛二分维度简单场景的快速近似算法技术问询

问题背景与需求 #

给定规模可达10^4×104的近似对称布尔方阵M，其中True代表物流场景中未计算的点对距离。需找到数量最少的子矩阵集合，覆盖所有True值（允许少量False值被误覆盖）。子矩阵由任意行/列索引集合定义（无需连续、可相交），目标是最小化子矩阵数量，同时避免过度计算，兼容模式化和随机数据场景。该问题属于二分图维度问题，为NP难，需高效近似算法。

核心算法思路 #

• 聚类预处理+贪心最大覆盖
  1. 行/列快速聚类：基于Jaccard相似度对行向量做轻量聚类，将高度相似的行归为同一组；利用矩阵近似对称特性，直接复用行聚类结果到列，减少计算量。聚类时采用采样优化——每行仅与随机选取的50-100行计算相似度，避免O(N²)的高复杂度。
  2. 贪心选最优子矩阵：每次从聚类组中选取能覆盖最多未标记True值的行组+列组组合作为子矩阵，标记已覆盖的True；当剩余True值分散时，切换为选取单个True的小邻域子矩阵（避免生成大量单元素子矩阵）。
• 动态松弛阈值控制
  引入可配置的True覆盖率阈值（覆盖的True数/子矩阵总元素数），候选子矩阵达标即可选中。模式化数据场景下调低阈值（如85%）以减少子矩阵数量；随机数据场景下调高阈值（如95%）控制误覆盖的False数量。
• 对称矩阵专属优化
  仅处理矩阵的上三角（或下三角）区域，生成的子矩阵自动镜像到对称区域，直接将计算规模减半，大幅提升效率。

算法特性说明 #

• 时间效率：聚类阶段复杂度为O(Nk)（k为采样行数，取50-100），贪心阶段复杂度为O(K*N)（K为最终子矩阵数量，远小于N），可高效处理10^4级别的矩阵。
• 覆盖质量：通过动态阈值平衡子矩阵数量与误覆盖率，模式化数据下能将子矩阵数量压缩至理想规模，随机数据下误覆盖的False数可控在设定范围内。
• 场景兼容性：既适配存在明显子矩阵模式的数据集，也能处理True值随机分散的场景，不会因数据分布变化出现性能或效果骤降。

内容的提问来源于stack exchange，提问作者Dimitrius