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

Question

Пусть x1

Я написал этот алгоритм, может кто-нибудь проверить, правильно ли это?

Algorithm PostOffice(P)

    m <- (x1+xn) / 2
    i <- 1
    while xi < m do
        i <- i+1
    if xi - x1 < xn - xi-1
        return xi
    else return xi-1

Answer 1

Если мы должны возвращаться в почтовое отделение в каждое посещение , оптимальное местоположение можно найти, как при следующем подходе. Если существует нечетное количество точек, оптимальным местом является средняя точка в отсортированном порядке. В противном случае все точки между двумя точками, которые находятся посередине в отсортированном порядке ввода, являются оптимальными. Эта проблема известна как 1-медианная проблема.

PS: Я думаю, что это не то, о чем спрашивает проблема, но если почтальон начинает с почтового отделения, уходит и бросает города и, наконец, возвращается на почту, каждая точка между минимальной и максимальной точкой является оптимальной. , Стоимость равна 2*(X_max - X_min)