Java中使用贪心算法的示例分析

小编给大家分享一下Java中使用贪心算法的示例分析,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!

贪心算法

由于贪心算法本身的特殊性,我们在使用贪心算法之前必须要进行证明,保证算法满足贪心选择性质。具体的证明方法无外乎就是通过数学归纳法来进行证明。但大部分人可能并不喜欢枯燥的公式,因而我这里提供一个使用贪心算法的小技巧。由于贪心算法某种程度上算是动态规划算法的特例,使用条件比较苛刻,因而能够用动态规划解决的问题尽量都是用动态规划来进行先解决,如果在用完动态规划之后,提交时发现问题超时,并且进行状态压缩之后仍然超时,此时我们就可以**考虑使用贪心算法来进行解决。**最后强调一下,我们在使用贪心算法之前,如果要保证解法的绝对正确,一定要对问题进行证明,切记,切记!!

下边我们以区间调度问题为例,来讲一下贪心算法到底该如何取用。

区间调度问题

问题描述:

给你很多形如 [start, end] 的闭区间,请你设计一个算法,算出这些区间中最多有几个互不相交的区间。

举个例子,intvs = [[1,3], [2,4], [3,6]],这些区间最多有 2 个区间互不相交,即 [[1,3], [3,6]],你的算法应该返回 2。注意边界相同并不算相交。

这个问题大眼一看好像有很多贪心策略可供选择,比如我们可以选择区间最短的?或者选择开始最早的?。。。

但是上面几种策略,我们都可以比较容易的举出反例来排除,同时这也是贪心算法的另一个小技巧--虽然好多时候直接证明贪心策略的正确性很难,但是我们可以从反证法入手,对贪心策略进行证伪,排除许多错误的贪心策略。??

好了,说了这么多,那针对该问题正确的贪心策略到底是哪个?

其实正确的思路也比较简单,可以分成下面三步:

  1. 从区间集合中选择一个区间 x,这个 x 是所有区间中结束最早的(end 最小)。

  2. 把所有与 x 区间相交的区间从区间集合中删除掉。

  3. 重复 1 和 2,直到区间集合为空。之前选出的那些 x 的集合就是最大的不想交子集。

这个思路实现成算法的话,可以按照每个区间的 end 数值进行升序排序,因为这样处理以后实现步骤 1 和步骤 2 就会容易很多。

我们通过下面这个动图来辅助理解其整个过程。

Java中使用贪心算法的示例分析

由于我们在计数之前进行了排序,所以所有与 x 相交的区间必然会和 x 的 end 相交;如果一个区间不想与 x 的 end 相交,它的 start 必须要大于或者等于 x 的 end。

具体实现的代码如下:

publicinteraseOverlapIntervals(int[][]intervals){
if(intervals.length==0){
return0;
}
Arrays.sort(
intervals,
newComparator<int[]>(){
@Override
publicintcompare(int[]o1,int[]o2){
returno1[1]-o2[1];
}
});
	//排序后的第一个必然可用
intcount=1;
intx_end=intervals[0][1];
for(int[]interval:intervals){
if(interval[0]>=x_end){
count++;
x_end=interval[1];
}
}
returncount;
}

应用

如果学会了上面的区间调度问题的话,leetCode 上边有两个题目,我们便都可以拿下了。

Java中使用贪心算法的示例分析

这个问题大眼一看好像和我们之前讲的那个区间调度问题毫不相关,但仔细分析一下,好像是一模一样的问题,如果最多有 n 个不重叠的区间,那么就至少需要 n 个箭头穿透所有区间。

Java中使用贪心算法的示例分析

因而问题也就转化成了,寻找不重叠区间的个数,但我们要注意的一点是,在 intervalSchedule 算法中,如果两个区间的边界触碰,不算重叠;而按照这道题目的描述,箭头如果碰到气球的边界气球也会爆炸,所以说相当于区间的边界触碰也算重叠。

Java中使用贪心算法的示例分析

代码实现如下:

publicintfindMinArrowShots(int[][]points){
if(points.length<=0){
return0;
}
//在排序的过程中要考虑溢出情况的发生
Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));
intcount=1;
intx_end=points[0][1];
for(int[]point:points){
if(point[0]>x_end){
count++;
x_end=point[1];
}
}
returncount;
}

总结

本文主要结合一个例子,讲了贪心算法的使用方式。

贪心算法实现起来容易,但难在证明。因而文中提供了两个小窍门辅助判断是否使用贪心算法:

  1. 在使用考虑贪心算法之前,先考虑使用动态规划(考虑状态压缩)解决该问题,如果问题依然超时,则考虑使用贪心算法。

  2. 在确定贪心策略之前,先用一些特殊的例子验证贪心策略的正确性。对于正确的贪心策略,为了保证算法的绝对正确,要通过数学归纳法进行验证。

看完了这篇文章,相信你对“Java中使用贪心算法的示例分析”有了一定的了解,如果想了解更多相关知识,欢迎关注恰卡编程网行业资讯频道,感谢各位的阅读!

发布于 2021-05-30 14:06:50
收藏
分享
海报
0 条评论
166
上一篇:Flask如何搭建一个API服务器 下一篇:PHP关键特性之命名空间的示例分析
目录

    0 条评论

    本站已关闭游客评论,请登录或者注册后再评论吧~

    忘记密码?

    图形验证码