mathematical-optimization - 地理分散启发式

Question

我正在尝试实现一种爬山算法，以根据特定标准决定从一组位置中选择哪些位置。最多有 5000 个位置可供选择。

这些标准之一是地理分散，因此我需要能够为我的位置的任何子集分配一个代表分散的值。

每个位置都有纬度和经度数据。

速度是一个问题，这就是为什么我需要一些启发式方法来估计一组特定位置(即可能的解决方案)的分散程度。

我曾尝试对我的潜在解决方案中每个位置的成对距离求和，但事实证明这太慢了。

然后，我在我的潜在解决方案中尝试了距所有位置中心的距离总和，事实证明这速度更快，但效果不佳。使用这种方法将有利于一些位置集群。

任何其他建议将不胜感激。

Answer 1

首先，您能否重申成对总和的含义？我在问，因为听起来你形成了所有可能的对，这将是非常低效的。如果是这种情况，如何首先找到 1) 最近的邻居，然后 2) 最长的路径？

1) 如果我没记错的话，你可以在不到 O(n log n) 的时间内完成。2)如果形成的树是断开的，你也必须找到树之间的最短距离。由于有树，这不是 NP 完全问题，但实际上最短路径算法就足够了。

此刻，我非常怀疑我没有正确理解你的问题，在地理区域的出现次数上出现某种偏差怎么样，要么在极端点之间平均分配，要么通过一些先验启发式选择。

您能定义或进一步阐述色散概念吗？