用 Python 寻找服务中心的最佳位置的程序

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

因此，如果输入类似于位置 = [(10,11),(11,10),(11,12),(12,11)]，那么输出将为 4.0

为了解决这个问题，我们将遵循以下步骤 -

• 数字：= 50

• 定义一个函数total()。这将占用 cx, cy, 位置

• 总计：= 0.0

• 对于位置上的每个 p，做

• x, y := p

• total := total + (cx, cy) 和 (x, y) 之间的欧几里得距离

• 总回报

• 定义一个函数fy()。这将占用 x, 个位置

• l := 0, r := 101

• 水库：= 0

• 对于 i 在 0 到 numIter 的范围内，执行

• x1 := l + (r - l) / 3

• x2 := r - (r - l) / 3

• t1 := fy(x1, 位置)

• t2 := fy(x2, 位置)

• res := t1 和 t2 的最小值

• 如果 t1 < t2，则

• 除此以外，

• r := x2

• l := x1

• l := y1

• r := y2

• y1 := l + (r - l) / 3

• y2 := r - (r - l) / 3

• t1 := 总计(x, y1, 位置)

• t2 := 总计(x, y2, 位置)

• res := t1 和 t2 的最小值

• 如果 t1 < t2，则

• 除此以外，

• 返回资源

• 定义一个函数fx()。这将采取立场

• l := 0, r := 101

• 水库：= 0

• 对于 i 在 0 到 numIter 的范围内，执行

• 返回资源

从 main 方法，返回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))

输入

[(10,11),(11,10),(11,12),(12,11)]

4.0