注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

三分法——求解凸性函数的极值问题——czyuan原创  

2010-04-03 10:10:44|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

       二分法作为分治中最常见的方法,适用于单调函数,逼近求解某点的值。但当函数是凸性函数时,二分法就无法适用,这时三分法就可以“大显身手”~~


       如图,类似二分的定义Left和Right,mid = (Left + Right) / 2,midmid = (mid + Right) / 2; 如果mid靠近极值点,则Right = midmid;否则(即midmid靠近极值点),则Left = mid;

程序模版如下:

double Calc(Type a)
{
    /* 根据题目的意思计算 */
}

void Solve(void)
{
    double Left, Right;
    double mid, midmid;
    double mid_value, midmid_value;
    Left = MIN; Right = MAX;
    while (Left + EPS < Right)
    {
        mid = (Left + Right) / 2;
        midmid = (mid + Right) / 2;
        mid_area = Calc(mid);
        midmid_area = Calc(midmid);
        // 假设求解最大极值.
        if (mid_area >= midmid_area) Right = midmid;
        else Left = mid;
    }
}

现根据几道的OJ题目来分析三分法的具体实现。

buaa 1033 Easy Problem
http://acm.buaa.edu.cn/oj/problem_show.php?c=0&p=1033

题意为在一条线段上找到一点,与给定的P点距离最小。很明显的凸性函数,用三分法来解决。
Calc函数即为求某点到P点的距离。

ZOJ 3203 Light Bulb
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3203

三分法——求解凸性函数的极值问题——czyuan原创 - 东月之神 - 东月之神


如图,人左右走动,求影子L的最长长度。
根据图,很容易发现当灯,人的头部和墙角成一条直线时(假设此时人站在A点),此时的长度是影子全在地上的最长长度。当人再向右走时,影子开始投影到墙上,当人贴着墙,影子长度即为人的高度。所以当人从A点走到墙,函数是先递增再递减,为凸性函数,所以我们可以用三分法来求解。

下面只给出Calc函数,其他直接套模版即可。
double Calc(double x)
{
    return (h * D - H * x) / (D - x) + x;
}

heru 5081 Turn the corner 08年哈尔滨regional网络赛
http://acm.hrbeu.edu.cn/index.php?act=problem&proid=5081

三分法——求解凸性函数的极值问题——czyuan原创 - 东月之神 - 东月之神


汽车拐弯问题,给定X, Y, l, d判断是否能够拐弯。首先当X或者Y小于d,那么一定不能。
其次我们发现随着角度θ的增大,最大高度h先增长后减小,即为凸性函数,可以用三分法来求解。

这里的Calc函数需要比较繁琐的推倒公式:
s = l * cos(θ) + w * sin(θ) - x;
h = s * tan(θ) + w * cos(θ);
其中s为汽车最右边的点离拐角的水平距离, h为里拐点最高的距离, θ范围从0到90。

POJ 3301 Texas Trip
http://acm.pku.edu.cn/JudgeOnline/problem?id=3301

题意为给定n(n <= 30)个点,求出饱含这些点的面积最小的正方形。

有两种解法,一种为逼近法,就是每次m分角度,求出最符合的角度,再继续m分,如此进行times次,即可求出较为精确的解。(m 大概取10, times取30即可)

第二种解法即为三分法,首先旋转的角度只要在0到180度即可,超过180度跟前面的相同的。坐标轴旋转后,坐标变换为:
X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;

  评论这张
 
阅读(2085)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017