对极值问题的探索

1.三分法

在对区间做二分查找之前,我们要保证这个区间是有序的,二分法适用于单调函数。对于非单调函数,二分法就不适用了,需要使用一种新的方法——三分法。

三分法首先把待求区间分成三份

mid1=L+(R-L)/3

mid2=R-(R-L)/3

比较f(mid1)和f(mid2)谁更靠近极值,若f(mid1)更靠近极值,则将右区间改为mid2,若f(mid2)更靠近极值,则将左区间改为mid1,再次计算mid1和mid2。重复以上过程,直至L+eps>R(eps为设置的误差值)

三分法适用于单峰函数的求极值。

#define eps 10e-6
double f() {} //计算题目所需要的值
while(l+eps<r)
{
    m1=l+(r-l)/3;
    m2=r-(r-l)/3;
    v1=f(m1);
    v2=f(m2);
    if(v1<v2)l=m1;
    else r=m2;
}

例题:

我们用dfs跑一遍较小的数据之后发现,最优解中每个小弟携带的物品都基本相同。也就是说,n件物品,分配给x个小弟,每个小弟得到n/x件物品时得到最优解。

但是还有一个小小的问题,n/x有余数怎么办?

很简单,让n%x个小弟多带一件物品就好了。也就是让(x-n%x)个小弟携带n/x件物品,让n%x个小弟携带n/x+1件物品。

据此,我们可以列出这样一个式子:

$ans=(x-n \bmod x)*(s+(\frac{n}{x})*(\frac{n}{x}))+(n \bmod i)*(s+(\frac{n}{x}+1)* (\frac{n}{x}+1))$
ll f(ll x)
{
	ll unit = n / x;//(n/x)算出每件物品的单价,也是(x-surplus)个小弟携带的物品件数
	ll surplus = n % x;//剩余的小弟多携带一件
	ll ans = (x - surplus) * (s + unit * unit) + surplus * (s + (unit + 1) * (unit + 1));
	return ans;
}

重点来了:写出f(x)之后,直接套上三分法的代码就可以了。但是这题有点特殊,这题求出的极值点须为整数,所以我们要优化一下三分法的代码。

ll SanFen(ll l, ll r) //找凸点
{
	while (l<r-1)
	{
		ll mid1 = l + (r - l) / 3;
		ll mid2 = r - (r - l) / 3;
		if (mid1 == l && mid2 == r)break;//增加的代码
		if (f(mid1) < f(mid2))
			r = mid2;
		else
			l = mid1;
	}
	ll minn = LLONG_MAX;//以下均为增加的代码
	for (ll i = l; i <= r; i++)//求出极值点所在区间
	{
		ll temp = f(i);
		if (temp < minn)minn = temp;
	}
	return minn;
}

上述代码比之前给出的模板代码增添了几行,为什么呢?把if (mid1 == l && mid2 == r)break;这行注释之后可以发现,程序进入了死循环中。因为本题中变量类型均为long long,而整数相除的误差又相对较大,所以程序运行到最后mid1永远等于l,mid2永远等于r。此时L、R差值较小,[L,R]为极值点所在区间,所以可以跳出循环用for循环在求出的极值点所在的区间去尝试求出极值。

再来看下一题

首先列出计算公式。可以很容易推出先增加攻击力再攻击恶龙。所以设增加攻击力次数为x,公式为$\frac{c}{a+b*x}+x$

ll f(ll x)
{
	ll sum = c / (a + b * x) + x;
	if (c % (a + b * x))sum++;
	return sum;
}

随便创造了一个很大的数据,画图看看效果。(图为函数部分图像)

很明显存在一个极值,直接套整数三分公式:

糟糕,出错了...使用的都是标准模板,为什么还会出错呢?

有幸获取到了本题的输入数据,跑了一遍,果然发现了几个错误结果。

以1 1 267974913236856316这个数据为例展开分析吧,程序输出1035325868,标准答案1035325867。

首先看到这个数据,心就凉了半截,这个数据足够大所以很容易覆盖到非常边角的bug,又不太好找出bug。既然最小值出错了,那么找到的极值点肯定也是错的。开循环试了一下程序找到的极值点周边的数,果然正确的极值点比程序找到的极值点偏移了两万多...

确定了问题,却一直找不到bug在哪,最后不得不把极值点周围的函数图象画出来找bug......

从图像上看,极值点非常“明显”。但实际上,在范围为40000的区间内,y的值差异极小(MATLAB默认使用double类型,所以有小数点)如果不使用double类型而使用整型,函数图象在此区间几乎成一条直线。三分函数在逼近极值点的时候,进入了错误的区间,最后找到的极值点就是错误的。因为是在靠近极值点的区域进入了错误的区间,所以极值点偏移的不多,最后求出的极值误差往往也只在个位数。

而要解决这个问题,要么使用double类型的三分函数(double类型无法取模),要么我们回归原始,用一种我们很熟悉的方法去做:

2.求导

回忆一下公式:$y=\frac{c}{a+b*x}+x$

求导:$-\frac{b}{(a+b*x)^{2}}+1$

令导数为0,求出极值点$x=\sqrt{\frac{c}{b}}-\frac{a}{b}$

还要注意两个地方,一个是求出的导数可能是负数,此时只要计算x=0时的值就可以了。还有一个是整型除法的误差问题,求出极值点后还要在该点左右取几个点求极值。

3.模拟退火算法

还没写,大概率会鸽了,但是欢迎你时常回来看看并催更。

总结

三分法适用于数据较小,极值点周围y的值差异较大的情况。求导可用于数据较大的情况,但是f(x)中如果有mod运算则在大多数情况下无法使用。

参考链接:https://blog.csdn.net/caduca/article/details/43526375

特别感谢涂涂、罗少和范总的帮助。

文章标题:对极值问题的探索
文章链接:https://intmain0.com/104/
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处
评论和私信会在第一时间回复。如果您觉得文章对您有帮助,可以点击文章右下角【分享】一下。您的鼓励是博主的最大动力!
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇