Оптимальный поиск, поиск точки, где сумма расстояний до других точек наименьшая

Question

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

В самолете на восемь очков

Как написать программу, которая получит мне такую ​​точку для k заданных точек в n-мерном пространстве (например, 16 точек в 10-мерном пространстве)

Как написать такой решатель?

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

Answer 1

Точка, для которой сумма расстояний до других точек минимальна, называется пространственной медианой этих точек, также называемой геометрической медианой .Его можно получить с помощью алгоритма Вайцфельда , который реализован в пакете R Gmedian.

Давайте попробуем на вашем примере:

library(Gmedian)

X <- rbind(
  c(3, 4),
  c(5, 3),
  c(1, 8),
  c(4, 6),
  c(6, 6),
  c(0, 1),
  c(4, 6),
  c(2, 1)
)

W <- Weiszfeld(X)

---

> W
$median
         [,1]     [,2]
[1,] 3.472091 4.607492

$iter
[1] 76

Вот как вы можете получить сумму расстояний:

smedian <- c(W$median)
sum(
  apply(X, 1, function(x){
    sqrt(crossprod(x-smedian))
  })
)
# 21.95253

Как видите, пространственная медиана отличается от той, которую вы получили ((4,4)), и от суммырасстояния меньше, чем у вас (22.84819).