LeetCode weekly-197-4: 1515. Best Position for a Service Centre
$ xy平面上の$ N個の点$ (x_1, y_1), (x_2, y_2),…, (x_N, y_N)が与えられる。$ \sum_{i=1}^{N} \sqrt{(x - x_{i})^2 + (y - y_{i})^2}の最小値を求めよ。
制約:
$ 1 \leq N \leq 50
$ 0 \leq x_{i}, y_{i} \leq 100
解の誤差が$ 10^{-5}以下であれば正答となる
---
幾何の高度なテクニックが求められると感じられて手が出せなかったが、実はそういったものは必要なかった。
目的関数は各点の$ \sqrt{(x - x_i)^2 + (y - y_i)^2}の和だが、この和を取る対象の値はその点と$ (x,y)との距離であって、凸関数であることがわかる。
性質の一つとしてわかることとして、$ xについては$ x_iの時最小でそこから離れる程大きくなり、$ yについても同様。
凸関数の和は凸関数となるため、目的関数は凸関数であることがわかる。簡単な証明(のようなもの)としては各関数の2階微分が非負であることと微分の線形性からわかる。
目的関数が凸関数であることから、極小値があれば(無限遠で発散することから確かに存在することがわかる)それは最小値であり$ x, yいずれもその最小値を与える点から離れれば離れるほど目的関数の値は単調増加する。
なお点が一直線上にある場合、最小値を与えるのは点でなく線分になるのだが($ (0, 0), (1, 0) の 2 点に対して最小値を与えるのは $ x \in [0, 1], y=0 )、最小値を与えるのが点であると考えても、どの点にたどり着いても得られる最小値が同一であることから問題無いことがわかる。
よってグリッドサーチ(と競プロの文脈で呼ぶのが正しいのか不明だが)で解が得られる。※
明らかに解を与える点は全点を囲う最小の長方形の中にあると言えるので、その領域で格子状に適当な数の点を打ち、その中で目的関数を最小化する点を得る。真の値はその点を含むその周囲の点による長方形にあると言えるため、領域を狭くして再度探索を行う。これを領域が許容誤差よりも小さくなるまで繰り返せば、その中の適当な点が解となる。
計算量について、
一回の探索で横・縦それぞれ$ a個ずつ点を打つと、最小を与えた点を中心に上下左右1格子$ 1/(a - 1)の範囲が次の探索範囲となるため、$ 4 / (a-1)^2倍となる($ a \geq 4でないと収束しない)。
一回の探索は$ O(a^2N)
一辺$ rの正方形内部にある2点の目的関数の差の最大値は$ N \sqrt 2 rで押さえられるため、$ N \leq 50より$ r \leq 10^{-7}であれば、その正方形中のどの点を選んでも真の値との誤差が$ 10^{-5}以下になることがわかる。よって初期の辺の最大長$ 100が最終的に$ 10^{-7}になれば良く、これは探索範囲が$ 10^{-9*2}倍になれば十分。
ということから、$ O(a^2 N * \log_{\frac{4}{(a-1)^2}} 10^{-18} ) = O(\frac{9a^2N}{\log \frac{a-1}{2}})(?)
分子の$ a^2が強いため、$ aは小さければ小さい程速く、1つ目の条件から$ a = 4とする(9分割する)のが丸そう。
と書いていて、$ xyそれぞれ3分割となるなと思うと同時に、これは三分探索を二次元で行っているということだと気付いた。※
ソース:
LeetCode の Discuss にも投稿した:
---
$ \sum_{i=1}^{N} |x - x_i|を最小化する$ xが$ x_1, x_2,…,x_Nの中央値となることが統計の文脈等で知られているが、その拡張ということなのだろう。しかし Geometric median は一次元の中央値ほど単純には求められず、Weiszfeld アルゴリズムなるものを使って求めることとなる。
---
※(追記)
二変数関数では凸であってもグリッドサーチ・三分探索は必ずしも真の解にたどり着けないっぽいことに気付いた。
最急降下法を用いるのがベストなのだろうか?