三元探索

三値探索アルゴリズム^[1]は、単峰性関数の最小値または最大値を見つけるコンピュータサイエンスの技術です。

機能

の最大値を求めており、最大値が と の間にあることが分かっていると仮定する。アルゴリズムを適用するには、となるよう な値が存在する必要がある。${\displaystyle f(x)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle x}$

• を満たすすべての場合、 が成り立ち、${\displaystyle a,b}$ ${\displaystyle A\leq a<b\leq x}$ ${\displaystyle f(a)<f(b)}$
• を満たすすべての場合、 が成り立ちます。${\displaystyle a,b}$ ${\displaystyle x\leq a<b\leq B}$ ${\displaystyle f(a)>f(b)}$

アルゴリズム

をある区間 上の 単峰性関数とします。この区間 上の任意の2点とをとります。このとき、3つの可能性が考えられます。 ${\displaystyle f(x)}$ ${\displaystyle [l;r]}$ ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$ ${\displaystyle l<m_{1}<m_{2}<r}$

• ならば、必要な最大値は左側の – には存在しない。つまり、最大値は区間内でのみ探す方が意味がある。${\displaystyle f(m_{1})<f(m_{2})}$ ${\displaystyle [l;m_{1}]}$ ${\displaystyle [m_{1};r]}$
• ならば、対称性までは前述と同様である。ここで、必要な最大値は右側の にはあり得ないので、線分 へ進む。${\displaystyle f(m_{1})>f(m_{2})}$ ${\displaystyle [m_{2};r]}$ ${\displaystyle [l;m_{2}]}$
• の場合、探索は で行われるべきですが、この場合は（コードを簡略化するために）前の2つのケースのいずれかに帰属させることができます。遅かれ早かれ、セグメントの長さは所定の定数よりわずかに短くなり、処理を停止できます。${\displaystyle f(m_{1})=f(m_{2})}$ ${\displaystyle [m_{1};m_{2}]}$

選択ポイントと： ${\displaystyle m_{1}}$ ${\displaystyle m_{2}}$

• ${\displaystyle m_{1}=l+(r-l)/3}$
• ${\displaystyle m_{2}=r-(r-l)/3}$

実行時間順序

${\displaystyle T(n)=T(2n/3)+O(1)=\Theta (\log n)}$ （マスター定理による）

再帰アルゴリズム

def ternary_search ( f , left , right , absolute_precision ) -> float : """left と right が現在の境界です    。最大値はそれらの間にあります。    """ if abs ( right - left ) < absolute_precision : return ( left + right ) / 2      
    


         
             

    左から3番目 =  ( 2  * 左 + 右)  /  3
    右から3番目 =  (左 +  2  * 右)  /  3

     f ( left_third )  <  f ( right_third )
        の場合: ternary_search ( f , left_third , right , absolute_precision )を返します。 そうでない場合: ternary_search ( f , left , right_third , absolute_precision )を返します。   
    
            

反復アルゴリズム

def ternary_search ( f , left , right , absolute_precision ) -> float : """[left, right] の範囲内で単峰関数 f() の最大値を求めます。    最小値を求めるには、if/else 文を逆にするか、比較を逆にします。    """ while abs ( right - left ) >= absolute_precision : left_third = left + ( right - left ) / 3 right_third = right - ( right - left ) / 3      
    


         
                
                

         f ( left_third )  <  f ( right_third )の場合: 
            left  =  left_third 
        、そうでない場合: 
            right  =  right_third

    # 左と右が現在の境界です。最大値はそれらの間にあります。
    return  ( left  +  right )  /  2

参照

• 最適化におけるニュートン法（導関数がゼロになる場所を探すのに使える）
• 黄金分割探索（三項探索に似ており、反復ごとに f の評価にほとんどの時間がかかる場合に便利です）
• 二分探索アルゴリズム（導関数の符号が変化する場所を検索するために使用できます）
• 補間検索
• 指数探索
• 線形探索

参考文献

1. “Ternary Search”. cp-algorithms.com . 2023年8月21日閲覧。