Ben*_*Ben 7 algorithm cluster-analysis
我在一个相对较小的二维网格上有许多点,它在两个维度上都包裹着.坐标只能是整数.我需要将它们分成最多N个接近在一起的点,其中N将是一个非常小的截止点,我最多怀疑10个.
我正在为游戏设计一个人工智能,而且我99%肯定在所有游戏中使用minimax会给我一个可用的前瞻性约1动作,如果那样的话.然而,在我们通过大量动作展望未来之前,遥远的游戏棋子应该无法相互影响,所以我想将游戏分成N个棋子的多个子游戏.但是,我需要确保我一次选择合理的N个片段,即那些靠得很近的片段.
我不关心异常值是自己留下还是与最远距离的集群混在一起.打破大于N的自然集群是不可避免的,只需要合理.因为这是在具有有限响应时间的游戏AI中使用的,所以我正在寻找尽可能快的算法,并且愿意牺牲性能的准确性.
有没有人有任何关于算法的建议来适应？K-means和亲戚似乎不合适,因为我不知道我想找到多少个集群,但我对我想要的集群有多大的约束.我已经看到一些证据表明通过将点捕捉到网格来近似解决方案可以帮助一些聚类算法,所以我希望整数坐标使问题更容易.基于距离的分层聚类将很容易适应环绕坐标,因为我只需插入不同的距离函数,并且相对容易限制聚类的大小.我还应该关注其他任何想法吗？
我对算法比对图书馆更感兴趣,尽管有很好的文档库可以很好地记录它们的工作方式.
编辑:当我正在为2011秋季AI挑战赛的参赛作品时,我最初问过这个问题,我很遗憾没有完成.我链接的页面有一个相当短的合理的高级游戏描述.
两个关键点是:
在比赛中,每个机器人都有严格的时间限制.我曾经想过使用minimax接近游戏(转弯真的是同时发生,但作为一种启发式,我认为它会没问题),但我担心如果我考虑整个游戏,就没有时间向前看很多动作立刻.但是由于每只蚂蚁每回合仅移动一个方格,两条蚂蚁不能通过最短路径分开N个空间,可能会相互干扰,直到我们向前看N/2次移动.
所以我正在寻找的解决方案是一次选择较小的蚂蚁群并分别对每组进行极小动作的好方法.我原本希望这会让我更深入地搜索移动树而不会失去太多准确性.但显然使用非常昂贵的聚类算法作为节省时间的启发式是没有意义的!
我仍然对这个问题的答案感兴趣,尽管我可以从技术中学到更多的东西而不是这个特别的比赛,因为它已经结束了!谢谢你到目前为止的所有答案.
中值切割算法在2D中实现非常简单,并且在这里可以很好地工作.你的异常值最终会成为你可以丢弃的1组或者其他什么.
需要进一步说明:中值切割是量化算法,但所有量化算法都是特殊情况聚类算法.在这种情况下,算法非常简单:找到包含所有点的最小边界框,沿着其最长边分割框(并缩小它以适合点),重复直到达到目标数量的框.
在网格上构造一个图G =( V , E ) 并将其分区。\n由于您对算法而不是库感兴趣，所以这是最近的一篇论文：
\n\n\n\n\n丹尼尔·戴尔林 (Daniel Delling)、安德鲁·V·戈德堡 (Andrew V. Goldberg)、伊利亚·拉赞什泰恩 (Ilya Razenshteyn) 和雷纳托·F·韦内克 (Renato F. Werneck)。具有自然切割的图分区。第25届国际并行与分布式处理研讨会(IPDPS\xe2\x80\x9911)。IEEE 计算机协会，2011 年。[ PDF ]
\n
从正文来看：
\n\n\n\n\n图分区问题的目标是 \xef\xac\x81nd 一个最小成本分区P，使得每个单元的大小以U为界。
\n
所以你将设置U = 10。
\n| 归档时间： |
|
| 查看次数： |
3830 次 |
| 最近记录： |