正如@chtz已经在评论中建议的那样，Eigen不会真正帮助你。我们仍然可以尝试找到一个更快的版本。
这是我的想法：
首先，我扩展/修复您的代码，以获得一个工作的引用实现。

/**
 * Reference implementation
 * 
 * Finds lowest row and column (prioritizes low row number)
 * where cost_matrix is zero and both row_cover and col_cover are zero
 * 
 * Returns {-1, -1} if no result is found.
 * The input arrays can be overwritten by the implementation as desired
 */
std::pair<int, int> reference(
      Eigen::MatrixXi& cost_matrix,
      Eigen::VectorXi& row_cover,
      Eigen::VectorXi& col_cover) noexcept
{
    int i, j;
    cost_matrix.colwise() += row_cover;
    cost_matrix.rowwise() += col_cover.transpose();
    Eigen::Index zeroRow, zeroCol;
    int min = cost_matrix.transpose().minCoeff(&zeroCol, &zeroRow);
    i = zeroRow;
    j = zeroCol;
    if(min) // no result found
        return {-1, -1};
    return {i, j};
}

字符串
遍历整个输入矩阵似乎是非常浪费的，除非覆盖向量通常为零而输入矩阵不是。如果覆盖包含许多非零元素，最好将它们转换为零索引的向量。

/**
 * Overwrite the front of cover with indices where it was zero
 * 
 * The return value gives the total number of zeros found.
 * The values behind that are left in undefined state
 */
static Eigen::Index to_zero_indices(Eigen::VectorXi& cover) noexcept
{
    Eigen::Index outpos = 0;
    for(Eigen::Index i = 0, n = cover.size(); i < n; ++i) {
        /* Loop body is written to be branchless */
        int value = cover[i];
        cover[outpos] = static_cast<int>(i);
        outpos += ! value;
    }
    return outpos;
}

型
现在我们只需要检查矩阵中两个覆盖都为零的条目。

/**
 * Alternative implementation based on sparse probing of the cost matrix
 * 
 * API-compatible to reference but in practice changes the cover vectors,
 * not the cost matrix
 */
std::pair<int, int> probe_indices(
      Eigen::MatrixXi& cost_matrix,
      Eigen::VectorXi& row_cover,
      Eigen::VectorXi& col_cover) noexcept
{
    const Eigen::Index rows_n = to_zero_indices(row_cover);
    const Eigen::Index cols_n = to_zero_indices(col_cover);
    for(int i: row_cover.head(rows_n))
        for(int j: col_cover.head(cols_n))
            if(! cost_matrix(i, j))
                return {i, j};
    return {-1, -1};
}

型
为了获得最佳结果，请使用-DNDEBUG编译，以避免在各种索引操作中进行范围检查。

测试

矩阵大小N大约是20，但是它每帧会运行很多次。0的间隔大约是1/N（可能每行几个0）
我假设这个1/N不适用于覆盖向量。否则你找到一个条目的机会很低。我随意决定用4/N测试覆盖矩阵，用1/N测试成本矩阵。
完整的测试和基准测试结果如下所示。在我的系统上，我的版本在所选参数集下的速度大约是10倍，即使我将cover更改为全零，它也快了7.5倍。即使在绝对最坏的情况下-cover全零，matrix全一-它仍然快了两倍。

#include <Eigen/Dense>

#include <chrono>
#include <iostream>
#include <random>
// using std::default_random_engine, std::bernoulli_distribution
#include <utility>
// using std::pair

/**
 * Fill the output with zeros and ones depending on the percentage
 *
 * Results are random but reproducible across process executions.
 * Input percentage is expected to be between 0 and 1
 */
void fill_pct(Eigen::Ref<Eigen::MatrixXi> out, double pct_ones)
{
    static std::default_random_engine::result_type seed = 0xdeadbeef;
    std::default_random_engine rng {seed++};
    std::bernoulli_distribution distr {pct_ones};
    out = Eigen::MatrixXi::NullaryExpr(
          out.rows(), out.cols(),
          [&]() -> int { return distr(rng); });
}
int main()
{
    using clock_t = std::chrono::steady_clock;
    const int size = 20;
    const double pct_zero = 1. / size;
    const double pct_zero_cover = 4. / size;
    const int repetitions = 1000000;
    Eigen::MatrixXi cost_matrix, matrix_copy;
    Eigen::VectorXi row_cover, col_cover, row_copy, col_copy;
    clock_t::duration reference_time {}, bench_time {};
    for(int i = 0; i < repetitions; ++i) {
        cost_matrix.resize(size, size);
        fill_pct(cost_matrix, 1. - pct_zero);
        matrix_copy = cost_matrix;
        for(Eigen::VectorXi* cover: {&row_cover, &col_cover}) {
            cover->resize(size);
            fill_pct(*cover, 1. - pct_zero_cover);
        }
        row_copy = row_cover;
        col_copy = col_cover;
        clock_t::time_point t1 = clock_t::now();
        std::pair<int, int> bench_result = probe_indices(
              cost_matrix, row_cover, col_cover);
        clock_t::time_point t2 = clock_t::now();
        std::pair<int, int> ref_result = reference(
              matrix_copy, row_copy, col_copy);
        clock_t::time_point t3 = clock_t::now();
        bench_time += t2 - t1;
        reference_time += t3 - t2;
        if(bench_result != ref_result)
            std::cout << bench_result.first << " != " << ref_result.first
                      << ' ' << bench_result.second << " != " << ref_result.second
                      << '\n';
    }
    using std::chrono::milliseconds;
    std::cout << "Reference " << std::chrono::duration_cast<milliseconds>(
                    reference_time).count() * 1e-3
              << "\nBench " << std::chrono::duration_cast<milliseconds>(
                    bench_time).count() * 1e-3
              << '\n';
}

型

更多要点

• 正如在评论中所讨论的，最好是转置输入，并在第一列上查找具有优先级的第一个条目。
• 我不认为显式向量化有多大意义，我觉得它可以用聚集指令来完成，但只有在覆盖为零的矩阵通常为非零的情况下才能真正起作用
• 在行覆盖和列覆盖大部分为零的情况下，我们可以反转逻辑并首先扫描矩阵。

附录：我对AVX 512的显式矢量化做了一些测试。首先，让to_zero_indices使用vpcompressd。这稍微快一点，但不值得。其次，我用一些矢量化扫描优化了上面最差的情况。在这种情况下，它使性能提高了一倍，但同时支持两种模式，并决定是使用扫描还是使用常规操作有足够的开销，使常规情况的速度降低了一半。所以没什么用。