这篇文章我们共同学习贪婪算法,贪婪策略是一种非常简单的问题解决策略。
教室调度问题
假设目前有如下的课程表,你希望将尽可能多的课程安排在某间教室上。
如果我们安排了美术课之后,英语课就不能安排到这间教室了
你希望在这间教室上尽可能多的课,那么如何选出尽可能多且时间不冲突的课程呢?
排课信息
具体做法在这里先给你:
1、 先选出结束最早的课,即就是这间教室上的第一堂课
2、 由于第一节课是10点结束的,因此我们要选从第一节课结束的时间才开始上的课,同样,我们选出结束最早的课,这将是这间教室上的第二堂课
重复第二步,这样我们就能找出这间教室既不冲突也可以安排尽可能多的课。
于是,我们就得出了这间教室可以上三堂课,如图所示:
排课结果
你看到这里一定会说这有啥难的!但这就是贪婪算法的优势——简单易行,因为每一步都是局部最优解,那么最终得到的就是全局最优解。当然贪婪算法有其局限性,正是其简单易实现的优点才没有被弃用。
我们再看一个问题——集合覆盖问题
假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台,让所有的地区都可以接收到信号
每个广播台播出都需要支付费用,因此要力图在尽可能少的广播台播出并且覆盖的州要尽可能多。
每个广播台都覆盖特定的区域,不同广播台的覆盖区域可能重叠
地区
是不是想想都挺难的,但是贪婪算法可以解决这一问题,具体做法:
1、 选出覆盖了最多的地区的广播台,即使下次选择的广播台已经覆盖了上次已经覆盖过的地区,也没有关系,只要它是覆盖最多的就可以。
2、 重复第一步,直到覆盖了所有的地区
这是一种近似算法。在获得精确解需要的时间太长时,可使用近似算法。判断近似算法优劣的标准如下:
i. 速度有多快
ii. 得到的近似解与最优解的接近程度
贪婪算法不仅简单,而且通常运行速度很快。
代码实现
package ShangGuiGu.Algorithm.Greedy;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;/**
* 贪心算法
*/public class GreedyAlgorithm //清空当前广播台覆盖的地区,为下一次for循环tempSet.clear();
}//选取到一个包含未覆盖地区最多的广播台if (maxKey!=null){
broadcastsList.add(maxKey);//选取的广播已经覆盖了一部分未覆盖的地区,剩下的即为未覆盖的地区,用于下一次forEach循环cities.removeAll(broadcasts.get(maxKey));
}//下一次wihle循环maxKey=nullmaxKey=null;
}//打印选取的广播台System.out.println("选取的广播台:"+broadcastsList);
}/**
* 得到所有广播所覆盖的地区集合
* @param broadcasts
* @return
*/public static HashSet getCities(HashMap broadcasts){
HashSet cities = new HashSet();for (HashSet curCities:broadcasts.values()){
cities.addAll(curCities);
}return cities;
}
}
领取专属 10元无门槛券
私享最新 技术干货