这是一个有趣但复杂的问题:
假设我们有两组点。一组 A 包括一些空间网格中的点，例如常规的 1D 或 3D 网格。另一组 B 包括随机间隔且与空间网格大小相同的点。在数学上，我们可以对这两个集合进行排序，并根据A和B之间的距离构造一个对应的矩阵。例如，A(i, j)可以指A的i和B的j之间的距离。
给定一些顺序，我们有一个矩阵。那么，矩阵中的对角线元素(i,i)就是A的点i和B的点i之间的距离。问题是如何找到一个好的重新排序/索引使得最大距离尽可能小？在矩阵形式中，如何找到一个好的排序/索引使得最大对角线元素尽可能小？
我自己的笔记:
假设集合A对应矩阵的行，集合B对应矩阵的列。然后重新排序矩阵意味着我们正在进行行/列置换。因此，我们的问题等同于找到一个好的排列来最小化最大对角线元素。
贪心算法可能是一种选择。但我正试图找到一种理想的完美重新排序，以最大限度地减少最大的对角线元素。
最佳答案
您所指的重新排序本质上是一个对应问题，即您正在尝试为另一组中的每个点找到最接近的匹配项。贪心算法可以正常工作。您要查找的距离通常称为 Hausdorff distance .
关于algorithm - 找到一个最小化两个集合的最大距离的算法，比贪心算法好，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19035273/