问题标签 [closest-points]

我有一个包含 shop_id、纬度和经度的列表。假设我们有相同数量的点，我想将每个商店与另一个商店匹配，这样我们的连接是独一无二的，并且我们最小化了整体距离。

我很好奇我的方法是否不太愚蠢，以及更好的方法会是什么。目前，这在合理的时间（一小时）内有效，可获得 1000 分。

假设我们有一个这样的列表：

我使用 PuLP 使用此工作流程创建一个 .lp 文件：

我在其中调用了一些生成器功能（以帮助 RAM ...）

如果我在 100 家商店上运行它，速度非常快，我可以使用默认的 PuLP 求解器。否则，我将 LP 文件提交给 NEOS 服务器上的 CPLEX。我创建了一个小辅助函数，它可以可视化结果匹配：

这是我的 LP 文件如何查找 10 个商店（截断）的简单示例：

结果：

最后，这是一个关于 1000 点的更大示例：

我正在努力思考分治算法如何适用于大于 2 的维度，特别是如何找到两个子问题之间最接近的点对。

我知道我只需要考虑轴上d两者之间的距离内的点。x

我知道在 3d 案例中，我需要将每个点与其他 15 个点进行比较。

我不明白的是如何选择这15个点。在 2d 情况下，只需按值对值进行排序y并按顺序遍历它们。y 然而，在 3d 情况下，每个点都需要与和 z轴上最接近它的 15 个点进行比较。我似乎无法找到一种方法来确定这 15 点是什么，而不会出现最坏的情况O(n^2)......

我在这里想念什么？

以下代码模拟查找最近的对，但是当我生成大于 250 的随机对时，它会引发堆栈溢出错误。但是 250 双和任何偶数以下似乎都可以正常工作。有任何想法吗？

该错误发生在 if 语句下的 ComparePoints 的递归调用中。

我正在尝试创建一种算法，该算法从随机生成的点中返回最接近的对。我已经完成了算法，但是算法的分治法并不比蛮力法快多少。我可以做些什么来优化代码，使其在 (n log n) 时间返回？

如果给我一个整数/浮点数列表，我将如何使用排序找到两个最接近的数字？

我得到了一个整数/浮点数列表，我需要找到最接近的两个数字。我将如何仅使用嵌套的 for 循环来做到这一点？

所以我在尝试调试这段代码时遇到了一些麻烦。我有一个数字列表，比如 [4,5,7,3,5,2,3]，我需要找到最接近的两个点，所以在这种情况下，3 和 3 因为它们的差为零. 但是，它没有返回正确的输出。如果一个数字在列表中没有重复，它会起作用，但如果一个数字出现多次，它就不起作用。

在这里研究最近点算法。我正在输入一个二维数组int。由于某种原因，我没有得到正确的答案。我的递归有什么问题conquer？我认为这就是问题所在。

我有一组二维笛卡尔点[b]，它们从一开始就顺时针方向前进并形成一个封闭的形状。这些中的每一个都有自己的伴生 2D 笛卡尔点q0，q1并定义了围绕该点的贝塞尔曲线（以及前面和后面的点）。所有这些点一起定义了一个封闭的二维复合贝塞尔曲线。

我有一个单独的点p，它是同一平面上的任意二维笛卡尔点。是否有一种简单的算法可以找到路径上最近点(x, y)的新二维笛卡尔点的坐标？qp

如此处所示，我有点和它们b[0]的b[3]句柄b[n].q0和b[n].q1，我有任意点p。我正在尝试计算 point q，而不是作为沿曲线的浮点位置，而是作为一对(x, y)坐标。

我试着搜索这个，但有些似乎只是一条很小的曲线，有些则与抽象数学和科学研究论文有关。

非常感谢任何能引导我找到算法解决方案的帮助，特别是如果它可以翻译成类似 C 的语言，而不是上述 SO 答案中的纯数学。

我有两个坐标archivo1和archivo2的数据帧，我需要第一个数据帧中第二个数据帧的最近点（id）。到目前为止，我的代码是：

代码运行并给了我预期的结果，但第一个文件有 700 万，第一个文件有 70k，所以需要 7 天的运行时间。谁能帮我优化一下？

这是两个文件的示例：

这是要查找的文件 2：