algorithm - 将 2d 整数坐标聚类成最多 N 个点的集合

Question

我在一个相对较小的二维网格上有许多点，该网格在两个维度上都环绕。坐标只能是整数。我需要将它们分成最多 N 个靠得很近的点的集合，其中 N 将是一个很小的截止点，我怀疑最多 10 个。

我正在为一款游戏设计 AI，我 99% 确定在所有游戏部件上使用 minimax 会给我一个大约 1 步的可用前瞻，如果那样的话。然而，在我们通过大量移动向前看之前，遥远的游戏应该不会相互影响，所以我想将游戏分成多个子游戏，一次有 N 个子游戏。但是，我需要确保我一次选择合理的 N 件，即靠得很近的件。

我不在乎离群值是单独存在还是与距离最小的集群混为一谈。拆分大于 N 的自然集群是不可避免的，只需要有点合理即可。因为这是在响应时间有限的游戏 AI 中使用的，所以我正在寻找一种尽可能快的算法，并且愿意牺牲准确性来换取性能。

有没有人对算法考虑自适应有任何建议？ K-means 和亲戚似乎不合适，因为我不知道我想找到多少个集群，但我对我想要的集群有一个限制。我已经看到一些证据表明通过将点捕捉到网格来近似解决方案可以帮助某些聚类算法，所以我希望整数坐标可以使问题更容易。基于距离的分层聚类很容易适应环绕坐标，因为我只是插入了一个不同的距离函数，而且也相对容易限制集群的大小。还有其他我应该考虑的想法吗？

与图书馆相比，我对算法更感兴趣，尽管欢迎拥有关于其工作原理的良好文档的图书馆。

编辑:我最初在为 Fall 2011 AI Challenge 编写条目时问过这个问题。 ，遗憾的是我从未完成。我链接到的页面对游戏进行了相当简短的高级描述。

两个关键点是:

1. 每个玩家都有潜在的大量 Ant
2. 每只 Ant 每回合都会收到命令，向北、向南、向东或向西移动 1 个方格；这意味着游戏的分支因子是 O(4^ants)。

在比赛中，每个机器人的回合也有严格的时间限制。我曾想通过使用 minimax 来接近游戏(转弯实际上是同时的，但作为一种启发式我认为这没问题)，但我担心如果我考虑整个游戏就没有时间向前看很多 Action 立刻。但是由于每只 Ant 每转一圈只移动一个方格，两只 Ant 不能通过最短路线分开 N 个空间，可能会相互干扰，直到我们向前看 N/2 次移动。

所以我正在寻找的解决方案是一次选择较小的 Ant 群并分别对每个群进行极小化最大化的好方法。我曾希望这能让我在不损失太多准确性的情况下更深入地搜索移动树。但显然，使用非常昂贵的聚类算法作为节省时间的启发式算法是没有意义的!

我仍然对这个问题的答案很感兴趣，虽然更多的是我可以从这些技术中学到什么，而不是这个特定的比赛，因为它已经结束了!感谢您到目前为止的所有回答。

Answer 1

中值切割算法在 2D 中实现起来非常简单，在这里效果很好。您的离群值最终会以 1 为一组结束，您可以丢弃它们或其他任何东西。

要求进一步解释:中值切割是一种量化算法，但所有量化算法都是特例聚类算法。在这种情况下，算法非常简单:找到包含所有点的最小边界框，沿其最长边拆分框(并缩小它以适合点)，重复直到达到目标框数。

A more detailed description and coded example

Wiki on color quantization has some good visuals and links