在C++ Eigen中高效查找三个密集矩阵向量的首个全零索引

我需要处理一个N×N的非负Eigen::MatrixXi矩阵cost_matrix，以及两个N×1的非负Eigen::VectorXi向量rowVector和colVector，目标是找到第一个索引(i,j)，使得以下三个条件同时成立：

• cost_matrix(i,j) == 0
• rowVector(i) == 0
• colVector(j) == 0

暴力遍历的时间复杂度是O(N²)，对于大矩阵效率太低，希望用Eigen的向量化特性实现最高效的解法。以下是优化后的代码示例（预期结果为i=1、j=2）：

#include <Eigen/Dense>
#include <iostream>

int main() {
    Eigen::MatrixXi cost_matrix(4,4);
    cost_matrix << 1, 2, 3, 0, 
                   5, 0, 0, 8,
                   9, 8, 7, 6,
                   0, 2, 1, 5;
    Eigen::VectorXi rowCover(4);
    Eigen::VectorXi colCover(4);
    rowCover << 0, 0, 1, 1;
    colCover << 1, 1, 0, 1;

    // 构造临时矩阵：仅当三个值都为0时，临时矩阵对应位置才为0，否则为正数
    Eigen::MatrixXi temp = cost_matrix;
    temp.colwise() += rowCover;
    temp.rowwise() += colCover.transpose();

    // 寻找第一个0元素的位置
    Eigen::Index zeroRow, zeroCol;
    // 转置后按列优先查找，等价于原矩阵行优先遍历找首个匹配
    temp.transpose().minCoeff(&zeroCol, &zeroRow);

    int i = zeroRow;
    int j = zeroCol;

    std::cout << "找到的索引：i=" << i << ", j=" << j << std::endl;
    // 预期输出：找到的索引：i=1, j=2
    return 0;
}

实现思路说明 #

1. 构造临时矩阵：利用Eigen的向量化广播操作，将rowVector加到cost_matrix的每一列，colVector的转置加到每一行。由于所有输入都是非负的，只有当cost_matrix(i,j)、rowVector(i)、colVector(j)全部为0时，临时矩阵的(i,j)位置才会是0，其他位置的值都是正数。
2. 查找首个0元素：通过minCoeff方法找到临时矩阵中的最小值（即0）的位置。对临时矩阵转置后调用minCoeff，是因为Eigen默认按列优先存储，转置后查找等价于在原矩阵中按行优先顺序寻找首个符合条件的索引，符合常规的"首个"遍历逻辑。

效率优势 #

这种方法完全利用Eigen的底层向量化优化，避免了手动循环的开销，时间复杂度仍为O(N²)，但实际运行效率远高于手动遍历，尤其是当N较大时，向量化操作能充分利用CPU的SIMD指令集。

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