时间戳

首页 > 解决方案 > 在两个数组之间找到一个函数，以最小化对之间的距离

r - 在两个数组之间找到一个函数，以最小化对之间的距离

问题描述

我将在一般设置中解释我的问题（因为我对一般算法感兴趣），然后根据我的具体情况拒绝它。

假设我们有两个有限集 A 和 B，它们都是 X 的子集和一个距离函数 d，它指定 X 的任意两点之间的距离。找到两个函数的算法是什么：从 A 到 B 的 f1 和从 B 到的 f2 A 使得 f1(a) 是 B 中最接近 a 的元素，反之亦然。

我的特殊情况是在 R 语言中，我在地球上有两组点（纬度，经度），我需要根据它们的距离将它们配对（从 A 到 B，反之亦然）。作为参考，我正在使用与 geosphere 包的 Haversine distance。

提前致谢。

标签： ralgorithmdistance

解决方案

刚刚提到，这是一个算法问题的算法解决方案。

让我们从O(n^2)时间和内存复杂性的解决方案开始。对于 中的每个元素，A请记住与 中的每个元素的距离B。然后遍历这个二维数组并为每一行找到它的最小值 - 这些元素是 的图像f1，f2始终是 的逆函数f1。

O(n log n)现在我们可以在时间复杂度和O(n)内存复杂度上创建类似的解决方案。使用二分查找。

A让我们以一种我们可以说出与 in 集合中的某个项目最近的项目的方式对元素进行排序O(log n)。使用数字可以通过对它们进行排序来完成，lon & lat您只需要先对它们进行排序而lon不是 by lat。

现在对于搜索中的每个元素，使用二分搜索A时最接近的项目是什么。每个问题B都需要。O(log n)现在对于每个元素，我们知道哪个是最接近的。O(n log n).

推荐阅读