Chọn khoảng cách ngắn nhất giữa các cặp thành phần

Question

Tôi muốn giải quyết vấn đề sau trong C++:

Tôi có 6 phần tử: A1, A2, A3, B1, B2, B3. Tôi muốn kết hợp chính xác một B với chính xác một A, theo cách mà tổng số kết quả phù hợp là nhỏ nhất.

Sau đây là cách tôi nghĩ về cách viết một thuật toán tham lam đơn giản (có thể không được tối ưu, nhưng dường như đủ tốt cho tôi):

1. Đo khoảng cách giữa tất cả các cặp AB, lưu nó trong một mảng 2D của nổi.
2. Sắp xếp mảng 2D thành các giá trị riêng lẻ, giống như lambda sắp xếp bên dưới:
3. Đặt kết quả phù hợp nhất cho A, tắt tìm kiếm B và A đã chọn (tắt cột và hàng 2D).
4. Chọn số nhỏ nhất từ ​​mảng vẫn có sẵn.
5. v.v., cho đến khi tất cả các kết quả phù hợp được thực hiện.

Có hai câu hỏi thú vị ở đây:

1. Bạn có thể cho tôi biết thế nào là vấn đề này được gọi là, và chỉ cho tôi một số giải pháp phù hợp với nó, trong trường hợp họ tồn tại?

2. Bạn có thể cho tôi biết cách bạn triển khai thuật toán tham lam ở trên trong C++? Cho đến nay tôi nghĩ về việc sử dụng chức năng này để sắp xếp

Đây là mã:

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

Và tôi nghĩ rằng tôi muốn giữ một vector<bool> selectedA, selectedB; để theo dõi các yếu tố được lựa chọn, nhưng tôi không biết nó sẽ như thế nào.

Lưu ý: OK, không có điểm nói về hiệu suất cho 3,3 phần tử, nhưng tôi thực sự quan tâm đến giải pháp thực sự cho vấn đề này, khi số lượng phần tử lớn hơn nhiều.

Answer 1

này được gọi là chi phí tối đa khớp song phương, và các thuật toán tổng quát nhất cho nó là Bellman-Ford Algorithm (bạn có thể chuyển đổi khoảng cách của bạn để tiêu cực để làm cho các thuật toán được áp dụng trực tiếp)

Bạn cũng có thể sử dụng Hungarian Algorithm, mà thực sự là nhiệm vụ vấn đề, bằng cách xác định A đỉnh như công nhân và B đỉnh như nhiệm vụ, và đưa khoảng cách trong ma trận chi phí.

EDIT:

Đối với phương pháp đơn giản (như trường hợp 3 phần tử), bạn có thể xem xét tìm kiếm hoàn chỉnh. Điều này là do chúng ta có thể xem xét ma trận khoảng cách n x n của bạn như một bảng, và chúng ta cần phải chọn n hình vuông, sao cho mỗi hàng và mỗi cột có chính xác một ô được chọn.

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

Sự phức tạp là n^n, vì vậy đây chỉ làm việc cho n < = 8.