Java教程

算法思想-三分

本文主要是介绍算法思想-三分,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

我认为三分就是就是关于二分的延伸思想,二分用于求解线性的相关问题,三分用于求解单谷凹凸函数的最值问题。
首先简述一下三分
三分思想用于解决一类求解函数的极值的方法(单谷凹凸函数)
有多种创建三分的方法,第一种相对来说更常用,其他的理解想法就行了。他们都是通过两者的值相比较,取其中一方,让 r 或 l 的值移动,进行区间缩小,找到函数顶点
这是第一种创建三分的方法
在这里插入图片描述

int ml = l + (r-l)/3;
int mr = r + 2*(r-l)/3;
if(f(ml) > f(mr) l = ml;//上图所示,应该偏向右边才是顶点
else r = mr;

第二种方式

在这里插入图片描述

int mid = (l+r)/2;
int midmid = mid + (mid+r)/2;
if(f(mid) > f(midmid)) l = mid;
else r = midmid;

第三种

在这里插入图片描述
在二分的很小的范围内找到一个 mid + eps 的点,判断它和 mid 值的大小,这种思路类似于二分,但是思想还是三分,可以自己理解一下。

double eps = -1e18;//表示趋向mid点很小的点,判断两点之间的大小关系就可以
int mid = (l+r)/2;
if(f(mid - eps) > f(mid)) l = mid-eps;
else r = mid;

然后就是用总体的来写出

int l = 0,r = 1e18;	//范围的值,我们从0到1e18
for(int i = 1;i <= 300;i++){
	int ml = l + (l+r)/3;
	int mr = l + 2*(l+r)/3;
	if(f(ml) > f(mr)) l = ml;	//f()函数就是你现在要求的内容,就是将问题转化成凹函数的内容
	else r = mr;
}

例题:
1.hdu 4355
题意:给你数轴上n个点的坐标还有他们的权重 w,让你找一个点,是这个点的距离到其他点的距离三次方再乘上位权的最小。

思路:简单理解一下,一个点到其他点的距离之和最小,那么就先要确定这个点的能取得位置,简单想象一下,这个点取最左边,是不是这个距离之和就非常大。这个点取最右边,同理这个点是不是也非常的大。当可以去的点左右两边同时向中间走的时候,总距离是不是就减小,直到中间可能有一个点取得最小值。具体证明就不用证了。可以将问题转化成用三分求凹函数求最值的问题。

参考代码

2.hdu 3400
题意:在一个二维平面内给定你两条传送带线段,AB和CD。然后在AB传送带上的速度是P,在CD传送带上的速度是Q,在平面其他部分的速度是R,问你从A到D点花费最短的时间是多少?

在这里插入图片描述

思路:我们要从A到D,是需要先从AB上的某个位置E离开,然后走中间的路线,最后到达CD上的某一点F,最后通过CD到达D点(当然AB和CD这两部分可以不走)

为什么要这样考虑呢?
因为 |AE|P/+|EF|/R 的值可能小于直接走 |AF|/R 的值。
另 g = |AE|P/+|EF|/R
所以我们先固定点 F,开始考虑从 A 到 F 的最短距离是在哪个点 E
很明显,我们固定 F 点以后,我们让 E 点从 A 到 B ,路径值 g 是先减小后增大的一个关系
再另 f = |FD|/Q
这是否让 F 的位置改变,FD的大小是一个递减函数,结合 g 值,f + g 总体是一个先减后增的函数,然后就可以使用三分找最值。

参考代码

3.buctoj周赛(5)逃离
三分的题目一般都是思维题目,只要能将问题转化为三分就好解决,这个题目转化上相对不好理解一些,可以参考学习一下


4.Turn the Corner
在这里插入图片描述
汽车拐弯问题,给定 X,Y,l,d 值当你考虑完过后,你会很容易想到,汽车拐弯无非是向前走(最上面的点不能超过墙),或者是在墙角的点转动(最左边的点不能超过墙),最后其实只要考虑最上面的点就行了。因为每当绕墙转动(随着角度变化改变),最左边的点碰到墙时,你就可以让车向前走,相应的增加的是最大高度 h 的值,所以总体来看你只需考虑最大高度 h 即可。
我们模拟发现,h 的值是先增大后减小的,所以可以看成一个凸函数,找最大值就可以了。
关键是找出 h 的函数:

s = l*cos(θ) + w*sin(θ) - x;
h = s*tan(θ) + w*cos(θ);	//θ 就是0 - pi/4

代码参考链接


总体来说,三分的内容与二分相似,大多结合思维题,就是将问题的模型转变成三分比较困难,如果能转化问题就迎刃而解了

这篇关于算法思想-三分的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!