设计一种有效的平均距离最小的邮局选址算法

Question

让x1< x2 <。。。< xn是表示直线沿线n个村庄坐标的实数。需要在其中一个村庄建立一家邮局。( a)设计了一种有效的算法，使村庄与邮局之间的平均距离最小化。

我写了这个算法，有人能检查一下它是否正确吗？

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)