托付，别再问我贪心算法了！（不是贪心算法）-人工智能-知优网

在求三角形最短路径和时，能否用贪心算法求解。所以本文打算对贪心算法进行简单地介绍，介绍完之后我们再来看看是否这道三角形最短路径问题能用贪心算法来求解。

前语

在求三角形最短途径和时，能否用贪心算法求解。所以本文计划对贪心算法进行简略地介绍，介绍完之后咱们再来看看是否这道三角形最短途径问题能用贪心算法来求解。

本文将会从以下几个方面来介绍贪心算法

什么是贪心算法
贪心算法例题详题
贪心算法适用场景
再看三角形最短途径和是否能用贪心算法求解

什么是贪心算法

贪心算法是指在每个阶段做挑选的时分都做出当时阶段(或状况)最好的挑选，而且希望这样做到的成果是大局最优解(但未必是大局最优解)

贪心算法其实是动态规划的一种,因为它的「贪心」，只着眼于当时阶段的最优解，所以每个子问题只会被核算一次，假如由此能得出大局最优解，相关于动态规划要对每个子问题求大局最优解，它的时刻杂乱度无疑是会下降一个量级的。

举个简略的比方，比方给定某个数字的金额(如 250)与 100, 50, 10, 5, 1 这些纸币(不定量)，怎样能用最少张的纸币来兑换这张金额呢，显着每次兑换应该先从大额的纸币兑换起，第一次选 100，第2次仍是选 100，第三次选第二大的 50 元，每次都选小于剩余金额中的最大面额的纸币，这样得出的解必定是大局最优解!时刻杂乱度无疑是线性的。

咱们先来看几道能够用贪心算法来求解的例题

贪心算法例题详题

分糖块

有 m 个糖块和 n 个孩子。咱们现在要把糖块分给这些孩子吃，可是糖块少，孩子多(m < n)，所以糖块只能分配给一部分孩子。每个糖块的巨细不等，这 m 个糖块的巨细别离是s1，s2，s3，……，sm。除此之外，每个孩子对糖块巨细的需求也是不相同的，只需糖块的巨细大于等于孩子的对糖块巨细的需求的时分，孩子才得到满意。假定这 n 个孩子对糖块巨细的需求别离是 g1，g2，g3，……，gn。那么怎样分配糖块，能尽或许满意最多数量的孩子呢?

求解：这道题假如用贪心来解解题思路仍是比较显着的，关于每个小孩的需求 gn，只需给他一切巨细大于 gn 的糖块中的最小值即可，这样就能把更大的糖块让给需求更大的小孩。整个代码如下：

publicclassSolution{
/**
*获取能分配给小孩且契合条件的最多糖块数
*/
privatestaticintdispatchCandy(int[]gList,int[]sList){
Arrays.sort(gList);//小孩对糖块的需求从小到大摆放
Arrays.sort(sList);//糖块巨细从小到大摆放
intmaximumCandyNum=0;
for(inti=0;i<gList.length;i++){
for(intj=0;j<sList.length;j++){
//挑选最接近小孩需求的糖块，以便让更大的糖块满意需求更大的小孩
if(gList[i]<=sList[j]){
maximumCandyNum++;
//糖块被选中，将其置为-1，代表无效了
sList[j]=-1;
//当时小孩糖块已选中，跳出
break;
}
}
}
returnmaximumCandyNum;
}
publicstaticvoidmain(String[]args){
//小孩对糖块的需求
int[]gList={1,2,4,6};
//糖块实践巨细
int[]sList={1,2,7,3};
intresult=dispatchCandy(gList,sList);
System.out.println("result="+result);
}
}

无堆叠区间

给定一个区间的调集，找到需求移除区间的最小数量，使剩余区间互不堆叠。留意:能够以为区间的结尾总是大于它的起点。区间 [1,2] 和 [2,3] 的鸿沟彼此“触摸”，但没有彼此堆叠。
示例 1: 输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解说: 移除 [1,3] 后，剩余的区间没有堆叠。
示例 2: 输入: [ [1,2], [1,2], [1,2] ] 输出: 2 解说: 你需求移除两个 [1,2] 来使剩余的区间没有堆叠。
示例 3: 输入: [ [1,2], [2,3] ] 输出: 0 解说: 你不需求移除任何区间，因为它们已经是无堆叠的了。

区间堆叠能够在生活中的许多场景里找到，比方使命调度，一个工人在一段时刻内需求完结多项使命，每个使命需求完结的时刻不同，怎样在这段时刻内让工人尽或许多地完结这些使命呢(使命与使命之间进行的时刻不能堆叠，一个工人不行能在同一段时刻内一起进行两项使命)

解题思路: 这道题咱们别离用动态规划和贪心算法来解一下，以便比照一下两者的时刻杂乱度，看下贪心算法是否在时刻杂乱度上更优胜一些。

动态规划解法

首要为了便利求解，咱们把每个区间按区间的起始点从小到大进行排序，如图示

接下来咱们套用上篇中的说的动态规划解题四步曲来看看怎样用动态规划进行求解。

1、判别是否可用递归来解

其实直观地看上面咱们排好序的各个区间，这不便是个组合吗，每个区间要么选，要么不选，把一切的组合穷举出来，再看哪个组合最契合标题中的条件，所以无疑是能够用递归的(组合用递归怎样解，强烈主张看下这篇文章)。

不过这题的组合有点特别，前后两个区间有条件约束，假如当时区间与前一个区间堆叠，则这两者只能取其一(另一个需求剔除去防止堆叠)，所以咱们有如下思路：

界说两个值, pre , cur ，别离代表前一个区间与当时区间，需求进行如下进程

比较前一个区间的结尾与当时区间的起始值
假如前一个区间的结尾小于当时区间的起始值，代表两区间不堆叠，则将 pre 置为 cur, cur 置为 cur + 1, 开端接下来紧邻的两个区间的判别(即重复进程 1)。
假如前一个区间的结尾大于当时区间的起始值，代表两区间堆叠，则 pre 不变, cur 置为 cur + 1 (行将 cur 对应的区间移除)，留意此刻移除区间数要加 1, 然后开端接下来 pre，cur+1 区间的判别(即重复进程 1)。

注：初次区间遍历咱们界说 pre = -1，cur = 0

从以上的描绘中能够很显着地看到存在递归现象，所以咱们写出了如下代码,要害代码都作了具体的注释。

publicclassSolution{
//区间类，包含起始值和停止值
privatestaticclassInterval{
intstart;
intend;
Interval(intstart,intend){
this.start=start;
this.end=end;
}
}
privatestaticIntegerremoveDuplicateIntervas(Interval[]intervals){
//将区间按起始点由小到大进行排序
Arrays.sort(intervals,Comparator.comparingInt(a->a.start));
//初次遍历从-1,0开端
returnremoveSubDuplicate(-1,0,intervals);
}
privatestaticIntegerremoveSubDuplicate(intpre,intcur,Interval[]intervals){
if(cur==intervals.length){
return0;
}
intnotRemove=Integer.MAX_VALUE;
if(pre==-1||intervals[pre].end<=intervals[cur].start){
/**
*假如是初次遍历，或许pre区间的结尾小于cur区间的起点（即区间不堆叠）,
*则pre=cur;cur=cur+1
*/
notRemove=removeSubDuplicate(cur,cur+1,intervals);
}
/**
*假如pre区间的结尾大于cur区间的起点，代表两区间堆叠，cur指向后一个区间，即cur=cur+1
*代表cur被移除，所以需求加1（代表这个区间被移除了）
*/
intremove=removeSubDuplicate(pre,cur+1,intervals)+1;
//取两者的较小值
returnMath.min(notRemove,remove);
}
publicstaticvoidmain(String[]args){
//初始化区间
Interval[]intervals={
newInterval(1,2),
newInterval(3,5),
newInterval(4,7),
newInterval(8,10),
newInterval(9,11)
};
intresult=removeDuplicateIntervas(intervals);
System.out.println("result="+result);
}
}

2、剖析在递归的进程中是否存在很多的重复子问题

怎样判别是否存在很多的重复子问题，在一文学会动态规划解题技巧咱们提出一种计划，画出递归树，不过这题假如画出递归树比较费事，其实关于组合问题咱们能够简略剖析一下，关于每个区间要么选，要么不选，咱们以 1 代表该区间被挑选，以 0 代表该区间不选，则简略考虑一下如下两个组合

11010
11001

仔细看，红框部分，便是重复子问题!

或许有人会说这样剖析也有点难，那我再教咱们一招，打印! 如图示

在递归函数中打印出来，然后剖析打印的规则

能够看到，的确存在着重复子问题，时刻杂乱度是多少呢，每个区间要么选，要么不选，共有两个状况，假如有 n 个区间的话，便是 2^n,所以咱们知道时刻杂乱度是 O(2^n)，指数级!显着无法承受

已然存在重复子问题，那咱们进入动态规划第三步

3、选用备忘录的方法来存子问题的解以防止很多的重复核算(剪枝)

在以上的剖析中根本咱们看到，其实便是 pre, cur 有或许存在很多重复，所以咱们保存 pre, cur 对应的中心成果，如下

//保存中心成果
privatestaticHashMap<String,Integer>map=newHashMap();
privatestaticIntegerremoveSubDuplicate(intpre,intcur,Interval[]intervals){
Stringkey=pre+","+cur;
if(map.get(key)!=null){
returnmap.get(key);
}
if(cur==intervals.length){
return0;
}
intnotRemove=Integer.MAX_VALUE;
if(pre==-1||intervals[pre].end<=intervals[cur].start){
notRemove=removeSubDuplicate(cur,cur+1,intervals);
}
intremove=removeSubDuplicate(pre,cur+1,intervals)+1;
intresult=Math.min(notRemove,remove);
map.put(key,result);
returnresult;
}

选用备忘录的方法缓存子问题的中心成果后，时刻杂乱度直线下降，到达 O(n^2)(因为 pre, cur 两个变量不断往后移，即两层循环，所以是 O(n^2)) 。

4、改用自底向上的方法来递推，即动态规划

咱们界说 dp[i] 为从 0 到第 i 个区间的最大不堆叠区间数,所以咱们得出了状况搬运方程

dp[i]=max{dp[j]}+1,其间0<=j<i而且需求满意一个条件interval[i].start>interval[j].end,即确保i,j指向的区间不堆叠。

则终究的 dp[区间总个数-1] 即为最大的接连不堆叠区间个数，那么区间总个数 - 最大的接连不堆叠区间个数不便是最小要移除的区间数了，有了 dp 方程，写起代码来就快了，如下

/**
*判别两区间是否堆叠,i区间的起点比j区间的大,假如j区间的结尾比i区间的起点大，则堆叠
*/
privatestaticbooleanisOverlapping(Intervali,Intervalj){
returnj.end>i.start;
}
/**
*动态规划求解
*/
privatestaticIntegerremoveSubDuplicateWithDP(Interval[]intervals){
//将区间按起始点由小到大进行排序
Arrays.sort(intervals,Comparator.comparingInt(a->a.start));
int[]dp=newint[intervals.length];
Arrays.fill(dp,0);
dp[0]=1;//将dp[0]置为1，因为就算一切的区间都堆叠，则接连不堆叠区间到少也为1
intresult=1;
for(inti=1;i<intervals.length;i++){
intmax=0;
for(intj=0;j<i;j++){
if(!isOverlapping(intervals[i],intervals[j])){
max=Math.max(dp[j],max);
}
}
dp[i]=max+1;
}
returnintervals.length-dp[intervals.length-1];
}

空间杂乱度是多少，因为只需一个 dp 一维数组，所以是 O(n)，时刻杂乱度呢，两重循环，所以是 O(n^2)。能够看到和选用递归+备忘录的时刻杂乱度相同，不过之前其实说了许屡次，递归简略导致栈溢出，所以主张仍是选用动态规划的方法来求解。

接下来要点来了，来看看怎样用贪心算法来求解。首要要把各个区间依照区间的结尾从小到大摆放，如下

咱们的思路与上文中的动态规划相同，先求出最大不堆叠子区间个数,再用「区间总数-最大不堆叠子区间个数」即为最小要移除的堆叠区间数。

用贪心算法求最大不重大子区间个数进程如下

挑选结尾最小的区间，设置为当时区间 cur 。
按区间结尾从小到大寻觅下一个与区间 cur 不堆叠的区间，然后将此区间设置为当时区间 cur(留意此刻最大不堆叠子区间个数要加1)，不断重复进程 2，直到遍历一切的区间。

动图如下,信任咱们看完动图会更简略了解

知道了解题思路，写代码就很简略了

/**
*贪心算法求解
*/
privatestaticIntegerremoveSubDuplicateWithGreedy(Interval[]intervals){
//将区间结尾由小到大进行排序
Arrays.sort(intervals,Comparator.comparingInt(a->a.end));
intcur=0;//设置第一个为当时区间
intcount=1;//最大不堆叠区间数,最小为1
for(inti=1;i<intervals.length;i++){
//不堆叠
if(intervals[cur].end<intervals[i].start){
cur=i;
count++;
}
}
//总区间个数减去最大不堆叠区间数即最小被移除堆叠区间
returnintervals.length-count;
}

时刻杂乱度是多少呢，只需一个循环，所以是 O(n), 比起动态规划的 O(n^2),的确快了一个数量级，简略剖析下为啥贪心算法这么快，由以上代码能够看到，它只关怀眼前的最优解(挑选下一个与当时区间不堆叠的区间再顺次遍历，选完之后再也无需关怀之前的区间了!)而动态规划呢，从它的 dp 方程(dp[i] = max{dp[j]} + 1)能够看出，关于每个 i ,都要自底向上遍历一遍 0 到 i 的解以求出最大值，也便是说关于动态规划的子问题而言，因为它寻求的是大局最优解，所以它有一个回溯(即自底向上求出一切子问题解的最优解)的进程，回溯的进程中就有一些重复的子问题核算，而贪心算法因为寻求的是眼前的最优解，所以不会有这种回溯的求解，也就省去了很多的操作，所以假如能够用贪心算法求解，时刻杂乱度无疑是能上升一个量级的。

贪心算法适用场景

简略总结一下贪心算法，它指的是每一步只选最优的，而且希望每一步挑选的最优解能达到大局的最优解，说实话这太难了，因为一般一个问题的挑选都会影响下一个问题的挑选，除非子问题之间彻底独立，没有相关，比方咱们在文中最初说的凑零钱的比方，假如一个国家的钞票比较奇葩，只需 1，5，11 这三种面值的钞票，怎样用最少的钞票凑出 15 呢，假如用贪心第一次选 11，那之后只能选 4 张 1 了，即 15 = 1 x 11 + 4 x1。其实最优解应该是 3 张 5 元的钞票，为啥这种情况下用贪心不适用呢，因为第一次选了 11，影响了后边钞票的挑选，也便是说子问题之间并不是独立的，而是互相制约，互有影响的，所以咱们选贪心的时分必定要留意它的适用场景。

再看三角形最短途径和是否能用贪心算法求解

回过头来看最初的问题，三角形最短途径和能否用贪心算法求解呢

先回忆一下这个标题: