在Python中找到服务中心的最佳位置的程序

假设我们有一个位置列表，其中包含一些房屋所在的坐标点列表。如果要在(xc, yc)处建立服务中心，使得任何给定点到(xc, yc)的欧几里德距离的总和最小，则必须找到最小距离的总和。

所以，如果输入是positions=[(10,11),(11,10),(11,12),(12,11)]，输出将是4.0。

为了解决这个问题，我们将采取以下步骤：

numIter:= 50
定义一个函数 total() ，它将采取 cx，cy，positions
total:=0.0
for each p in positions, do
- x，y:=p
- total:=total+ (cx，cy) 到 (x，y) 的欧几里德距离
return total
定义一个函数 fy() ，它将采取 x，positions
l:= 0，r:= 101
res:=0
for i in range 0 to numIter, do
- y1:= l+ (r-l) /3
- y2:= r- (r-l) /3
- t1:= total(x，y1，positions)
- t2:= total(x，y2，positions)
- res:= min(t1，t2)
- if t1 < t2，then
  - r:= y2
- otherwise，
  - l:= y1
- return res
- 定义一个函数 fx() ，它将采取positions
- l:= 0，r:= 101
- res:=0
- for i in range 0 to numIter, do
  - x1:= l+ (r-l) /3
  - x2:= r- (r-l) /3
  - t1:= fy(x1，positions)
  - t2:= fy(x2，positions)
  - res:= min(t1，t2)
  - if t1 < t2，then
  - r:= x2
  - otherwise，
  - l:= x1
- return res

从主方法返回 fx(positions)

示例

让我们看看以下实现，以获得更好的理解

from math import sqrt
def solve(points):
   numIter = 50

   def total(cx, cy, positions):
      total = 0.0
      for p in positions:
         x, y = p
         total += sqrt((cx - x) * (cx - x) + (cy - y) * (cy - y))
      return total

   def fy(x, positions):
      l, r = 0, 101
      res = 0
      for i in range(numIter):
         y1 = l + (r - l) / 3
         y2 = r - (r - l) / 3
         t1 = total(x, y1, positions)
         t2 = total(x, y2, positions)
         res = min(t1, t2)
         if t1 < t2:
            r = y2
         else:
            l = y1
      return res

   def fx(positions):
      l, r = 0, 101
      res = 0
      for i in range(numIter):
         x1 = l + (r - l) / 3
         x2 = r - (r - l) / 3
         t1 = fy(x1, positions)
         t2 = fy(x2, positions)
         res = min(t1, t2)
         if t1 < t2:
            r = x2
         else:
            l = x1
      return res

   return fx(positions)

positions = [(10,11),(11,10),(11,12),(12,11)]
print(solve(positions))