获取从矩阵最小值和索引而不重复指数C++

Question

我有一个vector< vector <int> >矩阵大小为n的和我想要得到的最小值对于每个i和其指数法[i] [j]，并把它在载体上，但我不想重复任何索引。

我已经找到了一种理论的方式，但我不能在代码中写。

请2个矢量ù←{1，...，N}，L←{1，...，N}
重复n次

• BE（U，L）∈U× L从矩阵[u，l]≤矩阵[i，j]，∀i∈U，∀j∈L
• S [u]←l
• Do U←U- {u} y L←L- {l}

Answer 1

您可以直接对此算法进行编码

typedef vector<vector<int>> Matrix; 
typedef pair<size_t, size_t> Index; 
typedef vector<Index> IndexList; 

IndexList MinimalSequence(const Matrix& matrix) { 
    IndexList result; 

    set<size_t> U, L; 
    for (size_t i = 0; i < matrix.size(); ++i) { // consider square 
     U.insert(i); 
     L.insert(i); 
    } 

    while (U.size()) { // same as L.size() 
     int min = numeric_limits<int>::max(); 
     Index minIndex; 
     for (auto u: U) 
      for (auto l: L) 
       if (matrix[u][l] < min) { 
        minIndex = make_pair(u, l); 
        min = matrix[u][l]; 
       } 

     U.erase(minIndex.first); 
     L.erase(minIndex.second); 
     result.push_back(minIndex); 
    } 

    return result; 
} 

也是你的问题是不能以这种方式清楚：你想从矩阵的整体最小的元素开始（如您的公式说的），然后移动到下一个最小？ 还是你想从左到右移动列？我根据公式实施它。

注意，在公式中设置非负整数的是set<size_t>上插入（）和删除（）可供选择。对于所有的while循环

我也建议尝试替代算法 - 由有相应的值进行排序矩阵指数列表，然后迭代它删除您不想再索引。

编辑：代码实际上不同于算法在几个方面是精确的。这似乎更实际。重复

• 过程，直到一套指标用完的 - 这等于n
• 回报结构是2D指数列表和编码比阵列

更多信息

Answer 2

您已经接受了答案，但是你不是面临可以使用Hugarian algorithm解决的Assignment problem，也许更有效的算法存在并已实施？