Pythonでサービスセンターの最適な位置を見つけるためのプログラム

いくつかの家が配置されている座標点のリストを含む位置のリストがあるとします。 （xc、yc）にサービスセンターを作成し、任意のポイントから（xc、yc）までのユークリッド距離の合計が最小になるようにする場合。したがって、最小距離の合計を見つける必要があります。

したがって、入力がpositions =[（10,11）、（11,10）、（11,12）、（12,11）]のような場合、出力は4.0

これを解決するには、次の手順に従います-

• numIter：=50

• 関数total（）を定義します。これにはcx、cy、positionsが必要です

• 合計：=0.0

• 位置の各pについて、実行します

  • x、y：=p

  • total：=total +（cx、cy）と（x、y）の間のユークリッド距離

• 合計を返す

• 関数fy（）を定義します。これはx、位置を取ります

• 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

    • r：=y2

  • それ以外の場合

    • l：=y1

  • 解像度を返す

  • 関数fx（）を定義します。これはポジションを取ります

  • l：=0、r：=101

  • res：=0

  • 0からnumIterの範囲のiの場合、実行

    • x1：=l +（r --l）/ 3

    • x2：=r-（r --l）/ 3

    • t1：=fy（x1、positions）

    • t2：=fy（x2、positions）

    • res：=t1とt2の最小値

    • t1

      • r：=x2

    • それ以外の場合

      • l：=x1

  • 解像度を返す

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