0

我必须设置点，比如说设置 A 和 B

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

A 的所有点都必须“移动”到 B 的一个点，但 B 的一个点不能耦合到 A 的多个点。

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

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

示例 1

示例图 1

示例 2

示例图 2

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

我将如何处理这个？

4

2 回答 2

2

这是一个分配问题，可以通过匈牙利算法在O ( n³ ) 时间内解决。找到源代码或自己实现它应该不会太难。

于 2015-10-22T08:14:23.407 回答
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
于 2015-10-21T16:28:40.967 回答