三分法求单峰函数极值

xiaoxiao2025-11-07  7

给一个下凸的函数,求其最小值

三分法,设当前区间在[L,R]

取三分点x1,x2

则区间被分为三块 [L,x1],[x1,x2],[x2,R]

这个时候看f(x1),f(x2)的关系

如果f(x1)<f(x2)说明解在[L,x2]中

否则如果说明解在[x1,R]当中

注意这里取得是x1(比较靠左的端点),就是为了解决x1,x2分别位于峰值的两边的情况,因为这样的话无论怎么搞都会将峰值囊括进去

重复上述过程,直到 L-R<EPS(精度要求)即可

例题 BZOJ1857

先占个坑

转载请注明原文地址: https://www.6miu.com/read-5039225.html

最新回复(0)