競プロのライブラリ整理~二分探索と三分探索~

Last updated at 2020-12-08Posted at 2020-12-06

#前書き
以下は、二分探索と三分探索の抽象化ライブラリ及びその説明の記事です。

こちらは、二分探索と三分探索を理解している方を想定した記事なので、二分探索と三分探索を理解していない方はまずは他の記事を参照するようにお願いします¹$^,$²$^,$³。

また、以下で繰り返し出てくる全順序集合としては整数または実数の時のみ想定しているので、その他の場合は書き換える必要があることにご注意ください。

#(1)アルゴリズムの説明

二分探索と三分探索のアルゴリズムの簡単な説明を以下でします。

##①二分探索とは

全順序集合上で**広義単調増加関数(または広義単調減少関数)$f$**が定義されている時に$f(y)=x$となる最小(または最大)の$y$を求めるアルゴリズムのことです。探索区間の長さを$n$とした時、探索を行うごとに長さが$\frac{1}{2}$になるので、一回の探索でかかる時間計算量を$O(X)$として$O(X \log{n})$で探索を行うことができます。

##②三分探索とは

全順序集合上で**狭義凸関数(または狭義凹関数)$f$**が定義されている時に$f(y)$が最小値(または最大値)を取る$y$を求めるアルゴリズムのことです。探索区間の長さを$n$とした時、探索を行うごとに長さが$\frac{2}{3}$になるので、一回の探索でかかる時間計算量を$O(X)$として$O(X \log{n})$で探索を行うことができます。

また、広義凸関数(または凹関数)の場合でも解が求まることはありますが局所最適解に陥る可能性があるので、使用する際には狭義であることを確認してください⁴。

#(2)抽象化の説明
##①二分探索の抽象化

まず、先程の二分探索の説明で「$f(y)=x$となる最小(または最大)の$y$を求める」と書きましたが、$f(y)=x$が成り立つ$y$が存在しない場合を考慮すると、「$f(y) \leqq x$となる最小(または最大)の$y$を求める」及び「$f(y) \geqq x$となる最小(または最大)の$y$を求める」とする二分探索を使うべきです。

ここで、上記の二分探索はめぐる式二分探索⁵と呼ばれる実装により簡単に実装することができます。めぐる式二分探索ではある値を境に条件を満たす領域と条件を満たさない領域⁶が二分されることを用いて実装を行います。以降は、めぐる式二分探索を理解していることが必須なので、@drkenさんの記事⁵を参考にしてください。

先程の記事⁵の後半に書いてある通り、領域がFalse,TrueとなってTrueの最小値を求めたい場合だけでなく、逆に領域がTrue,FalseとなってTrueの最大値を求めたい場合もあります。また、逆に言えば二分探索ではこの2パターンで全てのパターンを網羅できるので、この2パターンを抽象化したものをライブラリとします。そして、先程の記事⁵ではabsを用いているのですが、対称性や三分探索の抽象化との共通性を考えてabsを用いずに抽象化を行いました。

##②三分探索の抽象化

アルゴリズムの挙動は二分探索より難解ですが、二分探索の抽象化と三分探索の基本が理解できれば抽象化は難しくありません。ただ、二分探索では定義域でTrue,Falseを返す関数が必要であったのに対し、三分探索では最小値(または最大値)にしたい値を返す関数が必要であることに注意してください。

#(3)抽象化ライブラリの実装

先程の章で抽象化の説明を概ねしたので、抽象化ライブラリのコードの説明をします。

##①二分探索のコードの説明

まず、抽象化をするにあたり以下の二つの条件で場合分けをする必要があります。⁷

①探索したい定義域が整数(0)または実数(1)での場合分け($domain$)
②「領域がTrue,Falseの順でTrueの最大値を求めたい(0)」または「領域がFalse,Trueの順でTrueの最小値を求めたい(1)」での場合分け($searchtype$)

また、これらの場合分けに加え、bool値を返す関数$f$が必要です。

ここで、コンストラクタには**探索範囲($l,r$)及び探索範囲の最小値($eps$)**を与える必要があります。$l,r$については$l<r$だけでなく、$searchtype=0$の時は$f(l)=True$かつ$f(r)=False$,$searchtype=1$の時は$f(l)=False$かつ$f(r)=True$という条件を満たす必要があります。そして、$eps$は$domain=0$の時は1、$domain=1$の時は出力で指定された誤差を与えれば良いです。

以上でコンストラクタに与えた引数の説明をしました。また、ここからcalc関数の説明をしますが、実装はめぐる式二分探索とほとんど同じなので、比較しながら読むと理解しやすいと思います。そして、以下では$searchtype=1$での説明をしますが、$searchtype=0$の時も$l,r$の関係や大小関係を反転させることで同様の議論ができます。また、この逆転を行うために$op2$を導入していますが、if文の条件判定と最終的な返り値の部分のみで用いているので理解は難しくないと思います。

ここで、$searchtype=1$でのcalc関数の内容を説明します。まず、while文の条件式は$eps$以下で探索を終了するだけなので難しくありません。そして、$diff$は二等分点との差の絶対値,$bisection$は二等分点の値です。二等分点を求める際に割り算を行いますが、整数と実数で演算子が異なるので$op1$で指定しています。そして、if文の条件分岐についてはめぐる式二分探索⁵と同じなのでここでは省略します。

以上を行うことで、常に$f(l)=False,f(r)=True$の条件を満たしたまま繰り返し探索範囲が$\frac{1}{2}$されるので、探索終了時の$r$を出力すれば良いです。

##②三分探索のコードの説明

三分探索でも二分探索と同様に以下のような場合分けが必要です。

①探索したい定義域が整数(0)または実数(1)での場合分け($domain$)
②「狭義凹関数$f$の最大値を求めたい(0)」または「狭義凸関数$f$の最小値を求めたい(1)」での場合分け($searchtype$)

ここで、コンストラクタには探索範囲($l,r$)及び探索範囲の最小値($eps$)も与える必要があります。$l,r$は二分探索と違って条件指定はなく、$l\leqq r$のみを満たせば良いです。また、$eps$は$domain=0$の時は2、$domain=1$の時は出力で指定された誤差を与えれば良いです。$domain=0$の時のみ二分探索と異なることに注意してください。

以上でコンストラクタに与えた引数の説明をしました。ここからのcalc関数の説明は$searchtype=1$でしますが、$searchtype=0$の時も$l,r$の関係や大小関係を反転することで同様の議論をできます。また、二分探索の時と同様に$op2$を逆転を表すものとして導入しています。

このもとで、$searchtype=1$でのcalc関数の内容を説明します。まず、while文の条件式は$eps$以下で探索を終了するだけなので難しくありません。ただし、二分探索とは違って整数の場合は$eps=2$にする必要があります。そして、$diff$は三等分点どうしの差の絶対値,$trisection1,trisection2$は三等分点の値です(ただし、$trisection1<trisection2$)。また、三等分点を求める際に割り算を行いますが、整数と実数で演算子が異なるので$op1$で指定しています。そして、if文の条件分岐は通常の三分探索と同じなのでここでは省略します(条件分岐にも流儀がありますが、自分は対称性の良いものにしました。)。

以上を行うことで、$[l,r]$に最小値(or最大値)があるという条件を満たしたまま探索範囲が$\frac{2}{3}$されていくので、探索終了時に$[l,r]$に含まれる中でfの返り値を最小(or最大)にするものを求めれば良いです。また、最小か最大かで求める関数が違うので$op3$で指定しています。

##③機能の追加

以上で二分探索の大半の問題をカバーできますが、以下の二つの問題が発生しうるので改善しました。

###1.誤差の考慮

浮動小数点数には表現できる数に限界があり、epsの値によっては無限ループに陥る可能性があります。そのため、回数を決めうちした二分探索をすると良いです。また、この回数は探索範囲と探索範囲の最小値から求めることができます⁸。

###2.関数fが複数の引数を持つ場合の考慮

関数$f$は定義域に含まれる元のみを引数として持つ場合を想定していましたが、ループ内で用いる場合などは複数の引数を持たせる必要があります。従って、それらの引数もインスタンス変数とすれば良いです。本当はfunctoolsのpartial関数で固定しようと思ったのですが、1.5倍程度遅くなるようだったので今回は使いませんでした。

#(4)コード

(改善点があると思うのでコメントでお願いします！)

##①二分探索(追加機能なし)

binary_search.py

'''
二分探索の抽象化ライブラリ
domain:= 定義域が整数(0)or実数(1)
searchtype:= T→Fで最大値(0)かF→Tで最小値(1)か
f:= boolを返す関数(答えを含む領域でtrueを返す) 
l,r:= 探索範囲(l,rはsearchtypeの条件を満たす,l<r)
eps:= 誤差(整数なら1,実数なら誤差指定による)
op1:= 割り算の演算子
op2:= 反転させるかどうか
value:= 二分探索の解
'''
from operator import floordiv,truediv,truth,not_
class binary_search:
    def __init__(self,domain,searchtype,f,l,r,eps):
        self.domain=domain
        self.searchtype=searchtype
        self.f=f
        self.l,self.r=l,r
        self.eps=eps
        self.op1=[floordiv,truediv][domain]
        self.op2=[not_,truth][searchtype]
        self.value=self.calc()
    def calc(self):
        while self.r-self.l>self.eps:
            diff=self.op1(self.r-self.l,2)
            bisection=self.l+diff
            if self.op2(self.f(bisection)):
                self.r=bisection
            else:
                self.l=bisection
        return [self.l,self.r][self.op2(True)]

##②三分探索(追加機能なし)

ternary_search.py

'''
三分探索の抽象化ライブラリ
domain:= 定義域が整数(0)or実数(1)
searchtype:= 狭義に凹で最大値を求めたい(0)or狭義に凸で最小値を求めたい(1)
f:= 最大または最小にしたい値を返す
l,r:= 探索範囲(l<=r)
eps:= 誤差(整数なら2,実数なら誤差指定による)
op1:= 割り算の演算子
op2:= 反転させるかどうか(0の時反転)
op3:= 出力での反転
value:= 三分探索の解
'''
from operator import floordiv,truediv,truth,not_
class ternary_search:
    def __init__(self,domain,searchtype,f,l,r,eps):
        self.domain=domain
        self.searchtype=searchtype
        self.f=f
        self.l,self.r=l,r
        self.eps=eps
        self.op1=[floordiv,truediv][domain]
        self.op2=[not_,truth][searchtype]
        self.op3=[min,max][searchtype]
        self.value=self.calc()
    def calc(self):
        while self.r-self.l>self.eps:
            diff=self.op1(self.r-self.l,3)
            trisection1=self.l+diff
            trisection2=self.r-diff
            trisection1_value=self.f(trisection1)
            trisection2_value=self.f(trisection2)
            if self.op2(trisection1_value<=trisection2_value):
                self.r=trisection2
            if self.op2(trisection1_value>=trisection2_value):
                self.l=trisection1
        return self.op3([self.l,self.l+self.op1(self.r-self.l,2),self.r],key=self.f)

##③二分探索(追加機能あり)

binary_search_alpha.py

'''
二分探索の抽象化ライブラリ
domain:= 定義域が整数(0)or実数(1)
searchtype:= T→Fで最大値(0)かF→Tで最小値(1)か
f:= boolを返す関数(答えを含む領域でtrueを返す) 
l,r:= 探索範囲(l,rはsearchtypeの条件を満たす,l<r)
iter:= 探索回数
op1:= 割り算の演算子
op2:= 反転させるかどうか(0の時反転)
value:= 二分探索の解
args:= fの引数(iterable)…f(i,args)という形でargsを展開
'''
from operator import floordiv,truediv,truth,not_
from math import log
#答えはvalueに格納
class binary_search:
    def __init__(self,domain,searchtype,f,l,r,eps,args=None):
        self.domain=domain
        self.searchtype=searchtype
        self.f=f
        self.args=args
        self.l,self.r=l,r
        self.iter=int(log((r+1-l)/eps,2.0))+5
        self.op1=[floordiv,truediv][domain]
        self.op2=[not_,truth][searchtype]
        self.value=self.calc()
    def calc(self):
        for _ in range(self.iter):
            diff=self.op1(self.r-self.l,2)
            bisection=self.l+diff
            if self.op2(self.f(bisection,self.args)):
                self.r=bisection
            else:
                self.l=bisection
        return [self.l,self.r][self.searchtype]

##④三分探索(追加機能あり)

ternary_search_alpha.py

'''
三分探索の抽象化ライブラリ
domain:= 定義域が整数(0)or実数(1)
searchtype:= 狭義に凹で最大値を求めたい(0)or狭義に凸で最小値を求めたい(1)
f:= 最大または最小にしたい値を返す
l,r:= 探索範囲(l<=r)
eps:= 誤差(整数なら2,実数なら誤差指定による)
iter:= 探索回数
op1:= 割り算の演算子
op2:= 反転させるかどうか(0の時反転)
op3:= 出力での反転
value:= 三分探索の解
args:= fの引数(iterable)…f(i,args)という形でargsを展開
'''
from operator import floordiv,truediv,truth,not_
from math import log
class ternary_search:
    def __init__(self,domain,searchtype,f,l,r,eps,args=None):
        self.domain=domain
        self.searchtype=searchtype
        self.f=f
        self.l,self.r=l,r
        self.iter=int(log((r+1-l)/eps,1.5))+5
        self.args=args
        self.op1=[floordiv,truediv][domain]
        self.op2=[not_,truth][searchtype]
        self.op3=[max,min][searchtype]
        self.value=self.calc()
    def calc(self):
        for _ in range(self.iter):
            diff=self.op1(self.r-self.l,3)
            trisection1=self.l+diff
            trisection2=self.r-diff
            trisection1_value=self.f(trisection1,self.args)
            trisection2_value=self.f(trisection2,self.args)
            if self.op2(trisection1_value<=trisection2_value):
                self.r=trisection2
            if self.op2(trisection1_value>=trisection2_value):
                self.l=trisection1
        return self.op3([self.l,self.l+self.op1(self.r-self.l,2),self.r],key=lambda x:self.f(x,self.args))