Dường như bạn đang tìm kiếm Minimum weight perfect matching.
Có các thuật toán để khai thác thực tế rằng đây là những điểm trong mặt phẳng. Bài báo này: Mincost Perfect Matching in the Plane có một thuật toán và cũng đề cập đến một số công việc trước đó trên đó.
Khi được yêu cầu, đây là mô tả ngắn gọn về thuật toán "đơn giản" cho đối sánh tối thiểu có trọng số tối ưu trong biểu đồ. Đây là một bản tóm tắt ngắn về các phần của chương về kết hợp có trọng số trong sách Tối ưu hóa kết hợp, Thuật toán và Độ phức tạp bởi Papadimitriou & Steiglitz.
Giả sử bạn được cung cấp biểu đồ không có trọng số G (với số lượng nút bằng nhau). Biểu đồ có thể được coi là biểu đồ có trọng số hoàn chỉnh, bằng cách thêm các cạnh bị thiếu và gán cho chúng trọng số rất lớn.
Giả sử các đỉnh được dán nhãn 1 đến n và trọng số cạnh giữa các đỉnh i và j là c (i, j).
Chúng ta có n (n-1)/2 biến x (i, j) biểu thị sự khớp với G. x (i, j) = 1 nếu cạnh giữa i và j nằm trong khớp và x (i, j) = 0 nếu không.
Bây giờ vấn đề phù hợp có thể được viết như các vấn đề Lập trình tuyến tính:
giảm thiểu Sum c (i, j) * x (i, j)
tùy thuộc vào điều kiện là
Tổng x (1, j) = 1, trong đó j dao động từ 1 đến n.
Tổng x (2, j) = 1, trong đó j dao động từ 1 đến n. . . .
Tổng x (n, j) = 1, trong đó j dao động từ 1 đến n.
(Sum x (1, j) = 1 về cơ bản có nghĩa là chúng ta đang lựa chọn chính xác một sự cố mép đỉnh nhãn 1.)
Và điều kiện cuối cùng mà
x (i, j)> = 0
(chúng ta có thể nói x (i, j) = 0 hoặc 1, nhưng điều đó sẽ không làm cho này một Lập trình vấn đề tuyến tính như những hạn chế là một trong hai phương trình tuyến tính hoặc bất bình đẳng)
Có một phương pháp được gọi là phương pháp Simplex có thể giải quyết vấn đề Lập trình tuyến tính này để đưa ra một giải pháp tối ưu trong thời gian đa thức về số lượng các biến. Bây giờ, nếu G là bipartite, nó có thể được hiển thị rằng chúng ta có thể có được một giải pháp tối ưu sao cho x (i, j) = 0 hoặc 1. Do đó bằng cách giải quyết vấn đề lập trình tuyến tính này cho một đồ thị hai bên, chúng ta có được một thiết lập các nhiệm vụ cho mỗi x (i, j), mỗi là 0 hoặc 1. Bây giờ chúng ta có thể có được một kết hợp bằng cách chọn các cạnh (i, j) mà x (i, j) = 1. Các ràng buộc đảm bảo rằng nó sẽ phù hợp với trọng lượng nhỏ nhất.
Thật không may, điều này không đúng đối với đồ thị chung (tức là x (i, j) là 0 hoặc 1). Edmonds đã tìm ra rằng điều này là do sự hiện diện của các chu kỳ kỳ lạ trong biểu đồ.
Vì vậy, ngoài các contraints trên, Edmonds thêm các hạn chế bổ sung mà trong bất kỳ tập hợp con của các đỉnh của kích thước 2k + 1 (tức là kích thước lẻ), số cạnh phù hợp là không quá k
liệt kê mỗi tập con lẻ của các đỉnh để lấy danh sách các bộ S (1), S (2), ..., S (2^n - n). Hãy kích thước của S (r) là 2 * s (r) + 1.
Sau đó, những hạn chế trên là, đối với mỗi tập S (r)
Sum x (i, j) + y (r) = s (r), đối với i, j trong S (r).
Edmonds sau đó chứng minh rằng điều này là đủ để đảm bảo rằng mỗi x (i, j) là 0 hoặc 1, do đó cho chúng ta một trọng lượng tối thiểu phù hợp hoàn hảo.
Thật không may, bây giờ số lượng biến đã trở thành theo cấp số nhân. Vì vậy, các thuật toán simplex, nếu chỉ chạy trên này như nó được, sẽ dẫn đến một thuật toán thời gian mũ.
Để vượt qua điều này, Edmonds xem xét vấn đề lập trình tuyến tính kép (tôi sẽ không đi sâu vào chi tiết ở đây), và cho thấy thuật toán nhị phân kép khi chạy trên hệ thống chỉ mất các bước O (n^4) để đạt được một giải pháp, do đó cho chúng ta một thuật toán thời gian đa thức! Ông cho thấy điều này bằng cách chỉ ra rằng tại hầu hết O (n) của y (r) là khác không ở bất kỳ bước nào của thuật toán (mà ông gọi là hoa).
Đây là liên kết nên giải thích chi tiết hơn một chút: http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.pdf, Phần 2.
Cuốn sách tôi đã đề cập trước đây đáng đọc (mặc dù nó có thể hơi khô) để hiểu sâu hơn.
Phew. Hy vọng rằng sẽ giúp!
Điều này được gọi là vấn đề người bán hàng du lịch. –
Không, điều đó khác với TSP. Nhưng nhìn vào TSP có thể là một điểm tốt để bắt đầu. –
@Doc Brown: Hãy khai sáng cho tôi :) –