三分算法的简单应用

三分算法的简单应用三分算法三分算法求函数极值P1883 Error Curves - 洛谷P5931 灯泡 - 洛谷P2571 传送带 - 洛谷OJ参考三分算法二分法在单调函数上查找特定值或在有序数组中搜索目标依赖于函数在区间内具有单调性从而能够通过一次比较确定目标所在的半区间。但很多问题需要求凹函数或凸函数的极值凹函数在极值点两侧函数的单调性相反一侧递增另一侧递减。此时用二分法取中点时无法通过比较中点处的函数值与某个参考值来判断极值点位于中点的左侧还是右侧因为函数值的大小关系并不能唯一确定方向。三分法适用于求解凸性函数的极值问题二次函数就是一个典型的单峰函数。 三分法与二分法一样它会不断缩小答案所在的求解区间。二分法缩小区间利用的原理是函数的单调性而三分法利用的则是函数的单峰性。至于为什么不用求导的方式求极值是因为某些问题中需要求极值点的单峰函数并非一个单独的函数而是多个函数进行特殊运算得到的函数甚至是抽象函数或分段函数。此时在函数某些点上可能不可导。例如求多个单调性不完全相同的一次函数组成的分段函数的最小值的最大值就不能用求导来求解。三分算法求函数极值设当前求解的区间为[l,r]令m1 l(r-l)/3m2r-(r-l)/3接着计算这两个点的函数值f(m1),f(m2)之后将两点中函数值更优的那个点称为好点若计算最大值则f(m)更大的那个点 就为好点计算最小值同理而函数值较差的那个点称为坏点。可以证明最优点与好点会与坏点同侧。如图所示f(m1)f(m2)则m1是好点而m2是坏点因此最后的最优点会与m1一起在m2的左侧即我们的求解区间由[l,r]变为了[l,m2]。因此根据这个结论我们可以不停缩小求解区间直至得出近似解。 与二分一样我们可以指定三分的次数或是根据r-l的值来终止算法。以求上凸单峰函数的最大值为例三分模板doublefind(doublel,doubler){constdoubledlt1e-10;while(r-ldlt){doublem1l(r-l)/3;doublem2r-(r-l)/3;if(f(m1)f(m2))// m1比m2更靠近极值lm1;elserm2;}returnf(l);// 极值点这里lr}三分算法也可以用在单调函数上但求得的是 2 个端点的值。常出现的题目大致有求某个拥有具体解析式和定义域的函数的极值和优化枚举其中的函数需要现场分析和推理很考验个人的数学能力。P1883 Error Curves - 洛谷[P1883 【模板】三分 / 函数 / ICPC 2010 Chengdu R] Error Curves - 洛谷1435【例题3】曲线一堆二次函数组合在一起的叠加函数因为a 0 a0a0所以在[0,1000]可能单调递增也可能是先单调递减后单调递增。但无论是什么情况这个函数在[0,1000]都可以看做凹函数或单调函数然后对这个函数求最小值可以尝试三分。#includebits/stdc.husingnamespacestd;constdoubledlt1e-11;vectordoublea,b,c;intn;inlinedoublef(doublex){doubleansa[1]*x*xb[1]*xc[1];for(inti1;ia.size();i)ansmax(ans,a[i]*x*xb[i]*xc[i]);returnans;}voidac(){cinn;a.resize(n1,0);bca;for(inti1;in;i)cina[i]b[i]c[i];doublel0,r1000.0;while(r-ldlt){doublem1f(l(r-l)/3);doublem2f(r-(r-l)/3);if(m1m2)// 凹函数m1比m2更接近极值rr-(r-l)/3;elsell(r-l)/3;}printf(%.4lf\n,f(r));}intmain(){// freopen(in.in, r, stdin);intT1;cinT;while(T--)ac();return0;}P5931 灯泡 - 洛谷[P5931 清华集训 2015] 灯泡 - 洛谷1438灯泡题图如图所示但实际上根据D DD和h hh的变化会出现不同的情况。当影子仅出现在地面时如图所示根据三角形的相似性有L D L L x h H \frac{L}{D}\frac{L}{Lx}\frac{h}{H}DL​LxL​Hh​交叉相乘再移项得L h H − h x L\frac{h}{H-h}xLH−hh​x。随着x xx增大当x L D xLDxLD时影子L LL最长否则影子就会有一部分到墙上。影子L LL最长时x D − L H − h H D xD-L\frac{H-h}{H}DxD−LHH−h​D。也就是说当影子在地面上时x H − h H D x\frac{H-h}{H}DxHH−h​D。当影子出现在墙壁时如图所示根据相似三角形的性质有e d f g D − x D \frac{ed}{fg}\frac{D-x}{D}fged​DD−x​即h − L D − x H − L D − x D − x D \frac{h-LD-x}{H-LD-x}\frac{D-x}{D}H−LD−xh−LD−x​DD−x​。2 边同时乘以 2 个分母的乘积得h D − L D D 2 − D x ( H D − x ) ( D − x ) − L ( D − x ) hD-LDD^2-Dx(HD-x)(D-x)-L(D-x)hD−LDD2−Dx(HD−x)(D−x)−L(D−x)将要求的答案L LL移项到左边其余移项到右边得L ( H D − x ) ( D − x ) − h D − D 2 D x − x H D − H x D 2 − D x − D x x 2 − h D − D 2 D x − x H D − H x − D x x 2 − h D − x − x − ( H − h ) D x H D \begin{aligned}L\frac{(HD-x)(D-x)-hD-D^2Dx}{-x}\\\frac{HD-HxD^2-Dx-Dxx^2-hD-D^2Dx}{-x}\\\frac{HD-Hx -Dxx^2-hD }{-x}\\-x-\frac{(H-h)D}{x}HD\end{aligned}L​−x(HD−x)(D−x)−hD−D2Dx​−xHD−HxD2−Dx−Dxx2−hD−D2Dx​−xHD−Hx−Dxx2−hD​−x−x(H−h)D​HD​L − x − ( H − h ) D x H D L-x-\frac{(H-h)D}{x}HDL−x−x(H−h)D​HD是一个对勾函数在x ∈ [ 0 , ∞ ] x\in [0,\infty]x∈[0,∞]是凹函数。题目要求最大的影子长度则函数L LL的定义域应为[ H − h H D , D ] [\frac{H-h}{H}D,D][HH−h​D,D]在这个范围内L LL函数要么是单调函数要么是凹函数但无论是哪一个都能使用三分算法求得极值。[P5931 清华集训 2015] 灯泡 - 洛谷 和1438灯泡 参考#includebits/stdc.husingnamespacestd;doublef(doubleH,doubleh,doubleD,doublex){return(-x-((D*(H-h))/x)HD);}intmain(){// freopen(in.in, r, stdin);intT0;cinT;while(T--){doubleH,h,D;cinHhD;doubleL(H-h)*D/H,RD;while(R-L1e-9){doublem1L(R-L)/3,m2R-(R-L)/3;if(f(H,h,D,m1)f(H,h,D,m2))Lm1;// m2更靠近极值点elseRm2;}printf(%.3lf\n,f(H,h,D,L));}return0;}P2571 传送带 - 洛谷1439【SCOI2010】传送带[P2571 SCOI2010] 传送带 - 洛谷题目测试样例如图容易想到若点E EE固定则F FF从C CC移动 到D DD整体移动时间由长变短再变长这是一个单峰函数此时可以用三分算法。但因为E EE也是动点所以也要对E EE进行枚举。但对E EE的轨迹用二分枚举的话就无法获得下一步行动所以对E EE的轨迹也用三分。这题可以求函数解析式但最后的结果是个二元函数同样是使用三分优化E EE和F FF的枚举这里就不推导了。参考程序#includebits/stdc.husingnamespacestd;usingf64double;f64 ax,ay,bx,by,cx,cy,dx,dy,P,Q,R;booleq(f64 x,f64 y){returnfabs(x-y)1e-9;}voidmidl(f64aim,f64x,f64y){// 左端点收缩aimx(y-x)/3;};voidmidr(f64aim,f64x,f64y){// 右端点收缩aimy-(y-x)/3;};f64dis(f64 x1,f64 y1,f64 x2,f64 y2){// 计算2点间距f64 xx1-x2,yy1-y2;returnsqrt(x*xy*y);}f64tim(f64 x1,f64 y1,f64 x2,f64 y2){// 计算费时f64 dabdis(x1,y1,ax,ay);f64 dcddis(x2,y2,dx,dy);f64 d12dis(x1,y1,x2,y2);returndab/Pdcd/Qd12/R;}f64TCD(f64 x,f64 y){// 枚举F点f64 lxcx,lycy,rxdx,rydy;f64 mlx,mly,mrx,mry;while(!(eq(lx,rx)eq(ly,ry))){midl(mlx,lx,rx),midl(mly,ly,ry);midr(mrx,lx,rx),midr(mry,ly,ry);if(tim(x,y,mlx,mly)tim(x,y,mrx,mry))rxmrx,rymry;// ml更接近最优解elselxmlx,lymly;}returntim(x,y,lx,ly);}f64TAB(){// 枚举E点f64 lxax,lyay,rxbx,ryby;f64 mlx,mly,mrx,mry;while(!(eq(lx,rx)eq(ly,ry))){midl(mlx,lx,rx),midl(mly,ly,ry);midr(mrx,lx,rx),midr(mry,ly,ry);if(TCD(mlx,mly)TCD(mrx,mry))// ml更接近最优解rxmrx,rymry;elselxmlx,lymly;}returnTCD(mlx,mly);}intmain(){// freopen(in.in, r, stdin);cinaxaybxby;cincxcydxdy;cinPQR;printf(%.2lf,TAB());return0;}这题解法很多有模拟退火、暴力枚举、三分嵌套三分这里只举例三分嵌套三分。OJ参考[P1883 【模板】三分 / 函数 / ICPC 2010 Chengdu R] Error Curves - 洛谷1435【例题3】曲线[P5931 清华集训 2015] 灯泡 - 洛谷1438灯泡1439【SCOI2010】传送带[P2571 SCOI2010] 传送带 - 洛谷