Поместите точку N, чтобы минимизировать расстояние до списка точек

Question

Учитывая список точек на 2D-плоскости, как можно разместить N точек на плоскости таким образом, чтобы общая сумма всех расстояний от списка точек до ближайшей точки была как можно меньше?Окружение является сдержанным, и список будет содержать уникальные точки в диапазоне [(0,0);(~ 200: ~ 100)]

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

Answer 1

Этот звук действительно похож на то, что делает алгоритм кластеризации K-Means . В вашем случае список точек - это входные данные, а количество точек N - это количество кластеров.

К сожалению, то, что он делает, NP-трудный. Но есть много исследований, и есть много способов, чтобы попытаться сделать это лучше (просто прокрутите вниз страницу вики, чтобы найти).

Кроме того, я сомневаюсь, что будет лучший алгоритм, так как ученые очень активно используют k-means. Я думаю, если бы был лучший алгоритм, который они бы запустили для этого:)

И снова я представляю вам лучший учебник по Data Mining для меня: Слайды Эндрю Мура . Хотя я не знаю вашей цели, это должно быть очень близко к тому, что вам нужно.

Answer 2

Вы можете получить Центр масс списка узлов (с весами = 1).
Или дисперсия с х ^ 2 для расстояний.

Вы уменьшили проблему до того, где разместить N узлов в области центра масс, где расстояние до остальных минимально.

В идеальном мире вы бы просто поместили одну точку в центр масс. Но поскольку я предполагаю, что вы не можете разместить 2 точки в одном и том же месте, вам нужно выбрать окрестности центра масс.

Таким образом, проблема сводится к тому, чтобы просто выбрать лучшую из 8 точек вблизи центра масс, затем пересчитать центр масс и повторить это.