贪心算法（Greedy Algorithm）_csdn贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心算法在有最优子结构的问题中尤为有效，即局部最优解能决定全局最优解的问题。
贪心算法不保证会得到最优解，但在某些问题中，贪心算法的解足够接近最优解或者确实是最优解。贪心算法可以快速找到问题的可行解，因此对于要求不是很严格的问题，贪心算法可以作为一种简单而有效的解决方案。

一、典型应用

1. 钱币找零问题：在钱币找零问题中，我们希望用最少数量的钱币凑成特定的金额。
2. 霍夫曼编码（Huffman Coding）：在数据压缩中，用于构建最小长度的前缀编码。
3. 图的最小生成树：如普里姆算法（Prim’s algorithm）和克鲁斯卡尔算法（Kruskal’s algorithm）用于在图的顶点之间找到最短的边集合，使得所有顶点都被连接起来。
4. 单源最短路径问题：如迪杰斯特拉算法（Dijkstra’s algorithm）和贝尔曼-福特算法（Bellman-Ford algorithm）用于找到从单个源点到所有其他顶点的最短路径。
5. 分数背包问题：在这个问题中，我们希望最大化价值的总和，同时不超过一个给定的重量限制。

二、算法特点

简单直观：通常直接且易于实现。

• 效率：在很多情况下，贪心算法的运行时间较短。
• 无记忆：每次选择都是独立的，不依赖于之前的状态。
• 不总是得到最优解：在某些问题中，贪心选择可能导致非最优的全局解。

三、算法讲解

贪心算法是一种通过在每一步选择当前可用的最佳选项来解决问题的方法。它不担心当前最佳结果是否会带来整体最优结果。
算法从不逆转早期的决定，即使选择是错误的。它采用自顶向下的方法。
我们可以通过以下属性来确定是否可以使用该算法解决问题：

1. 贪心选择属性
   如果问题的最优解可以通过在每一步选择最佳选择而找到，而一旦选择就不考虑之前的步骤，那么可以使用贪心方法解决这个问题。这个属性被称为贪心选择属性。
2. 最优子结构
   如果问题的整体最优解对应于其子问题的最优解，那么可以使用贪心方法解决问题。这个属性被称为最优子结构。
   例如，假设我们想在下面的图中找到从根到叶的最长路径。让我们在这里使用贪心算法。
   
   在此树上应用贪心方法以找到最长的路径
   贪心方法
3. 让我们从根节点20开始。右子节点的权重为3，左子节点的权重为2。
4. 我们的问题是找到最长的路径。而且，目前的最佳解决方案是3。所以，贪心算法会选择3。
5. 最后，3的唯一子节点的权重为1。这给出了我们的最终结果20 + 3 + 1 = 24。
   然而，这不是最优解。还有另一条路路径携带更多权重（20 + 2 + 10 = 32），如下面的图像所示。
   
   最长路径
   因此，贪心算法并不总是给出最优/可行的解决方案。

贪心算法

1. 首先，解决方案集（包含答案）是空的。
2. 在每一步，一个项目被添加到解决方案集中，直到达到解决方案。
3. 如果解决方案集是可行的，当前的项目将被保留。
4. 否则，该项目将被拒绝，并且永远不会再次被考虑。
   现在让我们使用这个算法来解决一个问题。

例子 - 贪心方法

金额：$18
可用硬币为
  $5硬币
  $2硬币
  $1硬币
您可以使用每种硬币的数量没有限制。
1
2
3
4
5
6

解决方案：

1. 创建一个空的solution-set = { }。可用硬币为{5, 2, 1}。
2. 我们应该找到sum = 18。让我们从sum = 0开始。
3. 始终选择最大价值的硬币（即5），直到sum > 18。（当我们在每一步选择最大值时，我们希望能够更快地到达目的地。这个概念被称为贪心选择属性。）
4. 在第一次迭代中，solution-set = {5}，sum = 5。
5. 在第二次迭代中，solution-set = {5, 5}，sum = 10。
6. 在第三次迭代中，solution-set = {5, 5, 5}，sum = 15。
7. 在第四次迭代中，solution-set = {5, 5, 5, 2}，sum = 17。（我们不能在这里选择5，因为如果我们这样做，sum = 20，这比18大。所以，我们选择第二大的项目，即2。）
8. 类似地，在第五次迭代中，选择1。现在sum = 18，solution-set = {5, 5, 5, 2, 1}。

四、Python示例

包括钱币找零问题、霍夫曼编码树的构建、以及图的最小生成树（使用普里姆算法）。

1. 钱币找零问题

假设我们有不同面额的钱币，并且需要找零金额为amount，我们希望使用尽可能少的钱币。

def coinChange(coins, amount):
    # 动态规划的解法，而非贪心算法
    # 这里仅作为示例，因为贪心算法在这个问题中不总是有效
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# 示例
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))  # 输出：3，因为可以选 5 + 5 + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 霍夫曼编码

霍夫曼编码是一种使用变长编码表对数据进行编码的方法，它是基于符号出现频率的贪心算法。

import heapq

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def calc_freq(data):
    freq = {}
    for char in data:
        if char not in freq:
            freq[char] = 0
        freq[char] += 1
    return freq

def build_huffman_tree(data):
    freq = calc_freq(data)
    priority_queue = [Node(char, freq[char]) for char in freq]
    heapq.heapify(priority_queue)
    
    while len(priority_queue) > 1:
        left = heapq.heappop(priority_queue)
        right = heapq.heappop(priority_queue)
        
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        heapq.heappush(priority_queue, merged)
    
    return priority_queue[0]

# 示例
data = "this is an example for huffman encoding"
tree = build_huffman_tree(data)
print(tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

3. 最小生成树 - 普里姆算法

普里姆算法是一种用于在加权图中找到最小生成树的贪心算法。

def prim(graph, start):
    visited = set()
    visited.add(start)
    edges = []
    
    while len(visited) < len(graph):
        mim = float('inf')
        mim_edge = None
        for edge in graph:
            if edge[0] in visited and edge[1] not in visited:
                if edge[2] < mim:
                    mim = edge[2]
                    mim_edge = edge
            elif edge[1] in visited and edge[0] not in visited:
                if edge[2] < mim:
                    mim = edge[2]
                    mim_edge = edge
        if mim_edge is None:
            break
        visited.add(mim_edge[1])
        edges.append(mim_edge)
    
    return edges

# 示例
graph = [
    ('A', 'B', 1),
    ('A', 'C', 3),
    ('B', 'C', 3),
    ('B', 'D', 1),
    ('C', 'D', 4),
    ('C', 'E', 2),
    ('D', 'E', 3)
]

print(prim(graph, 'A'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

请注意，贪心算法并不总是能得到最优解，特别是在钱币找零问题中，贪心算法可能无法找到最少数量的钱币组合。在实际应用中，需要根据问题的具体性质和要求来选择是否使用贪心算法。
在实际应用中，是否使用贪心算法取决于问题的性质以及对解的质量要求。对于某些问题，贪心算法可以提供有效的近似解，而对于其他问题，则可能需要更复杂的算法来找到最优解。