图解贪婪算法(转)

古城微笑少年丶 2022-02-02 00:25 266阅读 0赞

### 文章目录 ###

*  算法简介
 *  基本思路
 *  案例
 *   *  案例一
     *  案例二
     *  案例三
     *  NP完全问题
 *  小结
 *  java实现

原博链接： [https://blog.csdn.net/a8082649/article/details/82079779][https_blog.csdn.net_a8082649_article_details_82079779]

# 算法简介 #

**贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。**

**贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。**

*  贪婪算法并**没有固定的算法解决框架**，算法的关键是贪婪策略的选择，根据不同的问题选择不同的策略。
 *  必须注意的是策略的选择必须具备无后效性，即某个状态的选择不会影响到之前的状态，只与当前状态有关，所以对采用的贪婪的策略一定要仔细分析其是否满足无后效性。

比如最短路径问题(广度优先、狄克斯特拉)都属于贪婪算法，只是在其问题策略的选择上，刚好可以得到最优解。

# 基本思路 #

其基本的解题思路为：

1.  建立数学模型来描述问题
2.  把求解的问题分成若干个子问题
3.  对每一子问题求解，得到子问题的局部最优解
4.  把子问题对应的局部最优解合成原来整个问题的一个近似最优解

# 案例 #

这边的案例来自"算法图解"一书

## 案例一 ##

**区间调度问题:**

假设有如下课程，希望尽可能多的将课程安排在一间教室里：

这个问题看似要思考很多，实际上算法很简单:

1.选择结束最早的课，便是要在这教室上课的第一节课  
2.接下来，选择第一堂课结束后才开始的课，并且结束最早的课，这将是第二节在教室上的课。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]  
重复这样做就能找出答案，这边的选择策略便是结束最早且和上一节课不冲突的课进行排序，因为每次都选择结束最早的，所以留给后面的时间也就越多，自然就能排下越多的课了。

每一节课的选择都是策略内的局部最优解(留给后面的时间最多)，所以最终的结果也是近似最优解(这个案例上就是最优解)。 (该案例的代码实现，就是一个简单的时间遍历比较过程)

这里有一个前提是每种课程的上课时长一样

## 案例二 ##

背包问题：有一个背包，容量为35磅 ， 现有如下物品

<table> 
 <thead> 
  <tr> 
   <th>物品</th> 
   <th>重量</th> 
   <th>价格</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>吉他</td> 
   <td>15</td> 
   <td>1500</td> 
  </tr> 
  <tr> 
   <td>音响</td> 
   <td>30</td> 
   <td>3000</td> 
  </tr> 
  <tr> 
   <td>笔记本电脑</td> 
   <td>20</td> 
   <td>2000</td> 
  </tr> 
  <tr> 
   <td>显示器</td> 
   <td>29</td> 
   <td>2999</td> 
  </tr> 
  <tr> 
   <td>笔</td> 
   <td>1</td> 
   <td>200</td> 
  </tr> 
 </tbody> 
</table>

要求达到的目标为装入的背包的总价值最大，并且重量不超出。

方便计算所以只有5个物品，实际情况可能是成千上万。

同上使用贪婪算法，因为要总价值最大，所以每次每次都装入最贵的,然后在装入下一个最贵的，选择结果如下：

选择: 音响 + 笔，总价值 3000 + 200 = 3200

并不是最优解: 吉他 + 笔记本电脑, 总价值 1500 + 2000 = 3500

当然选择策略有时候并不是很固定，可能是如下：

> (1)每次挑选价值最大的,并且最终重量不超出：  
> 选择: 音响 + 笔，总价值 3000 + 200 = 3200

> (2)每次挑选重量最大的,并且最终重量不超出(可能如果要求装入最大的重量才会优先考虑)：  
> 选择: 音响 + 笔，总价值 3000 + 200 = 3200

> (3)每次挑选单位价值最大的(价格/重量),并且最终重量不超出：  
> 选择: 笔+ 显示器，总价值 200 + 2999 = 3199

如上**最终的结果并不是最优解，在这个案例中贪婪算法并无法得出最优解**，只能得到近似最优解,也算是该算法的局限性之一。该类问题中需要得到最优解的话可以采取动态规划算法

## 案例三 ##

集合覆盖问题:

假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]  
如何找出覆盖所有地区的广播台的集合呢，听起来容易，实现起来很复杂，使用穷举法实现：

*  (1) 列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2ⁿ个
 *  (2) 在这些集合中，选出覆盖全部地区的最小的集合，假设n不在，但是当n非常大的时候，假设每秒可以计算10个子集

<table> 
 <thead> 
  <tr> 
   <th>广播台数量n</th> 
   <th>子集总数2ⁿ</th> 
   <th>需要的时间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>32</td> 
   <td>3.2秒</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>1024</td> 
   <td>102.4秒</td> 
  </tr> 
  <tr> 
   <td>32</td> 
   <td>4294967296</td> 
   <td>13.6年</td> 
  </tr> 
  <tr> 
   <td>100</td> 
   <td>1.26*100³º</td> 
   <td>4x10²³年</td> 
  </tr> 
 </tbody> 
</table>

目前并没有算法可以快速计算得到准备的值， 而使用贪婪算法，则可以得到非常接近的解，并且效率高:

选择策略上，因为需要覆盖全部地区的最小集合:

*  (1) 选出一个广播台，即它覆盖了最多未覆盖的地区即便包含一些已覆盖的地区也没关系
 *  (2) 重复第一步直到覆盖了全部的地区

这是一种近似算法（approximation algorithm，贪婪算法的一种）。在获取到精确的最优解需要的时间太长时，便可以使用近似算法，判断近似算法的优劣标准如下:

*  速度有多快
 *  得到的近似解与最优解的接近程度

在本例中贪婪算法是个不错的选择，不仅运行速度快，本例运行时间O(n²),最坏的情况，假设n个广播台，每个广播台就覆盖1个地区,n个地区，总计需要查询n\*n=O(n²),实现可查看后面的java代码实现

<table> 
 <thead> 
  <tr> 
   <th>广播台数量n</th> 
   <th>子集总数2ⁿ</th> 
   <th>穷举需要时间</th> 
   <th>贪婪算法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>32</td> 
   <td>3.2秒</td> 
   <td>2.5秒</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>32</td> 
   <td>102.4秒</td> 
   <td>10秒</td> 
  </tr> 
  <tr> 
   <td>32</td> 
   <td>32</td> 
   <td>13.6年</td> 
   <td>102.4秒</td> 
  </tr> 
  <tr> 
   <td>100</td> 
   <td>32</td> 
   <td>4x10²³年</td> 
   <td>1000秒</td> 
  </tr> 
 </tbody> 
</table>

此时算法选出的是K1, K2, K3, K5，符合覆盖了全部的地区，可能不是预期中的K2, K3,K4,K5(也许预期中的更便宜，更便于实施等等)

## NP完全问题 ##

案例四:

旅行商问题

假设有旅行商需要从下面三个城市的某一个城市出发，如何规划路线获取行程的最短路径。  
![在这里插入图片描述][20190510143640346.png]  
存在3！(阶乘)=6种可能情况:

A->B->C
    A->C->B
    B->A->C
    B->C->A
    C->A->B
    C->B->A

这边和之前求最短路径的算法(广度搜索、狄克斯特拉、贝尔曼-福特)，最大的差别是没有固定源点(起点),，每一个节点都可能是源点，并且需要经过每一个节点，所以若穷举法则不得不找出每一种可能并进行比较。

当城市数量为n,则可能性为n!，假设每秒处理判断一个路线

<table> 
 <thead> 
  <tr> 
   <th>数量n</th> 
   <th>总数n!</th> 
   <th>穷举需要时间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>120</td> 
   <td>120秒</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>3628800</td> 
   <td>42天</td> 
  </tr> 
 </tbody> 
</table>

而使用贪婪算法，随机选择从一个城市出发，比如A，每次选择从最近的还没去过的城市出发,则可以得到近似最优解。

第一次比较n-1个城市 第二次比较n-2个城市 … 第n-1次比较1个城市 第n次不存在需要比较的了个

0+1+2+3+…+(n-1) ≈ O(n²/2)

<table> 
 <thead> 
  <tr> 
   <th>数量n</th> 
   <th>总数n!</th> 
   <th>穷举需要时间</th> 
   <th>贪婪需要时间</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>5</td> 
   <td>120</td> 
   <td>120秒</td> 
   <td>12.5秒</td> 
  </tr> 
  <tr> 
   <td>10</td> 
   <td>3628800</td> 
   <td>42天</td> 
   <td>50秒</td> 
  </tr> 
 </tbody> 
</table>

类似上述集合覆盖问题、旅行商问题，都属于NP完全问题，在数学领域上并没有快速得到最优解的方案，贪婪算法是最适合处理这类问题的了。

**如何判断是NP完全问题的:**

1.  元素较少时，一般运行速度很快，但随着元素数量增多，速度会变得非常慢
2.  涉及到需要计算比较"所有的组合"情况的通常是NP完全问题
3.  无法分割成小问题，必须考虑各种可能的情况。这可能是NP完全问题
4.  如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题
5.  如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题
6.  如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题

# 小结 #

1.  贪婪算法可以寻找局部最优解，并尝试与这种方式获得全局最优解
2.  得到的可能是近似最优解，但也可能便是最优解(区间调度问题，最短路径问题(广度优先、狄克斯特拉))
3.  对于完全NP问题，目前并没有快速得到最优解的解决方案
4.  面临NP完全问题，最佳的做法就是使用近似算法
5.  贪婪算法(近似算法)在大部分情况下易于实现，并且效率不错

# java实现 #

贪婪算法需要根据具体问题，选择对应的策略来实现，所以这边只取集合覆盖问题做个示例：

/** * 贪婪算法 - 集合覆盖问题 * @author Administrator * */
    public class Greedy { 
    	
    	public static void main(String[] args){ 
    		//初始化广播台信息
    		HashMap<String,HashSet<String>> broadcasts = new HashMap<String,HashSet<String>>();
    		broadcasts.put("K1", new HashSet(Arrays.asList(new String[] { "ID","NV","UT"})));
    		broadcasts.put("K2", new HashSet(Arrays.asList(new String[] { "WA","ID","MT"})));
    		broadcasts.put("K3", new HashSet(Arrays.asList(new String[] { "OR","NV","CA"})));
    		broadcasts.put("K4", new HashSet(Arrays.asList(new String[] { "NV","UT"})));
    		broadcasts.put("K5", new HashSet(Arrays.asList(new String[] { "CA","AZ"})));
     
    		//需要覆盖的全部地区
    		HashSet<String> allAreas = new HashSet(Arrays.asList(new String[] { "ID","NV","UT","WA","MT","OR","CA","AZ"}));
    		//所选择的广播台列表
    		List<String> selects = new ArrayList<String>();
    		
    		HashSet<String> tempSet = new HashSet<String>();
    		String maxKey = null;
    		while(allAreas.size()!=0) { 
    			maxKey = null;
    			for(String key : broadcasts.keySet()) { 
    				tempSet.clear();
    				HashSet<String> areas = broadcasts.get(key);
    				tempSet.addAll(areas);
    				//求出2个集合的交集，此时tempSet会被赋值为交集的内容，所以使用临时变量
    				tempSet.retainAll(allAreas);
    				//如果该集合包含的地区数量比原本的集合多
    				if (tempSet.size()>0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) { 
    					maxKey = key;
    				}
    			}
    			
    			if (maxKey != null) { 
    				selects.add(maxKey);
    				allAreas.removeAll(broadcasts.get(maxKey));
    			}
    		}
    		System.out.print("selects:" + selects);
     
    	}
    }

执行完main方法打印信息如下:
    selects:[K1, K2, K3, K5]

[https_blog.csdn.net_a8082649_article_details_82079779]: https://blog.csdn.net/a8082649/article/details/82079779
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220202/43f9475987e04f669619cfaaa5d2581e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]: /images/20220202/88164c68abf242aea23c68086f76e5bc.png
[20190510143640346.png]: /images/20220202/328ea49fcb324c77be11b0af19a51bca.png