贪婪算法的分析与实现

这篇文章我们共同学习贪婪算法，贪婪策略是一种非常简单的问题解决策略。

教室调度问题

假设目前有如下的课程表，你希望将尽可能多的课程安排在某间教室上。

如果我们安排了美术课之后，英语课就不能安排到这间教室了

你希望在这间教室上尽可能多的课，那么如何选出尽可能多且时间不冲突的课程呢？

排课信息

具体做法在这里先给你：

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;

}

}