如何在1D中找到一组唯一的最接近点对？

Question

我的问题和这个问题很相似。如何找到一组唯一的最接近的点对？

唯一不同的是，我是在1D中。

所以，我有两组点（因为我在1D中，我们可以把它们看成0和1之间的数字）A和B，每组点分别含有m和n个元素，m<=n。

我的目标是找到集合C，由B中的m个DISTINCT点组成，使距离[A(i), C(i)]的总和最小化，如果m=n，我可以使用WWSERSTEIN距离，它有一个很好的1D实现。在2D中，我会使用hungarian算法，但它相当昂贵，我希望在1D中有一个更快的解决方案。

谅谅

Answer 1

大声思考。

对于A中的每一个点，很容易找到B中两边最近的两个点。为此只要把A和B越来越多地进行排序，通过类似合并的过程，就可以找到A的每一点在B中的前身和继任者。

这个过程的成本是O(NA对NA)+O(NB对NB)+O(NA+NB)，其中最后一项可以被吸收。

在左右两边的点中，给每一个点分配其最近的邻点，就可以实现最小的和。

---

到目前为止还不错，但不幸的是，最近的邻点也可能是A点的最近邻点，这时需要对冲突进行仲裁（A点中的一个点必须分配给另一个B邻点）。在最坏的情况下，会造成级联冲突。

到目前为止，我担心这个问题是全局性的，我看不到更好的办法，只能尝试用各种可能的方式解决冲突，并保持最佳配置。这个过程中，冲突点序列的长度是指数级的。