見つける一致が

Question

は、以下のように、私は、重複なしで、固有:: MatrixXf（4,5）を有すると言う：

a  b c  d  e 
A: 0.60 0.70 0.80 0.90 0.00 
B: 0.51 0.61 0.71 0.81 0.91 
C: 0.41 0.31 0.21 0.11 0.01 
D: 0.10 0.20 0.30 0.40 0.50 

Iは、（行（i）とカラムとの間の一致を見つける必要がありますj）は、（i）または（j）が1回だけ選択された値（i、j）が小さい（最小の最小値）1である。私の方法の

結果：

私の仕事はこれまでのところ、左上から右下に始まり、最低限の一致を検索する（ささいな）反復的なアプローチに私を導いた、私は、カップル(A,e =0.00) (B,a =0.51) (C,e =0.01) (D,a =0.10)を得ました。

a  b c  d  e 
A: 0.60 0.70 0.80 0.90 0.00 
          ^
B: 0.51 0.61 0.71 0.81 0.91 
    ^
C: 0.41 0.31 0.21 0.11 0.01 
          ^
D: 0.10 0.20 0.30 0.40 0.50 
    ^

は、あなたが見ることができるように、私は「E」を持って、「」望ましくない試合として二度選ばれ、それで結果

を募集しました。私の完璧なマッチは代わりに(A,e =0.00) (D,a =0.10) (C,d =0.11) (B,b =0.61)で、「c」は匹敵しません。

a  b c  d  e 
A: 0.60 0.70 0.80 0.90 0.00 
          ^
B: 0.51 0.61 0.71 0.81 0.91 
     ^
C: 0.41 0.31 0.21 0.11 0.01 
        ^
D: 0.10 0.20 0.30 0.40 0.50 
    ^

これを実行する方法が必要ですが、わかりませんでした。 あなたは各行のユニークな最小値を探している：

for (i = 0; i < Score.rows(); i++) 
{ 
    Correspondance correspondence; 
    correspondence.source = source[i]; 
    int idx = 0; 
    for (int j = 0; j < Score.cols(); j++) 
    { 
     if (Score(i, j) < Score(i, idx)) idx = j; 
    } 
    correspondence.target = target[idx]; 
    correspondences_.push_back(correspondence); 
} 

with Source [A, B, C, D] and target [a, b, c, d, e] 

Answer 1

私はちょっと挑戦しました。問題。 （C++ 11の機能を使用します）

#include <iostream> 
#include <vector> 
#include <tuple> 
#include <algorithm> 

double data[4][5] = { 
    { 0.60, 0.70, 0.80, 0.90, 0.00 }, 
    { 0.51, 0.61, 0.71, 0.81, 0.91 }, 
    { 0.41, 0.31, 0.21, 0.11, 0.01 }, 
    { 0.10, 0.20, 0.30, 0.40, 0.50 } }; 

struct Element 
{ 
    int x; 
    int y; 
    double value; 
}; 

std::vector<Element> find(double (&matrix)[4][5]) 
{ 
    std::vector<Element> elements; 
    std::vector<Element> matches; 

    // build vector of all elements 
    for (int i = 0; i < 4; i++) 
     for (int j = 0; j < 5; j++) 
      elements.push_back({i, j, matrix[i][j]}); 

    // sort all elements from smallest to largest 
    std::sort(elements.begin(), elements.end(), 
    [](const Element& a, const Element& b) 
    { 
     return a.value < b.value; 
    }); 

    while (!elements.empty()) 
    { 
     // pull out smallest value 
     Element smallest = elements[0]; 
     matches.push_back(smallest); 

     // remove all other elements in the same row or column 
     elements.erase(std::remove_if(elements.begin(), elements.end(), 
     [smallest](const Element& e) 
     { 
      return e.x == smallest.x || e.y == smallest.y; 
     }), elements.end()); 
    } 

    return matches; 
} 

int main() 
{ 
    auto matches = find(data); 

    // print values 
    for (auto match : matches) 
     std::cout << "(" << match.x 
        << "," << match.y 
        << " = " << match.value 
        << ")" << std::endl; 

    return 0; 
} 

Answer 2

は、ここで私は理解して何：

は、ここに私のコードです。最小値を順に（最小から最大まで）検索したいとします。

これは、現在行っているように行単位で検索することができないことを意味します。 ENTIREテーブルを4回検索して、各行の最小値を検索する必要があります。そして、何かがうまく見つかったら、見つかった行と列を取り除き、再び検索されないようにします。

私は既に見つかった行/列を取り除くための2つのアイデアが含まれています。以下のコードでOPTION 1とOPTION 2というラベルが付けられています。 ;）

//search for 4 values 
for (i = 0; i < Score.rows(); i++) 
{ 
    //search ALL rows 
    for (i = 0; i < Score.rows(); i++) 
    { 
     Correspondance correspondence; 
     correspondence.source = source[i]; 
     int idx = 0; 
     for (int j = 0; j < Score.cols(); j++) 
     { 
      //OPTION 1: Do something here to reject indexes from row/col that are already "found" 
      if (Score(i, j) < Score(i, idx)) idx = j; 
     }  
    } 
    //only record the answer after all rows are searched 
    //this is the global minimum value 
    correspondence.target = target[idx]; 
    correspondences_.push_back(correspondence); 
    //OPTION 2: Do something here to eliminate the row/cols that are already "found" so that they don't get searched again 
} 

P.S.私はC++の対応が分からないので、プッシュ/ポップがオプションの配列問題のように扱いました