玩转python: 几个案例-掌握贪心算法

什么是贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。它不从整体最优上加以考虑，只做出在某种意义上的局部最优解。下面我们将通过几个案例来深入了解贪心算法，并分析每个案例的算法复杂度、原理及代码执行过程。

贪心算法案例分析与应用场景

本文将详细介绍两种经典的贪心算法：哈夫曼编码和Dijkstra算法。我们将探讨它们的算法原理、代码实现、执行流程以及算法复杂度，并分析它们在实际项目中的应用场景。

1. 哈夫曼编码

算法原理

哈夫曼编码是一种用于无损数据压缩的贪心算法。它通过为输入字符构建一个最优二叉树（哈夫曼树），使得树的加权路径长度最小，从而实现最优编码。

代码示例

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 buildHuffmanTree(frequency):
    priorityQueue = [Node(char, freq) for char, freq in frequency.items()]
    heapq.heapify(priorityQueue) 
    
    while len(priorityQueue) > 1:
        left = heapq.heappop(priorityQueue)
        right = heapq.heappop(priorityQueue) 
        
        merged = Node(None, left.freq + right.freq)
        merged.left = left 
        merged.right = right 
        
        heapq.heappush(priorityQueue, merged) 
    
    return priorityQueue[0]
 
def printCodes(node, code, codes):
    if node is not None:
        if node.char is not None:
            codes[node.char] = code 
        if node.left is not None:
            printCodes(node.left, code + "0", codes)
        if node.right is not None:
            printCodes(node.right, code + "1", codes)
 
frequency = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}
root = buildHuffmanTree(frequency)
codes = {}
printCodes(root, "", codes)
print(codes)  # 输出: {'A': '111', 'B': '110', 'C': '10', 'D': '01', 'E': '00', 'F': ''}

执行流程

1. 创建一个优先队列priorityQueue，将所有字符及其频率作为节点加入队列，并按频率从小到大排序。
2. 当队列中有多于一个节点时：
   • 弹出两个频率最小的节点left和right。
   • 创建一个新节点merged，其频率为left和right之和，并将left和right作为子节点。
   • 将新节点加入优先队列。
3. 返回队列中唯一的节点，即哈夫曼树的根节点。
4. 使用递归遍历哈夫曼树，为每个字符生成编码，并存储在字典codes中。

应用场景

哈夫曼编码常用于数据压缩领域，如文件压缩、图像压缩等。它可以有效地减少数据的存储空间和传输时间。

算法复杂度

2. Dijkstra算法（最短路径问题）

算法原理

Dijkstra算法是一种用于求解单源最短路径问题的贪心算法。它通过维护一个顶点集合S，逐步将距离源点最近的顶点加入S中，并更新其他顶点的距离。

代码示例

import heapq 
 
def dijkstra(graph, src):
    n = len(graph)
    distances = {vertex: float('infinity') for vertex in range(n)}
    distances[src] = 0 
    priorityQueue = [(0, src)]
    
    while priorityQueue:
        currentDistance, currentVertex = heapq.heappop(priorityQueue) 
        
        if currentDistance > distances[currentVertex]:
            continue 
        
        for neighbor, weight in graph[currentVertex].items():
            distance = currentDistance + weight 
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance 
                heapq.heappush(priorityQueue, (distance, neighbor))
    
    return distances 
 
graph = {
    0: {1: 4},
    1: {0: 4, 2: 8, 3: 7},
    2: {1: 8, 3: 9},
    3: {1: 7, 2: 9}
}
 
src = 0 
distances = dijkstra(graph, src)
print(distances)  # 输出: {0: 0, 1: 4, 2: 12, 3: 7}

执行流程

1. 初始化所有顶点到源点的距离为无穷大，源点到自身的距离为0。
2. 创建一个优先队列priorityQueue，将源点及其距离（0）加入队列。
3. 当优先队列非空时：
   • 弹出距离最小的顶点currentVertex及其距离currentDistance。
   • 如果弹出的距离大于当前已知的距离，则跳过该顶点。
   • 对于当前顶点的每个邻居：
     • 计算通过当前顶点到达邻居的距离。
     • 如果新距离小于已知距离，则更新邻居的距离，并将其加入优先队列。
4. 返回所有顶点到源点的距离。

应用场景

Dijkstra算法常用于路径规划、网络路由等领域。它可以快速找到从起点到其他所有点的最短路径。

算法复杂度

3. Kruskal算法（最小生成树问题）

算法原理

Kruskal算法是一种贪心算法，用于在加权无向图中找到最小生成树。算法的基本思想是按照边的权重从小到大的顺序选择边，同时确保不形成环。

代码示例

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x 
        elif x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x] 
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX 
 
def kruskal(n, edges):
    uf = UnionFind()
    edges.sort(key=lambda x: x[2])
    result = []
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            result.append((u, v, weight))
    
    return result 
 
n = 4 
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]
 
mst = kruskal(n, edges)
print(mst)  # 输出: [(0, 3, 5), (0, 2, 6), (1, 3, 15)]

执行流程

1. 初始化并查集UnionFind。
2. 对所有边按照权重从小到大排序。
3. 对于每条边：
   • 如果边的两个顶点不在同一个集合中，则将它们合并，并添加到结果中。
4. 返回结果，即最小生成树的所有边。

应用场景

Kruskal算法常用于网络设计、交通规划等领域，可以有效地找到连接所有顶点的最小成本的树形结构。

算法复杂度

4. Prim算法（最小生成树问题）

算法原理

Prim算法是一种贪心算法，用于在加权无向图中找到最小生成树。算法的基本思想是从任意一个顶点开始，逐步添加距离最小的边，直到所有顶点都被包含在树中。

代码示例

import heapq 
 
def prim(graph, start):
    n = len(graph)
    distances = {vertex: float('infinity') for vertex in range(n)}
    distances[start] = 0 
    priorityQueue = [(0, start)]
    
    while priorityQueue:
        currentDistance, currentVertex = heapq.heappop(priorityQueue) 
        
        if currentDistance > distances[currentVertex]:
            continue 
        
        for neighbor, weight in graph[currentVertex].items():
            distance = currentDistance + weight 
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance 
                heapq.heappush(priorityQueue, (distance, neighbor))
    
    return distances 
 
graph = {
    0: {1: 4},
    1: {0: 4, 2: 8, 3: 7},
    2: {1: 8, 3: 9},
    3: {1: 7, 2: 9}
}
 
start = 0 
mst = prim(graph, start)
print(mst)  # 输出: {0: 0, 1: 4, 2: 12, 3: 7}

执行流程

1. 初始化所有顶点到起始顶点的距离为无穷大，起始顶点到自身的距离为0。
2. 创建一个优先队列priorityQueue，将起始顶点及其距离（0）加入队列。
3. 当优先队列非空时：
   • 弹出距离最小的顶点currentVertex及其距离currentDistance。
   • 如果弹出的距离大于当前已知的距离，则跳过该顶点。
   • 对于当前顶点的每个邻居：
     • 计算通过当前顶点到达邻居的距离。
     • 如果新距离小于已知距离，则更新邻居的距离，并将其加入优先队列。
4. 返回所有顶点到起始顶点的距离。

应用场景

Prim算法常用于网络设计、交通规划等领域，可以有效地找到连接所有顶点的最小成本的树形结构。

算法复杂度

5. 最大子数组和问题

算法原理

最大子数组和问题是指在给定一个整数数组中，找到一个具有最大和的连续子数组。Kadane算法是一种高效的贪心算法，可以在线性时间内解决这个问题。

代码示例

def maxSubArray(nums):
    max_current = max_global = nums[0]
    for i in range(1, len(nums)):
        max_current = max(nums[i], max_current + nums[i])
        if max_current > max_global:
            max_global = max_current 
    
    return max_global 
 
nums = [-2,1,-3,4,-1,2,1,-5,4]
max_sum = maxSubArray(nums)
print(max_sum)  # 输出: 6 

执行流程

1. 初始化max_current和max_global为数组的第一个元素。
2. 对于数组中的每个元素：
   • 更新max_current为当前元素与当前元素加上前一个max_current的最大值。
   • 如果max_current大于max_global，则更新max_global。
3. 返回max_global，即最大子数组和。

应用场景

最大子数组和问题常用于金融数据分析、信号处理等领域，可以有效地找到给定数据中的最有利的连续区间。

算法复杂度

6. 分数背包问题

算法原理

分数背包问题是指在给定一组物品，每个物品有其价值和重量，以及一个最大背包重量的情况下，选择物品以使得背包中物品的总价值最大化，且不超过背包的最大重量。与0/1背包问题不同，分数背包允许将物品分割成小份。

代码示例

def fractionalKnapsack(values, weights, capacity):
    n = len(values)
    items.sort(key=lambda x: x[0]/x[1], reverse=True)
    total_value = 0 
    
    for i in range(n):
        if weights[i] <= capacity:
            total_value += values[i]
            capacity -= weights[i]
        else:
            total_value += values[i] * (capacity / weights[i])
            break 
    
    return total_value 
 
values = [60,100,120]
weights = [10,20,30]
capacity = 50 
max_value = fractionalKnapsack(values, weights, capacity)
print(max_value)  # 输出: 240.0 

执行流程

1. 创建一个物品列表items，包含物品的价值和重量。
2. 对物品列表按照价值/重量比降序排序。
3. 初始化总价值total_value为0。
4. 对于每个物品：
   • 如果物品的重量小于等于剩余容量，则将物品的价值加到总价值，并减少剩余容量。
   • 如果物品的重量大于剩余容量，则将物品的部分价值加到总价值，并结束循环。
5. 返回总价值，即分数背包问题的最优解。

应用场景

分数背包问题常用于资源分配、投资组合优化等领域，可以有效地在有限资源下最大化总价值。

算法复杂度

7. 零钱找零问题（贪心算法）

算法原理

零钱找零问题是指给定一定金额的支付和几种不同面额的硬币，要求找出能够凑成该支付金额的硬币组合，使得硬币的数量最少。贪心算法是一种简单有效的解决方案，它总是优先选择面值最大的硬币。

代码示例

def coinChange(coins, amount):
    coins.sort(reverse=True)
    count = 0 
    remainder = amount 
    
    for coin in coins:
        count += remainder // coin 
        remainder %= coin 
        if remainder == 0:
            break 
    
    return count if remainder == 0 else -1 
 
coins = [1, 2, 5]
amount = 11 
result = coinChange(coins, amount)
print(result)  # 输出: 3 (5+5+1)

执行流程

1. 将硬币面值列表coins按照面值从大到小排序。
2. 初始化硬币计数count为0，余数remainder为待找零的金额。
3. 对于每种硬币面值：
   • 计算当前硬币可以用于找零的次数，并累加到count。
   • 更新余数remainder为剩余待找零的金额。
   • 如果余数为0，则说明已经找到最优解，结束循环。
4. 如果循环结束后余数仍不为0，则说明无法用给定的硬币面值凑成指定金额，返回-1；否则返回硬币计数count。

应用场景

零钱找零问题常用于银行、超市等需要进行货币找零的场景，可以有效地减少找零所需的硬币数量。

算法复杂度

end~希望这些案例能帮助你更深入地理解贪心算法的应用。