用 Python 编写程序来查找服务中心的最佳位置

pythonserver side programmingprogramming更新于 2025/12/1 0:44:17

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

因此，如果输入为 positions = [(10,11),(11,10),(11,12),(12,11)]，则输出将为 4.0

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

numIter := 50
定义一个函数 total() 。这将需要 cx、cy、positions
total := 0.0
对于 positions 中的每个 p，执行
- x, y := p
- total := total + (cx, cy) 和 (x, y) 之间的欧几里得距离
返回 total
定义一个函数 fy() 。这将需要 x、positions
l := 0, r := 101
res := 0
对于范围从 0 到 numIter 的 i，执行
- y1 := l + (r - l) / 3
- y2 := r - (r - l) / 3
- t1 := total(x, y1, positions)
- t2 := total(x, y2, positions)
- res := t1 和 t2 的最小值
- 如果 t1 < t2，则
  - r := y2
- 否则，
  - l := y1
- 返回 res
- 定义一个函数 fx() 。这将采取立场
- l := 0, r := 101
- res := 0
- 对于 i 在 0 到 numIter 范围内，执行
  - x1 := l + (r - l) / 3
  - x2 := r - (r - l) / 3
  - t1 := fy(x1, positions)
  - t2 := fy(x2, positions)
  - res := t1 和 t2 的最小值
  - 如果 t1 < t2，则
    - r := x2
  - 否则，
    - l := x1
- 返回 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))