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

Z时代
2024-01-10
分类：综合

假设我们有一个位置列表，其中包含一些房屋所在的坐标点列表。如果您想在 (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))