2 次元 3 分探索

 

この記事は

2 変数関数の最大値を嘘解法で求めるときに思いついた方法を書いています。厳密性のない感覚的な議論が多いので、厳密な話をしたい人はお帰り頂くか、読んだうえでいろいろご指摘頂けると嬉しいです。

 

題材

もとは この問題 を考えていたときに考えたものですが、他にも応用できるかもしれません。

 

問題の一般化

R = \{(x,\ y) \| x_0 \le x \le x_1,\ y_0 \le y \le y_1\} の範囲で関数 f(x,\ y) が定義されているとき、 R 内での f(x,\ y) の最大値を求めたい。

ただし f は高速に *1 計算でき、かつそれなりにきれいな関数 *2 であることを期待します。

 

凸性

この記事では、 2 変数関数 f が凸とは、任意の方向への 2 階微分が負であることとします。

あるいは \forall (l_x,\ l_y)\neq (r_x,\ r_y) \in R および 0\lt t \lt 1 に対して、 f(l_x + t (r_x - l_x),\ l_y + t (r_y - l_y)) \gt f(l_x,\ l_y) + t (f(r_x,\ r_y) - f(l_x,\ l_y)) が成立することと言っても良いかもしれません。

 

9 分探索 *3

方針

もし定義域が 1 次元なら、いわゆる 3 分探索や黄金探索が有名です。

2 次元でも似たようなことをしてみましょう。具体的には、区間を 3\times 3=9 個に区切り、中央の 4 点での値に応じて区間を縮めていく方針です。

解法

f(l_x + i \cdot \displaystyle\frac{r_x - l_x}{3},\ l_y + j \cdot \displaystyle\frac{r_y - l_y}{3})\ (i,\ j \in (1,\ 2))

を計算します。この中で一番大きな値を取る点（複数ある場合はそのうちどれでも）を i=i_0,\ j=j_0 とすると、範囲内での最大値を取る点は

\quad \quad l_x + (i_0 - 1)\ \displaystyle\frac{r_x - l_x}{3} \le x \le l_x + (i_0 + 1)\ \displaystyle\frac{r_x - l_x}{3}

\quad \quad l_y + (j_0 - 1)\ \displaystyle\frac{r_y - l_y}{3} \le y \le l_y + (j_0 + 1)\ \displaystyle\frac{r_y - l_y}{3}

の範囲にありそうな予感がします *4 。

なので関係ない区間を削っていくことで、 O(-\log\varepsilon) の計算量で最大値を取ると思われる点の近くが分かります *5 。

もちろん f が変な関数だと正しいとは言えませんし、凸性を仮定しても反例があります *6 が、方向に対する差異が小さい場合 *7 はうまくいく可能性も高いかもしれません。

上に挙げた題材では、方向に対する対称性が高く、また局所解になる可能性も低いのでこれで通すことができます。

AC 解法（PyPy 3）

 

各軸 3 分探索 *8

方針

上で紹介した 9 分探索ではもとの関数にかなり良い性質がある場合でないとうまくいかないかもしれません。この節では、 x 座標、 y 座標のそれぞれで 3 分探索をすることを考えます。この方法は、凸性がある場合にはうまくいくことが保証されるので先ほどの方法より応用範囲が広いかもしれません。

解法

x=x_0 を固定したときの f(x,\ y) の最大値を求めることを考えます。この場合は、 1 次元の場合と同様に y 軸方向に 3 分探索することで O(-\log\varepsilon) で計算することができます。凸性がある場合にはこの正当性が保証されます。

この結果を f_{max}(x) とします。 f_{max} は 1 変数関数なので、今度はこれを x に関して 3 分探索すると、 f_{max} の最大値が得られます。

もとの f が凸の場合、 f_{max} も凸になるので、この結果は元の f の最大値と一致します。計算量は O((-\log\varepsilon)^{2}) です。

 

題材で挙げた問題は、全体で見ると凸ではないのですが、小さい範囲で見るとある程度凸性があるはずなので、たくさん試すと通すことができます。

AC 解法（PyPy 3）

 

*1:O(1) でできることを前提としますが、そうでない場合は全体の計算量がそれだけ重くなります

*2:特に定式化はしません

*3:仮称

*4:予感がするだけです

*5:\varepsilon の定義は適当に解釈してください

*6:斜めに強めの尾根がある場合など

*7:要定義

*8:仮称