获得两组点之间最近对的最佳组合

Question

我必须设置点，假设设置 A 和 B

A 和 B 大小相等
A 的每个元素都耦合到 B 的一个元素

A的所有点都必须'move'到B的一个点，但B的一个点不能耦合到A的多个点

我需要找到最佳组合，其中总（步行）距离（从每对之间的距离相加）是最小的。

为了演示目的，我在 Java 中做了一个例子（目前暴力破解所有可能的组合并检查哪个具有最小的总距离）

示例 1

示例 2

绿色矩形代表集合 A 中的一个点，青色矩形代表集合 B 中的一个点，忽略橙色方块

我该如何处理？

Answer 1

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

Answer 2

这是一个assignment problem, which can be solved in O(n³) time by the Hungarian algorithm。找源码或者自己实现应该不难。

获得两组点之间最近对的最佳组合

Getting the best combination of closest pairs between 2 sets of points

java

algorithm

closest-points