Как найти лучшую комбинацию, чтобы минимизировать общее расстояние во всех группах точек

Question

Учитывая 4n + k точек с положением (x, y) (или (x, y, z) для трехмерного случая), где n = 1,2,3, ...; k∈ {0,1,2,3}. Сгруппируйте точки в n-k группы из 4 точек и k групп из 5 точек. Центроид группы - это среднее положение 4 (или 5) точек в группе.

Как эффективно получить наилучшую комбинацию, чтобы минимизировать сумму расстояний каждой точки до собственного группового центроида?

Жестокое перечисление - единственный способ, которым я добился, чтобы получить лучшую комбинацию. Однако грубая сила работает, только когда n достаточно мало из-за вычислительных ограничений.

Я также попробовал кластеризацию и генетический алгоритм K-Means, но ни один из них, ни комбинация этих двух алгоритмов не могут гарантировать наилучшую комбинацию.

Answer 1

Поскольку проблема предположительно в NP-сложности, вы не сможете найти алгоритм, который гарантирует для нахождения оптимального значения и который работает в приемлемое время для больших данных.

Вы должны согласиться с приближением, таким как kmeans.