2010年3月6日土曜日

三分探索

三分探索.二分探索じゃなくて三分探索.

二分探索は,単調関数の零点を求めるのに使われますが,
三分探索は,凸関数の極値を求めるのに使われます.

参考

実数探索三種類解説 - nodchipの日記
http://d.hatena.ne.jp/nodchip/20090303/1236058357

3分探索 - ICPC突破専用ザク
http://d.hatena.ne.jp/ir5/20090630/1246349028

fを上に凸な関数とします.
区間[a, b]を3等分して[a, c1], [c1, c2], [c2, b]の3つの区間をつくります.
この時,極大値は,上の3区間の内のどれかにあり,以下が成立します.

・極大値が[a, c1]にある(Fig.1)
⇒f(c1)>f(c2)が成立.b=c2とする.
・極大値が[c1, c2]にある(Fig.2)
⇒a=c1となってもb=c2となってもよい .
・極大値が[c2, b]にある(Fig.3)
⇒f(c1)<f(c2)が成立.a=c1とする.



Fig.1


Fig.2


Fig.3

言い換えれば,
f(c1)>f(c2)⇒極大値は[a, c2]に存在
f(c1)<f(c2)⇒極大値は[c1, b]に存在

よって,各ステップ毎に探索空間を2/3にすることが出来ます.

これを実装すると下のようになります.


double search(double left, double right, int iteration){
for(int i=0;i if(f((left*2+right)/3)>f((left+right*2)/3))
right=(left+right*2)/3;
else
left=(left*2+right)/3;
}
return (left+right)/2;
}


・例1
f(x)=x-x
df/dx=(-ln(x)-1)x-x
ですので,
df/dx=0
とおけば,
x=1/e≒0.367879441
となります.

結果:
初期値
[0, 4]
100回反復計算させた時の解
x=0.3678794519063162

・例2
鋸波
x-floor(x)
連続関数ですが,x∈Zの時は微分不可能であり極大値をとります.

結果:
初期値
[0, 4]
100回反復計算させた時の解
x=1.9999999999999996
上手く計算できたようです.

・例3
δ関数っぽいもの
δ関数は,
δ(x)=0 (x≠0)
δ(0)=∞
ですが,それっぽいものとして,

f(x)=0 (x≠0)
f(0)=1
に三分法を適用.

結果:
初期値
[-2, 2]
100回反復計算させた時の解
x=1.9999999999999996

駄目でした.連続で無いとやはり無理ですね.

0 件のコメント: