最適化アルゴリズム-フィボナッチ数列検索
4698 ワード
フィボナッチ数列の検索は、Edwinの「最適化導論」第4版7.3章を参照して、アルゴリズムはgo言語で実現します.
/*****************************************
* FileName : fibonacci_search.go
* Author : fredric
* Date : 2017.09.01
* Note :
* History :
*****************************************/
package search
import(
"fmt"
)
func _get_fibonacci(i int) int{
if i == 1 {
return 1
}else if i == 2{
return 2
}else{
return _get_fibonacci(i - 1) + _get_fibonacci(i - 2)
}
}
func _test_func(x float64) float64 {
return x*x*x*x - 14*x*x*x + 60*x*x - 70*x
}
func _test_func_01(x float64) float64 {
return (x - 1) * (x - 1)
}
/*
* p
* p ,
* p1 = 1 - FN/FN+1
* p2 = 1 - FN-1/FN
* ...
* PN = 1 - F1/F2
* :p1*p2*..pN = 1/FN+1
* F N+1
*/
func DoFibonnaciSearch(){
fmt.Println("DoFibonnaciSearch")
// 0.2
// 1 + 2e/F N + 1 <= /
// e , 0.05
// N
a0 := 0.0
b0 := 2.0
p := 0.0
delta := 0.05 //
for i := 5; i >=1; i-- {
if i != 1 {
fmt.Printf("a0 = %f, b0 = %f
", a0, b0)
//
p1 := _get_fibonacci(i)
p0 := _get_fibonacci(i - 1)
p = 1 - float64(p0)/float64(p1)
a1 := a0 + p * (b0 - a0)
b1 := a0 + (1 - p) * (b0 - a0)
f_a1 := _test_func_01(a1)
f_b1 := _test_func_01(b1)
if f_b1 > f_a1 {
b0 = b1
}else{
a0 = a1
}
fmt.Printf("a1 = %f, b1 = %f f_a1 = %f, f_b1 = %f p = %f
", a1, b1, f_a1, f_b1, p)
}else{
a1 := a0 + (1/2 - delta) * (b0 - a0)
b1 := a0 + (1/2 - delta) * (b0 - a0)
f_a1 := (a1 - 1) * (a1 - 1)
f_b1 := (b1 - 1) * (b1 - 1)
if f_b1 > f_a1 {
b0 = b1
}else{
a0 = a1
}
}
}//for i := 5; i >=1; i-- {
fmt.Printf("a0 = %f, b0 = %f", a0, b0)
}