Wybór najkrótszej odległości między parami elementów

Question

Chciałbym rozwiązać następujący problem w C++:

Mam 6 elementów: A1, A2, A3, B1, B2, B3. Chciałbym dopasować dokładnie jeden B do dokładnie jednego A, w taki sposób, aby suma wynikowych dopasowań była najmniejsza.

Oto jak myślałem o pisaniu prosty chciwy algorytm (może nie być optymalna, ale wydaje się wystarczająco dobre dla mnie):

1. Zmierz odległość między wszystkimi parami AB, zapisać go w tablicy 2D pływa.
2. Posortuj tablicę 2D jako pojedyncze wartości, podobnie jak rodzaj lambda poniżej:
3. Ustaw najlepsze dopasowanie dla tego A, wyłącz wyszukiwanie odpowiednich B i A (wyłącz kolumnę i wiersz w 2D).
4. Wybierz najmniejszą liczbę z wciąż dostępnej tablicy.
5. itd. Itd., Dopóki nie zostaną wykonane wszystkie mecze.

Istnieją dwa interesujące pytania tutaj:

1. Może mi pan powiedzieć, jak się nazywa ten problem i wskazać mi niektórych odpowiednich rozwiązań do niej, w przypadku gdy istnieje?

2. Czy możesz mi powiedzieć, jak zaimplementowałeś powyższy chciwy algorytm w C++? Do tej pory myślałem o użyciu tej funkcji można sortować

Oto kod:

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]; 
}); 

I myślę, że zachowa vector<bool> selectedA, selectedB; śledzić wybranych elementów, ale ja nie wiem, jak dobrze by to było.

Uwaga: OK, nie ma sensu mówić o wydajności dla 3,3 elementów, ale byłbym naprawdę zainteresowany prawdziwym rozwiązaniem tego problemu, gdy liczba elementów jest znacznie większa.

Answer 1

To się nazywa Maksymalny koszt dwustronny Matching, a najbardziej ogólny algorytm dla niego jest Bellman-Ford Algorithm (można konwertować dystans do ujemnego, aby algorytm bezpośrednio dotyczy)

Można również użyć Hungarian Algorithm, która jest faktycznie przypisanie Problem polega na zdefiniowaniu wierzchołków A jako robotów i wierzchołków B jako zadań oraz umieszczeniu odległości w macierzy kosztów.

EDIT:

Dla prostej metody (jak Twoim przypadku 3-element), można rozważyć całkowite wyszukiwanie. Dzieje się tak dlatego, że możemy wziąć pod uwagę macierz odległości n x n jako planszę i musimy wybrać n kwadratów, tak aby każdy wiersz i każda kolumna miała dokładnie jeden wybrany kwadrat.

 
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)); 
} 

Złożoność jest n^n, więc to działa tylko dla n = < 8.