三分探索の一般化および最適化

F

概論

三分探査を一般化し, 棄却領域の大きさを評価することでよりよい三分探査を目指したが, 特に成果は得られなかったため, 元来の三分探査を用いるのがよかろうという結論が導かれた.

導入

三分探査と黄金分割探査

三分探査というものがある.
定義は(準備中).

より効率がよい類似探査として黄金分割探査というものがある.
定義は(準備中).

黄金分割探査は以下の二点から三分探査より優れているとされる

  • 棄却領域がより大きい ( 1/(1+φ)>1/3 ).

  • 計算結果が流用できる.

本題

計算結果の流用についてはこれ以上の議論の余地はないと思われる.

以下, 棄却領域の大きさに主眼を置き,
よりよい三分探査について議論を行う.

三分探査の一般化として比率 r:(1-2r):r の分割を(r-)一般三分探査と呼ぶこととする.
即ち三分探査は r=1/3 であり, 黄金分割探査は r=1/(1+φ) である.

上では考慮されていないが, (一般)三分探査においては, 探査領域の端点の値が最小値を取るとき, 中央領域も棄却できる.
これを考慮したうえで, 最もよい r を求めたい.

棄却領域の実現確率

棄却領域の選択確率を以下のモデル化により定める.

  • 探査領域を [0:1] とする.

  • 極小点は [0:1] 上一様分布とする.

  • 極小点を x_0 としたとき, |x_1-x_0|<|x_2-x_0|⇒f(x_1)<f(x_2) とする.

このとき中央領域が棄却されるのは, 極小点と最も近い探査点が端点であるときである.
その確率は左端右端それぞれについて r/2 であるため, r となる.

棄却領域の大きさに基づく探査のscore

元の探査領域の大きさが d , 許される誤差が e (<d),
一回の探査で探査領域が縮小できる割合が s (<1) であるとき,
探査の回数 n について

が成り立つため, 回数は

を満たす. このことから単位回数あたりの進捗を

と定めることができそうである. このことから縮小率 s に対するscoreを log(1/s) とする.

探査scoreの期待値

中央領域が棄却されるとき, 縮小率は r , この確率は r .
されないとき, 縮小率は 1-r , 確率は 1-r である.
よってsocre期待値は

rlog(1/r)+(1-r)log(1/(1-r)) のグラフ (desmosによる).

これは r=1/2 で最大になる.
破綻.

定性的には, どちらに転んでも半分棄却できる r=1/2 が最高, でも三分探査でなくなってしまうため破綻.
三分探査を保証するためのscoreを盛り込まないとこうなっちゃうようね……

結論

  • 一般化三分探査を棄却領域のみにより評価するためには, scoreに「三分探査実現の担保」を盛り込む必要があり, むずかしい.

  • そもそも棄却領域が定数倍になったところで, scoreが対数になる以上あんまりおいしくないよね. アルゴリズムとしての評価にそれほど影響しないよね. 手を動かす前に気付けばよかったのに.

  • 計算回数を考慮に入れると, 明らかに黄金分割探査が優れていると思われる.

  • 実装の簡便さで言うと, 三分探査が一番負担がないので, きっと俺は三分探査しか使わないだろうね.

この記事が気に入ったらサポートをしてみませんか？