Ánh xạ một tập hợp các điểm 3D đến một tập hợp khác với tổng số khoảng cách tối thiểu

Question

Được cho là hai tập hợp các điểm ba chiều, một nguồn và một bộ đích. Số điểm trên mỗi bộ là tùy ý (có thể bằng không). Nhiệm vụ là gán một hoặc không có điểm nguồn cho tất cả các điểm đích, sao cho tổng của tất cả các khoảng cách là tối thiểu. Nếu có nhiều nguồn hơn điểm đích, các điểm bổ sung sẽ bị bỏ qua.

Có giải pháp hiệu quả cho vấn đề này, nhưng vì số điểm có thể lớn, nên không khả thi. Tôi nghe nói vấn đề này là dễ dàng trong 2D với kích thước thiết lập bằng nhau, nhưng thật đáng buồn những điều kiện tiên quyết không được đưa ra ở đây.

Tôi quan tâm đến cả hai phép tính xấp xỉ và chính xác.

Chỉnh sửa: Haha, có, tôi cho rằng nó có vẻ giống như bài tập về nhà. Trên thực tế, nó không phải. Tôi đang viết một chương trình nhận vị trí của một số lượng lớn ô tô và tôi đang cố gắng ánh xạ chúng tới các ô đỗ xe tương ứng. :)

Answer 1

Tắt đầu của tôi, sắp xếp không gian tiếp theo là mô phỏng ủ.

Lưới không gian & sắp xếp các bộ thành các ô không gian.

Giải quyết sự cố O (NM) trong mỗi ô, sau đó trong vùng lân cận ô, v.v. để có được kết quả thử nghiệm.

Cuối cùng, chạy rất nhiều chu kỳ ủ mô phỏng, trong đó bạn thay đổi ngẫu nhiên các trận đấu để khám phá không gian gần đó.

Đây là phỏng đoán, giúp bạn có được câu trả lời tốt mặc dù không nhất thiết phải là câu trả lời tốt nhất, và nó sẽ khá hiệu quả do sắp xếp lưới ban đầu.

Answer 2

Mặc dù tôi không thực sự có câu trả lời cho câu hỏi của bạn, tôi có thể đề xuất xem xét các chủ đề sau. (Tôi biết rất ít về vấn đề này, nhưng gặp nó trước đây trên Stack Overflow.)

• Nearest Neighbour Search
• kd-tree

Hope this helps một chút.

Answer 3

Một cách để bạn có thể tiếp cận vấn đề này là để điều trị được như vấn đề chuyển nhượng cổ điển: http://en.wikipedia.org/wiki/Assignment_problem

Bạn đối xử với các điểm như các đỉnh của đồ thị, và trọng lượng của các cạnh là khoảng cách giữa các điểm. Bởi vì các thuật toán nhanh nhất cho rằng bạn đang tìm kiếm cho phù hợp tối đa (và không phải tối thiểu như trong trường hợp của bạn), và trọng lượng là không âm, bạn có thể xác định lại trọng lượng là ví dụ:

weight(A, B) = bigNumber- distance(A,B) 

nơi bigNumber lớn hơn khoảng cách dài nhất của bạn.

Rõ ràng là bạn kết thúc bằng biểu đồ hai chân. Sau đó, bạn sử dụng một trong các thuật toán chuẩn để đối sánh hai bên trọng số tối đa (nhiều tài nguyên trên web, ví dụ: http://valis.cs.uiuc.edu/~sariel/teach/courses/473/notes/27_matchings_notes.pdf hoặc Wikipedia để xem tổng quan: http://en.wikipedia.org/wiki/Perfect_matching#Maximum_bipartite_matchings) Bằng cách này bạn sẽ kết thúc với một thuật toán O (NM max (N, M)) , trong đó N và M là kích thước của các tập hợp các điểm của bạn.