使搜索区间宽度逐次递减 ●设,中的新的探索点为和2。 ●由于搜索区间宽度要按相同比例递减,因此 (3) ●并且,希望在新一轮的搜索中,上次的探索点能够被重复利 用(以减少计算)。不妨设重复利用t为新的探索点,而 2重新选择(1<t2)。 因此,12-1=12-1=0(2-d)=0(b-a)。(由(1) ●由(2,12-1=(20-1%b-a) 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 6 ⚫设[a, t2]中的新的探索点为 1 t 和 2 t 。 ⚫由于搜索区间宽度要按相同比例递减，因此 = − − = − − t a t t t a t a 2 2 1 2 2 。 (3) ⚫并且，希望在新一轮的搜索中，上次的探索点能够被重复利 用（以减少计算）。不妨设重复利用 t1为新的探索点 1 t ，而 2 t 重新选择（ 1 2 t t ）。 ⚫因此， t −t = t −t = (t −a) = (b − a) 2 2 1 2 1 2 。（由(1)） ⚫由(2)，t −t = (2 −1)(b−a) 2 1 。 使搜索区间宽度逐次递减
使搜索区间宽度逐次递减 于是,2=20-1。但这将得到O=1,搜索区间不能递减。 这表明将t用作不合适。 ●将t用作2。 (3,(1)→4-a=0(2-a)=o(b-a)。 (2)→1-a=(-0)(b-a ●于是,02+0-1=0。解三次方程,得s3 ≈0.618 (另一个根舍弃)。 ●这就是0618法的由来。 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 7 ⚫于是， 2 1 2 = − 。但这将得到 =1 ，搜索区间不能递减。 这表明将 t1用作 1 t不合适。 ⚫将 t1用作 2 t 。 ⚫(3), (1) t − a = (t − a) = (b − a) 2 1 2 。 ⚫(2) t −a = (1−)(b−a) 1 。 ⚫于是， 1 0 2 + − = 。解二次方程，得 0.618 2 5 1 − = （另一个根舍弃）。 ⚫这就是 0.618 法的由来。 使搜索区间宽度逐次递减
0.618法 (E>0为输入参数,表示最后区间精度。) 1确定单谷区间a,b为初始搜索区间。 2探索点th2赋初值:←-a+0.382(b-a),q1←-q(1); ta+0.618(-a),φ2φ(t2) 2011年11月 山东大学软件学院 8
2011年11月 山东大学 软件学院 8 （ > 0 为输入参数，表示最后区间精度。） 1 确定单谷区间[a, b]为初始搜索区间。 2 探索点 t1, t2赋初值：t1 a + 0.382(b – a)，1 (t1)； t2 a + 0.618(b – a)，2 (t2)。 0.618法
0.618法 3 while b-a>edo 4 if (p1 <(P2 then 5b←t2,t2←t1,q2←q1 6←a+0.382(b-a),q1←φ(t) else 8 a(t1,t<t2,q1←q2 ←a+0.618(b-a),q2<φ(t2)。 10 endif endwise l2 return t,qp1作为最后求到的最小值估计。 2011年11月 山东大学软件学院
2011年11月 山东大学 软件学院 9 0.618法 3 while b – a > do 4 if 1 < 2 then 5 b t2, t2 t1, 2 1。 6 t1 a + 0.382(b – a)，1 (t1)。 7 else 8 a t1, t1 t2, 1 2。 9 t2 a + 0.618(b – a)，2 (t2)。 10 endif 11 endwhile 12 return t1, 1作为最后求到的最小值估计