贪婪算法又称什么

贪婪算法又称贪心算法，是一种简单、高效、常用的算法思想。在求解最优解、近似最优解或启发式搜索等问题时，贪婪算法发挥重要作用。本文将从定义、优缺点、应用及案例等多个角度来分析贪婪算法。

一、定义

贪婪算法是一种以贪心思想为基础的算法，即每次寻找局部最优解，并通过不断贪心选择，最终得到全局最优解的策略。贪婪算法的特点是每次只考虑局部最优解，不考虑全局最优解，因此算法实现简单高效。

二、优缺点

贪婪算法的优点在于算法实现简单、高效；在面对NP难问题或求解正解时，近似最优解的效果较好。同时，贪婪算法的执行速度比较快，能够较好地应用在较大数据量上。

缺点在于贪婪算法只考虑局部最优解，因此存在可能出现结果不是全局最优的情况。同时，贪婪算法的结果受到初值、排序等因素的影响，对于不同的问题需要采用不同的贪心策略，则需要具备一定的经验或调试，因此在解决一些较为复杂的问题时，效果较差。

三、应用

贪婪算法被广泛应用于多个领域。以下将列举几个常见的问题及其贪婪算法的应用：

1.背包问题：假设有n个物品，每个物品有一定的重量和价值，在限定的重量范围内如何选取物品，使得物品总价值最大。贪婪算法常用的策略有价值密度和重量限制。

2.最小生成树：给定一个带权连通图，边上带着权重值，如何在保证边的连通性的同时使得各条边上权重值之和最小。贪婪策略常使用Prim算法和Kruskal算法。

3.任务调度：如何将n个处理器分配给m个任务，由于各个处理器的性能不同，如何使得任务结束时间最早。贪婪算法可以采用“最短处理时间”或“处理器利用率”等贪婪策略。

四、案例

1.贪心策略求解背包问题：

假设有10个物品，每个物品的重量为wi，价值为vi，背包的载重量为W。采用价值密度策略，将物品按照价值密度从大到小排列，逐一选择放入背包中，直至背包载满为止。具体实现方式在代码实现中进行了体现。

```

def knapsack(max_weight, items):

items.sort(key=lambda i: i[0]/i[1], reverse=True)

total, result = 0, []

for i in items:

if total+i[1] > max_weight:

break

total += i[1]

result.append(i)

value = sum([x[0] for x in result])

return result, value

```

2.贪心算法求解最小生成树

假设有如下图所示的一个带权连通图，可以采用贪婪算法的Prim策略求解最小生成树。具体实现方法就是：假设初始值为任意一个顶点，从该顶点开始逐个添加其他的顶点，优先选择权值最小的边，直至遍历完所有节点为止。