一般の数列を三分探索すると極小点が求まるとは限らない

概要

三分探索を行うと極小点が $1$ つも求まらないような数列を構成した。また、一般の数列に対して $\Theta(\log (N))$ の時間計算量で極小点を $1$ つ求めるアルゴリズムを説明する。

定義

$A = (A _ 1, A _ 2, \dots, A _ N) ~ (N \geq 1)$ を実数列とする。整数 $i ~ (1 \leq i \leq N)$ が $A$ の極小点であることを、 $A _ {i - 1} \geq A _ {i}, ~ A _ {i} \leq A _ {i + 1}$ を満たすことと定義する。ただし仮想的に $A _ 0 = A _ {N + 1} = + \infty$ とする。

三分探索

$A$ が丁度 $1$ つの極小点を持つとき、三分探索を用いると $A$ に $\Theta(\log (N))$ 回アクセスすることでその極小点を求めることができる。三分探索は以下のようなアルゴリズムである。

最初、 $(l, r) := (0, N + 1)$ とする。「 $A$ の極小点 $i$ が $l \lt i \lt r$ を満たす」という条件を維持したまま $r - l$ を狭めていく。

$\textrm{(i)}$ $r - l = 2$ の場合

$(l + r) / 2$ が極小点であり、アルゴリズムを終了する。
$\textrm{(ii)}$ $r - l \geq 3$ の場合

$(l', r') := (\lfloor (2l + r) / 3 \rfloor, \lfloor (l + 2r) / 3 \rfloor )$ とする。 $(l, (2l + r) / 3, (l + 2r) / 3, r)$ は隣接項の差が $1$ 以上であるから、それぞれに floor 関数を適用した $(l, l', r', r)$ は狭義単調増加列になることに注意。
- $\textrm{(ii - i)}$ $A _ {l'} \lt A _ {r'}$ の場合
  
  $(l, r) \leftarrow (l, r')$ と更新して繰り返す。
- $\textrm{(ii - ii)}$ $A _ {l'} \gt A _ {r'}$ の場合
  
  $(l, r) \leftarrow (l', r)$ と更新して繰り返す。

$\textrm{(ii)}$ が起こるたびに $r - l$ は $\lceil 2(r - l) / 3 \rceil$ 以下になるから、時間計算量は $\mathrm{O}(\log (N))$ である。

三分探索で極小点が求まらないような一般の数列

$N = 26$ の例を図示した。数列ではなく関数のグラフになっているが、適当に離散化して考えて欲しい。

f:id:noshi91:20220313203519j:plain

$3$ 回のイテレーションの後 $(l, r) = (9, 17)$ となり、極小点が存在しないことが分かる。

一般の数列に対して、極小点を $1$ つ求めるアルゴリズム

黄金分割探索は、一般の数列に対しても $1$ つ極小点を求めることができる (詳細略)。本記事では、黄金分割探索とは異なるアルゴリズムを説明する。

最初 $(l, m, r) := (0, \lceil N / 2 \rceil, N + 1)$ とする *1。「 $l \lt m \lt r$ かつ $A _ l \geq A _ m, ~ A _ m \leq A _ r$ 」を満たすという条件を保ちつつ、 $r - l$ を狭めていく。

$\textrm{(i)}$ $r - l = 2$ の場合

$l + 1 = m = r - 1$ であり、不変条件から $m$ が極小点である。アルゴリズムを終了する。
$\textrm{(ii)}$ $r - l \geq 3$ の場合

$(l ^ {\prime}, r ^ {\prime}) := (\lfloor (l + m) / 2 \rfloor, \lceil (m + r) / 2 \rceil)$ とする。 $l \leq l' \lt m \lt r' \leq r$ である。
- $\textrm{(ii - i)}$ $A _ {l'} \lt A _ m$ の場合
  
  不変条件と併せて $A _ l \geq A _ m \gt A _ {l'}$ である。特に $A _ l \neq A _ {l'}$ より $l \lt l'$ も満たされるため、 $(l, m, r) \leftarrow (l, l', m)$ と更新して繰り返す。
- $\textrm{(ii - ii)}$ $A _ {m} \gt A _ {r'}$ の場合
  
  $\textrm{(ii - i)}$ の場合と対称である。 $(l, m, r) \leftarrow (m, r', r)$ と更新して繰り返す。
- $\textrm{(ii - iii)}$ $A _ {l'} \geq A _ m, ~ A _ m \leq A _ {r'}$ の場合
  
  $(l, m, r) \leftarrow (l', m, r')$ と更新して繰り返す。