CODEWITHSUNDEEP
c++arraysalgorithmsorting
hyperknot
hyperknot

Reputation: 13966

Selecting shortest distance between pairs of elements

I would like to solve the following problem in C++:

I have 6 elements: A1, A2, A3, B1, B2, B3. I would like to match exactly one B to exactly one A, in such a way that the sum of the resulting matches is the smallest.

Here is how I thought about writing a simple greedy algorithm (might not be optimal, but seems good enough for me):

  1. Measure the distance between all A-B pairs, save it in an 2D array of floats.
  2. Sort the 2D array as individual values, something like the sort lambda below:
  3. Set the best match for that A, disable searching for the selected B and A (disable a column and a row in 2D).
  4. Select the smallest number from the still available array.
  5. etc. etc, till all matches are made.

There are two interesting questions here:

  1. Can you tell me how is this problem called, and point me to some proper solutions to it, in case they exists?

  2. Can you tell me how would you implement the above greedy algorithm in C++? So far I thought about using this function to sort

Here is the code:

float centerDistances[3][3]; // .. random distances

vector<int> idx(9);

for (size_t i = 0; i != idx.size(); ++i) idx[i] = i;
sort(idx.begin(), idx.end(), [](int i1, int i2) 
{
    return centerDistances[0][i1] < centerDistances[0][i2];
});

And I think I'd keep a vector<bool> selectedA, selectedB; to keep track of selected elements, but I don't know how well it'd be.

Note: OK, there is no point talking about performance for 3,3 elements, but I'd be really interested in the real solution to this problem, when the number of elements is much larger.

Upvotes: 5

Views: 826

Answers (1)

justhalf
justhalf

Reputation: 9107

This is called Maximum Cost Bipartite Matching, and the most general algorithm for it is Bellman-Ford Algorithm (you can convert your distance to negative to make the algorithm directly applicable)

You can also use Hungarian Algorithm, which is actually assignment problem, by defining the A vertices as workers and B vertices as tasks, and putting the distance in the cost matrix.

EDIT:

For simple method (like your 3-element case), you can consider complete search. This is because we can consider your n x n distance matrix as a board, and we need to select n squares, such that each row and each column has exactly one selected square.

float cost[n][n];
bool[n] used;

float solve(int row){
    float min = 999999; // Put a very large number here
    for(int i=0; i < n; i++){
        if(!used[i]){
            used[i] = 1;
            if(i==n-1){
                return cost[row][i];
            } else {
                float total = cost[row][i]+solve(row+1);
                if(total<min) min=total;
            }
            used[i] = 0;
        }
    }
    return min;
}

int main(){
    printf("%.2f\n",solve(0));
}

The complexity is n^n, so this only works for n <= 8.

Upvotes: 5

Related Questions