Pythonでサービスセンターの最適な設置場所を見つけるプログラム（三分探索）

複数の家の座標点を含むリストが与えられたとします。(xc, yc) の位置にサービスセンターを設置するとき、すべての点から (xc, yc) までのユークリッド距離の合計が最小になるようにしたいと考えます。つまり、この問題では最小となる距離の合計を求める必要があります。

たとえば、入力が positions = [(10,11),(11,10),(11,12),(12,11)] の場合、出力は 4.0 になります。

解決のアプローチ：三分探索（Ternary Search）

この問題は三分探索を用いて効率的に解くことができます。「全点とのユークリッド距離の合計」という目的関数は下に凸な関数であるため、x 座標と y 座標のそれぞれに対して三分探索をネストして適用することで、最適な位置を段階的に絞り込めます。

具体的な手順は以下の通りです。

• 反復回数 numIter := 50 と設定する

• 関数 total(cx, cy, positions) を定義する：各点 (x, y) と (cx, cy) のユークリッド距離を合計して返す補助関数です

• 関数 fy(x, positions) を定義する：x を固定した状態で、y 方向に三分探索を行い、その x における距離合計の最小値を求めます

  • 探索範囲を l := 0、r := 101 と初期化

  • numIter 回にわたり、区間を三等分する2点 y1、y2 での値 t1、t2 を比較

  • t1 < t2 なら最小値は左側にあるので r := y2、そうでなければ l := y1 として範囲を狭める

  • t1 と t2 の小さい方を res として記録し、最後に返す

• 関数 fx(positions) を定義する：今度は x 方向に三分探索を行い、各区切り点 x1、x2 に対して fy() を呼び出すことで、全体の最小値を求めます

メイン処理では 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

まとめ

この手法では、x 方向・y 方向それぞれに50回ずつの三分探索を適用するため、座標の範囲が固定されていれば反復回数のみで精度が決まり、非常に安定した結果が得られます。幾何学的な最適化問題において、凸性を利用した三分探索は強力なテクニックなので、ぜひ覚えておきましょう。