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

我在一个相对较小的二维网格上有许多点,它在两个维度上都包裹着.坐标只能是整数.我需要将它们分成最多N个接近在一起的点,其中N将是一个非常小的截止点,我最多怀疑10个.

我正在为游戏设计一个人工智能,而且我99%肯定在所有游戏中使用minimax会给我一个可用的前瞻性约1动作,如果那样的话.然而,在我们通过大量动作展望未来之前,遥远的游戏棋子应该无法相互影响,所以我想将游戏分成N个棋子的多个子游戏.但是,我需要确保我一次选择合理的N个片段,即那些靠得很近的片段.

我不关心异常值是自己留下还是与最远距离的集群混在一起.打破大于N的自然集群是不可避免的,只需要合理.因为这是在具有有限响应时间的游戏AI中使用的,所以我正在寻找尽可能快的算法,并且愿意牺牲性能的准确性.

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

我对算法比对图书馆更感兴趣,尽管有很好的文档库可以很好地记录它们的工作方式.

编辑:当我正在为2011秋季AI挑战赛的参赛作品时,我最初问过这个问题,我很遗憾没有完成.我链接的页面有一个相当短的合理的高级游戏描述.

两个关键点是:

每个玩家都有大量的蚂蚁

每一只蚂蚁每回合都有一个命令,向北,向南,向东或向西移动1个方格; 这意味着游戏的分支因子是O(4 ^蚂蚁).

在比赛中,每个机器人都有严格的时间限制.我曾经想过使用minimax接近游戏(转弯真的是同时发生,但作为一种启发式,我认为它会没问题),但我担心如果我考虑整个游戏,就没有时间向前看很多动作立刻.但是由于每只蚂蚁每回合仅移动一个方格,两条蚂蚁不能通过最短路径分开N个空间,可能会相互干扰,直到我们向前看N/2次移动.

所以我正在寻找的解决方案是一次选择较小的蚂蚁群并分别对每组进行极小动作的好方法.我原本希望这会让我更深入地搜索移动树而不会失去太多准确性.但显然使用非常昂贵的聚类算法作为节省时间的启发式是没有意义的!

我仍然对这个问题的答案感兴趣,尽管我可以从技术中学到更多的东西而不是这个特别的比赛,因为它已经结束了!谢谢你到目前为止的所有答案.

中值切割算法在2D中实现非常简单,并且在这里可以很好地工作.你的异常值最终会成为你可以丢弃的1组或者其他什么.

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

更详细的描述和编码示例

关于颜色量化的Wiki有一些很好的视觉效果和链接