Как я могу получить оптимальное соответствие между K группами?

Question

У меня есть K наборов точек данных, я хотел бы создать группы размером K, которые минимизируют общую сумму внутригрупповых расстояний.Я знаком с алгоритмами сопоставления с двудольными графами, но мне бы хотелось, чтобы это было более двух наборов.

Есть идеи?

Редактировать:

Каждая группа будет состоять из одного элемента каждого набора, повторы не допускаются.

Пример: у вас есть{a1, a2, a3}, {b1, b2, b3}, {c1, c2, c3} Вы хотите создать группы, например, {a1, b3, c3}, {a2, b1, c2}, {a3, b2,c1} минимизация суммы внутригрупповых расстояний.

Answer 1

Эта проблема может быть сведена к другой, аналогичной проблеме, которую я решил ранее для другого вопроса stackoverflow.Идея состоит в том, чтобы вычислить все комбинации групп размером n / k и взвесить их в соответствии с их внутригрупповыми расстояниями.Пройдите через область поиска допустимых комбинаций комбинаций.Ведите учет минимальной суммы и используйте ее для удаления тупиковых веток.Вы можете ускорить поиск, используя динамическое программирование, создав оптимальные подмножества решения и составив из этого окончательное решение (как описано в моем другом посте), или вы можете использовать жадный метод и некоторые ручные трюки, чтобы найти почтиоптимальное (или оптимальное) решение (также описано в указанном посте). Здесь - ссылка на вспомогательную проблему, которую вы можете уменьшить до.

Answer 2

Даже для k = 3 он имеет вид трёхмерного соответствия NP-трудной задачи.(Очевидное сокращение не работает, потому что могут быть созданы фантомные тройки, где каждая из трех пар недопустимой тройки появляется отдельно в допустимой тройке.)

В зависимости от размера экземпляра, я бы либоПопробуйте локальный поиск или целочисленное программирование с генерацией столбцов (но внутренняя проблема кажется сложной без структуры низкоразмерного метрического пространства, и даже тогда нетривиальной).