您的位置: 首页  >  文章  >  三分查找求最值及其应用

三分查找求最值及其应用

分类: 文章 • 2024-12-11 15:27:58

一. 概念

 
在二分查找的基础上，在右区间（或左区间）再进行一次二分，这样的查找算法称为三分查找，也就是三分法。
三分查找通常用来迅速确定最值。

二分查找所面向的搜索序列的要求是：具有单调性（不一定严格单调）；没有单调性的序列不是使用二分查找。
与二分查找不同的是，三分法所面向的搜索序列的要求是：序列为一个凸性函数。通俗来讲，就是该序列必须有一个最大值（或最小值），在最大值（最小值）的左侧序列，必须满足不严格单调递增（递减），右侧序列必须满足不严格单调递减（递增）。如下图，表示一个有最大值的凸性函数：

三分查找求最值及其应用

二、算法过程

（1）、与二分法类似，先取整个区间的中间值mid。
[cpp] view plain copy
  1. mid = (left + right) / 2;    

（2）、再取右侧区间的中间值midmid,从而把区间分为三个小区间
[cpp] view plain copy
  1. midmid=（mid+right）/2;  


（3）、我们mid比midmid更靠近最值，我们就舍弃右区间，否则我们舍弃左区间？。
比较mid与midmid谁最靠近最值，只需要确定mid所在的函数值与midmid所在的函数值的大小。当最值为最大值时，mid与midmid中较大的那个自然更为靠近最值。最值为最小值时同理。
[cpp] view plain copy
  1. if (cal(mid) > cal(midmid))    
  2.     right = midmid;  //mid大，则一定要选择包含mid区间的  
  3. else    
  4.     left = mid;  //midmid大，则选择的区间要包含midmid  
（4）、重复（1）（2）（3）直至找到最值。
 
 
算法的正确性：
1、mid与midmid在最值的同一侧。由于凸性函数在最大值（最小值）任意一侧都具有单调性，因此，mid与midmid中，更大（小）的那个 数自然更为靠近最值。此时，我们远离最值的那个区间不可能包含最值，因此可以舍弃。
2、mid与midmid在最值的两侧。由于最值在中间的一个区间，因此我们舍弃一个区间后，并不会影响到最值
 
注：假如是取最大值，则mid和midmid中谁大谁更靠近最终的结果，于是最终选择的区间一定要包含较大者；同样取最小值也是这样的。

三、具体实现  

[cpp] view plain copy
  1. const double EPS = 1e-10;    
  2.     
  3. double calc(double x)    
  4. {    
  5.     // f(x) = -(x-3)^2 + 2;     
  6.     return -(x-3.0)*(x-3.0) + 2;    
  7. }    
  8.     
  9. double ternarySearch(double low, double high)    
  10. {    
  11.     double mid, midmid;    
  12.     while (low + EPS < high)    
  13.     {    
  14.         mid = (low + high) / 2;    
  15.         midmid = (mid + high) / 2;    
  16.         double mid_value = calc(mid);    
  17.         double midmid_value = calc(midmid);    
  18.         if (mid_value > midmid_value)    
  19.             high = midmid;    
  20.         else    
  21.             low = mid;    
  22.     }    
  23.     return low;    
  24. }                                                                                                      

四、应用实例

题目列表 > 集会

时间限制: 2000ms 内存限制: 256MB

描述
        在一条河的一侧，分布着 N 个村庄。这些村庄平日里需要一些贸易往来，然而商人们来回走遍每一座村庄是非常辛苦的，于是他们决定每个月都在河边举行一次集会，大家都来集会上购买需要的物品。然而在集会地点的选择上，大家却有分歧，因为谁都不愿意集会的地点离自己村庄非常远。经过一番激烈的讨论之后，大家决定要将集会地点挑选在这样一个位置：它离最远的村庄的距离要尽可能的近。

        我们把河看做一条足够长的直线，河岸就是平面坐标系上 y = 0 的这条线，y < 0 的区域是河水，而所有村庄都在 y ≥ 0 的区域里。现在给出所有村庄的平面坐标，你要在河岸上找到这样一个位置，使得它到所有村庄的最远距离最小。

输入
        输入文件包含多组测试数据。

        第一行，给出一个整数 T，为数据组数。接下来依次给出每组测试数据。

每组数据的第一行是一个整数 N，表示村庄的数量。接下来 N 行，每行有两个实数 xi 和 yi，表示每一个村庄的坐标。

输出
        对于每组测试数据，输出一行”Case #X: Y”，其中 X 表示测试数据编号，Y 表示集会地点的 x 坐标值，要求与正确答案的绝对误差在10-6以内。所有数据按读入顺序从 1 开始编号。

数据范围
        小数据：T ≤ 100, 0 < N ≤ 50, 0 ≤ |xi|, yi ≤ 10000

        大数据：T ≤ 10, 0 < N ≤ 50000, 0 ≤ |xi|, yi ≤ 10000

样例输入
1
5
0 8
1 6
4 4
-5 7
-6 1
样例输出
Case #1: -1.000000

 

思路：

       看这个题目第一眼觉得这精度要求也太高了吧，，
       现在在反过来分析下这个题目。

       考虑用三分查找，来处理。
       对于具有单调性质的问题可以用二分查找。例如，在一个已排序的数组中，查找一个数，可以用二分查找。

但当函数是凸性函数时，二分法就无法适用，这时就可以用三分查找了。。。。

 

代码：

[html] view plain copy
  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cmath>  
  4. #define N 50005  
  5. using namespace std;  
  6. #define sqr(x) ((x)*(x))  
  7.   
  8. double xx[N] , yy[N];  
  9. int n;  
  10.   
  11. double cal(double x)  
  12. {  
  13.     double ans = 0;  
  14.     for (int i = 1 ; i <= n ; ++ i)  
  15.         ans = max(ans , sqrt(sqr(xx[i] - x) + sqr(yy[i])));  
  16.     return ans;  
  17. }  
  18.   
  19. int main1()  
  20. {  
  21.     int ca = 0;  
  22.     int n;cin>>n;  
  23.     while (n--)  
  24.     {  
  25.         scanf("%d",&n);  
  26.         for (int i = 1 ; i <= n ; ++ i)  
  27.             scanf("%lf%lf" ,&xx[i] , &yy[i]);  
  28.         double l = -10000 , r = 10000 , m1 , m2;  
  29.         // 5e-7是5*10的-7次方。  
  30.         while (r - l >= 5e-7)  
  31.         {  
  32.                         // m1处于1/3处  
  33.                         // m2处于2/3处  
  34.             m1 = (l * 2 + r) / 3.0;  
  35.             m2 = (r * 2 + l) / 3.0;  
  36.             double v1 = cal(m1) , v2 = cal(m2);  
  37.             if (v1 < v2)  
  38.                 r = m2;  
  39.             else l = m1;  
  40.         }  
  41.         printf("Case #%d: %lf\n" , ++ ca , l);  
  42.     }  
  43.                 system("pause");  
  44.     return 0;  
  45. }  

相关推荐