地理上分配权力（人）的想法或工具

Question

我有很多地方有坐标，我有人在出现问题时维护这些地方。 我正在寻找一种方法来放置现场的人，使他们成为最接近可能的主要数量的网站。

这个想法是这样的： 我有3000个网站与lat &长。 我想选择我有多少人可用，并与该信息我想获得最佳的坐标来分发他们。我不是在寻找一个存在的工具（但如果存在，我可以找它），但我不知道如何从这样的事情开始（我可以使用mysql，php，Gmaps，我学习另一个languaje /工具，如果它可以帮助我）。 谢谢

Answer 1

在一组给定的位置分配任意数量的人的问题是optimization问题。更具体地说，它可以被解释为clustering问题。在JS中实现的一个很好的集群示例可以在A Curious Animal博客找到。

正如你在上面的例子中看到的，聚类表示分组的相邻位置。换句话说，这是一种计算，可以在给定的一组位置上产生一组位置（群集）的最优分布。如果我们声明一个集群是一个人而不是一个位置组我们得到您的问题陈述。

由于人数是您的输入，我建议使用k-means聚类算法（short explanation，available software list @wikipedia）。

编辑：

当与一般的优化算法的工作有两点需要说明：

• 选择的算法旨在解决您的（类）的问题
• 一些输入参数组合可导致奇数，不可接受的结果

第一点需要一些算法知识，而第二点是一个问题正如你很好地注意到的那样，尝试错误。另外，输入的suptile差异会导致输出差异很大。

上述链接指出k-means算法“不适用于non-globuar clusters”。

从他的对面开始会更容易 - globular cluster定义为：“更精确的数学术语是convex，这大致意味着您可以在两个集群成员之间绘制的任何线停留在集群的边界内“：

非球状簇（非凸点的集合）看起来像这样：

也许你的“薄卵形团”是非凸的？

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

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

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

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

这是我偶然发现的一些code sample in C#。希望它有帮助。