黄金分割法

ActionScriptでいきなり実装する前に慣れたPythonで作ってみた。

まず黄金比を求める。

>>> from math import sqrt
>>> sqrt(5)
2.2360679774997898
>>> sqrt(5) / 2 + 0.5
1.6180339887498949
>>> GOLD = _

黄金比の逆数と黄金比引く1が一致することを確認する(一応)

>>> 1 / GOLD
0.61803398874989479
>>> GOLD - 1
0.6180339887498949

1 / GOLD / GOLDをG2にしておく

>>> (GOLD - 1) / GOLD
0.38196601125010515
>>> 1 / GOLD / GOLD
0.3819660112501051
>>> G2 = _

適当な関数を作る。aの時に最小値をとるような関数。aは0.3にしたけどこれは秘密。

>>> def foo(x):
	return (x - a) ** 2

>>> a = 0.3

最小値を探索で求める関数を作る。

>>> def search(start, end):
	diff = end - start
	a = start + G2 * diff
	b = end - G2 * diff
	fa = foo(a)
	fb = foo(b)
	for i in range(10):
		print "f(%f)=%f, f(%f)=%f" % (a, fa, b, fb)
		if fa < fb:
			end = b
			b = a
			fb = fa
			diff = end - start
			a = start + G2 * diff
			fa = foo(a)
		else:
			start = a
			a = b
			fa = fb
			diff = end - start
			b = end - G2 * diff
			fb = foo(b)

			
>>> search(0, 1)
f(0.381966)=0.006718, f(0.618034)=0.101146
f(0.236068)=0.004087, f(0.381966)=0.006718
f(0.145898)=0.023747, f(0.236068)=0.004087
f(0.236068)=0.004087, f(0.291796)=0.000067
f(0.291796)=0.000067, f(0.326238)=0.000688
f(0.270510)=0.000870, f(0.291796)=0.000067
f(0.291796)=0.000067, f(0.304952)=0.000025
f(0.304952)=0.000025, f(0.313082)=0.000171
f(0.299927)=0.000000, f(0.304952)=0.000025
f(0.296821)=0.000010, f(0.299927)=0.000000

fooを11回呼び出すだけで0.299927まで近寄ることができた(秘密の答えは0.3だったね！)

• • • • -

慣れたPythonでデバッグしたのでActionScriptに移植しても一発で動いた。
正確にはFunctionにすべきところをfunctionにしてたんで一発じゃないけど。

class GoldenRatioSearch{
  public static var G2:Number = 0.38196601125010515;
  public static function search(f:Function):Number{
	var diff:Number = 1.0;
	var start:Number = 0.0;
	var end:Number = 1.0;
	var a:Number = start + G2 * diff;
	var b:Number = end - G2 * diff;
	var fa:Number = f(a);
	var fb:Number = f(b);
	for(var i:int=0; i < 10; i++){
	  if(fa < fb){
		end = b;
		b = a;
		fb = fa;
		diff = end - start;
		a = start + G2 * diff;
		fa = f(a);
	  }else{
		start = a;
		a = b;
		fa = fb;
		diff = end - start;
		b = end - G2 * diff;
		fb = f(b);
	  }
	}
	if(fa < fb){
	  return a;
	}
	return b;
  }
}

• • • • -

とりあえずこれを手みやげにSpark Projectに殴り込み参加申し込みしようかな。