獲得2組點之間的最近對最佳組合

我不得不點的集合，可以說設置A和B獲得2組點之間的最近對最佳組合

A和B是在大小
A的每一個元件被耦合等於到B的元素

所有A的點以「搬」到B的點，但B的點不能連接到A的多點

我需要找到最佳組合，其中t他總（步行）距離（從每對之間的距離加起來的）是最小的。

我在Java中製成的示例用於演示目的（目前暴力破解每個可能的組合，並檢查具有最小總距離）

實施例1

Example img 1

實施例2

Example img 2

綠色矩形代表集合A中的一個點，青色矩形代表集合B中的一個點，忽略橙色方塊

我將如何處理此問題？

來源

2015-10-21 Bram

，以提高這是一個assignment problem，它可以是解決於O（n³）時間由Hungarian algorithm。找到源代碼或自己實現它不應該太難。

來源

2015-10-22 08:14:23

loop over A points 
    find closest B point NOT already connected to A point

這將給以最小的處理時間的體面的原料液

如果你有剩餘的一些額外的時間，然後試圖通過

loop over connections 
    loop over connections with index greater then selected in previous loop 
     sum total length of two connections 
     swap connection pairs 
     sum total length of swapped connections 
     if swap is less 
     replace original with swapped 
     if reached time budget 
     end

來源

2015-10-21 16:28:40 ravenspoint

獲得2組點之間的最近對最佳組合

回答

相關問題