Кластеризация 2d целочисленных координат в наборы не более N точек
У меня есть несколько точек на относительно небольшой 2-мерной сетке, которая охватывает оба измерения. Координаты могут быть только целыми числами. Мне нужно разделить их на наборы не более N точек, которые находятся близко друг к другу, где N будет довольно небольшим отсечением, я подозреваю, что не более 10.
Я разрабатываю ИИ для игры, и я на 99% уверен, что использование минимакса для всех игровых элементов даст мне полезный прогноз примерно на 1 ход, если это так. Однако удаленные игровые фишки не должны влиять друг на друга, пока мы не заглянем вперед на большое количество ходов, поэтому я хочу разделить игру на несколько подигр по N фишек одновременно. Однако мне нужно убедиться, что я выбираю разумные N частей за раз, то есть те, которые расположены близко друг к другу.
Меня не волнует, останутся ли выбросы сами по себе или смешаны с их наименее удаленным кластером. Разделение естественных кластеров размером больше N неизбежно, и оно должно быть разумным. Поскольку это используется в игровом ИИ с ограниченным временем отклика, я ищу как можно более быстрый алгоритм и готов пойти на компромисс между точностью и производительностью.
Есть ли у кого-нибудь предложения по адаптации алгоритмов? K-средства и родственники не кажутся подходящими, поскольку я не знаю, сколько кластеров я хочу найти, но у меня есть ограничение на то, насколько большие кластеры я хочу. Я видел некоторые доказательства того, что аппроксимация решения путем привязки точек к сетке может помочь некоторым алгоритмам кластеризации, поэтому я надеюсь, что целочисленные координаты облегчают проблему. Иерархическую кластеризацию на основе расстояния будет легко адаптировать к циклическим координатам, поскольку я просто подключаю другую функцию расстояния, а также относительно легко ограничивать размер кластеров. Есть ли другие идеи, на которые мне следует обратить внимание?
Меня больше интересуют алгоритмы, чем библиотеки, хотя библиотеки с хорошей документацией о том, как они работают, будут приветствоваться.
РЕДАКТИРОВАТЬ : Я изначально задал этот вопрос, когда работал над записью для Fall 2011 AI Challenge , которую, к сожалению, так и не закончил. Страница, на которую я дал ссылку, содержит достаточно короткое и достаточно высокоуровневое описание игры.
Двумя ключевыми моментами являются:
- Каждый игрок имеет потенциально большое количество муравьев.
- Каждому муравью отдается приказ каждый ход, двигаясь на 1 квадрат на север, юг, восток или запад; это означает, что коэффициент ветвления игры равен O (4 муравьев ).
В конкурсе также были жесткие временные ограничения на ход каждого бота. Я думал подойти к игре, используя минимакс (ходы действительно одновременные, но в качестве эвристики я подумал, что это будет нормально), но я боялся, что у меня не будет времени заглядывать вперед на очень много ходов, если я буду рассматривать всю игру однажды. Но поскольку каждый муравей перемещается только на один квадрат за ход, два муравья не могут находиться на расстоянии N интервалов по кратчайшему маршруту, возможно, мешать друг другу, пока мы не посмотрим вперед на N / 2 хода.
Итак, решение, которое я искал, было хорошим способом выбрать меньшие группы муравьев за раз и минимаксировать каждую группу отдельно. Я надеялся, что это позволит мне глубже искать в дереве ходов без большой потери точности. Но очевидно, что нет смысла использовать очень дорогой алгоритм кластеризации в качестве эвристики для экономии времени!
Меня все еще интересует ответ на этот вопрос, но больше в том, что я могу узнать из техник, чем в этом конкретном конкурсе, поскольку он закончился! Спасибо за все ответы.