我必须要点集,比如说集 A 和 B
- A 和 B 大小相等
- A的每个元素都耦合到B的一个元素
A的所有点都必须'移动'到B的一个点,但是B的一个点不能耦合到A的多个点。
我需要找到最佳组合,其中总(步行)距离(从每对之间的距离加起来)是最小的。
为了演示目的,我在 Java 中做了一个例子(目前暴力破解所有可能的组合并检查哪个具有最小的总距离)
示例 1
示例 2
绿色矩形代表集合A中的一个点,青色矩形代表集合B中的一个点,忽略橙色方 block
我该如何处理?
最佳答案
这是一个 assignment problem , 这可以通过 Hungarian algorithm 在 O(n³) 时间内解决.找到源代码或自己实现应该不会太难。
关于java - 获得两组点之间最近对的最佳组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33264176/