地理分散启发式算法

Question

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

其中之一的标准是地理分散度，因此我需要能够为我的任何子集分配一个表示分散度的值。

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

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

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

然后我尝试了所有潜在解决方案的所有位置到中心的距离之和，这被证明更快，但效果不佳。使用这种方法将偏向于少数位置簇。

如果您有其他建议，将不胜感激。

- user1994232

---

我很好奇为什么计算成对距离会太慢。我认为设施选址问题是战略性、高成本的决策问题，即使算法需要花费数小时或数天才能运行，也足以做出一个将在未来几年内固定的决策。 - user327301

是的，你说得对，我的问题在于地理分散始终是与其他因素相比的三元目标，即在其他所有条件相等的情况下选择更分散的解决方案。如果没有地理分散，我的实现可以在15秒内提供良好的结果，但我不能超过30秒。我基本上正在尝试找到一个折中的方法，在不付出计算代价的情况下收集关于分散的部分指示。 - user1994232

Answer 1

首先，您能否重新说明一下什么是成对求和？我问这个问题是因为听起来您要形成所有可能的配对，这将非常低效。如果是这种情况，那么先找到最近的邻居，然后再找到最长的路径如何？

1）如果我没记错的话，您可以在少于O（n log n）的时间内完成此操作。 2）如果形成的树是不连通的，则还必须找到树之间的最短距离。由于是树，这不是一个NP完全问题，实际上最短路径算法就足够了。

此时，我非常怀疑我没有正确理解您的问题，那么如何通过地理区域中出现次数的某种偏差来解决问题，可以均匀分布在极端点之间，也可以选择一些先前的启发式方法。

您能否定义或进一步阐述分散概念？

- Gspia

Answer 2

考虑三种情况：

1. 所有节点都在一个密集的簇中。
2. 所有节点都在一个簇中，但该簇很宽。
3. 许多节点在一个簇中，但有一些节点远离该簇。

对于所有成对距离的总和可以很好地捕捉（1）和（2）：接近的簇比大簇给出更小的结果。那么对于（3）呢？在这里，总节点数 N 的比例 e 远离，平均距离为 D。其他 (1-e)N 个节点以平均距离 d 聚集。

现在，必须考虑多少成对连接？对于聚集的节点，有 ((1-e)N)^2=e^2*N^2-2*e*N^2+N^2 这样的连接。对于远程节点，有 e^2*N^2 个连接。

现在，将这些值乘以平均距离。这给出了一个总的成对平均值：(d*(e^2*N^2-2*e*N^2+N^2)+D*(e^2*N^2))/N。现在，假设e很小，我们可以忽略包含e^2的项。因此，平均值为d*(N^2-2*e*N^2)/N。

现在，考虑您的第二个指标：每个人与平均中心点的距离。这在（1）和（2）上表现良好：接近的聚类比较大的聚类具有更小的结果。它在第3个指标上如何表现？使用与上述相同的e来表示异常值的比例。现在，节点从中心点的平均距离由(d*(1-e)*N+D*e*N)/N给出。换句话说，聚类节点不再被加权。

是否有一种轻量级计算方法，仍然可以更适当地加权聚类节点？我认为是的。

我的建议是从列表中选择随机节点对，计算节点间距离，然后对结果取平均值。对于（1）紧密聚集的情况，所有节点都会靠在一起，因此您绘制的所有随机节点对都将接近您通过计算得到的成对平均值。对于（2）松散聚集的情况，同样如此。对于（3）具有异常值的聚类，您更有可能从聚类内部而不是外部抽取节点，因此异常值最终被忽略。

随着采样节点数的增加，聚类将倾向于支配随机采样。我猜测这将提供O(N)而不是O(N^2)时间的相当准确性。

- Richard