1

我有很多有坐标的地方，当出现问题时，我会有人维护这些地方。我正在寻找一种方法来放置现场人员，以便他们尽可能接近大量站点。

这个想法类似于：我有 3000 个带有 lat&long 的站点。我想选择我有多少可用的人，并通过这些信息获得最佳坐标来分配他们。

我不是在寻找现有的工具（但如果存在，我可以寻找它），但我不知道如何从这样的东西开始（我可以使用 mysql、php、Gmaps，如果有的话，我会学习另一种语言/工具帮我）。谢谢

4

1 回答 1

3

在给定的一组位置上分布任意数量的人的问题是一个优化问题。更具体地说，它可以解释为聚类问题。可以在A Curious Animal博客中找到一个用 JS 实现的漂亮集群示例。

正如您在上面的示例中所看到的，聚类意味着对相邻位置进行分组。换句话说，它是一种计算，可以在给定的一组位置上产生位置组（集群）的最佳分布。如果我们声明一个集群是一个人而不是一个位置组，我们就会得到您的问题陈述。

由于人数是您的输入，我建议使用 k-means 聚类算法（简短说明，可用软件列表 @wikipedia）。

编辑：

通常在使用优化算法时有两个注意事项：

  • 所选算法旨在解决您的（类别）问题
  • 某些输入参数组合可能会导致奇怪的、不可接受的结果

第一点需要一些算法知识，而第二点是试错的问题，正如您所注意到的那样。此外，输入的细微差异会导致输出的巨大差异。

上面的链接指出，k-means 算法“不适用于非球状集群”。

从他的对立面开始会更容易——一个球状星团，它被定义为：“更精确的数学术语是凸的，这大致意味着你可以在两个星团成员之间画的任何线都停留在星团的边界内。”：

凸集

非球状簇（非凸点集）如下所示：

非凸集

可能您的“薄卵形簇”是非凸的？

另一个重要特征（也在上面的链接中说明）是 k-means 是一种非确定性算法，这意味着它可能（并且很可能会）在多次运行时为相同的输入产生不同的输出。

发生这种情况是因为该算法随机对集群进行初始分区 - 并且最终输出对该初始分区高度敏感。根据使用的实现，您可能在此处有一些修改空间。

如果这不能带来令人满意的结果，那么剩下的唯一一件事就是尝试另一种算法（因为已经给出了位置）。我会建议我在商业产品中使用的QT 聚类算法。它是一种确定性聚类算法，将最小聚类大小和阈值距离 - 点到聚类中心的距离作为输入。

但是，使用这种方法，您将需要修改算法本身。当“不能再形成具有最小集群大小的集群”时，该算法通常会停止。您需要修改算法以在达到所需的集群数量时停止。最小集群大小值应该可以为 1，但您可能希望尝试不同的阈值距离值。

这是我偶然发现的一些C# 代码示例。希望对您有所帮助。

于 2013-03-02T11:50:54.797 回答