1 策略内核

贪心策略(Greedy Strategy)，顾名思义，就是每一步都选择当前最优的选项来构建最终解。这意味着它不一定能找到全局最优解，但在某些问题中，这种贪心的选择是能够有效地得到全局最优解的。

1.1 基本思想

• 局部最优选择：每一步都选择当前看起来最优的选项，而不考虑该选择对后续的影响。这种选择是基于某种贪心准则的。贪心准则根据不同的目标制定。
• 放弃后效性：贪心策略不回溯，之前作出的选择不会再改变。
• 问题分解：贪心策略通常将问题分解为多个子问题，并通过解决这些子问题来构建最终的解决方案。

1.2 策略步骤

• 定义贪心选择性质：确认问题的贪心选择性质，即局部最优解是否能够导致全局最优解。
• 确定贪心准则：明确在每一步选择中应该优先考虑哪个选项。
• 实现：
  • 初始化一个解决方案的结构。
  • 迭代地选择当前最优的选项，直到达到目标。
• 验证结果：检查最终结果是否是全局最优解。

1.3 贪心算法举例说明

1.3.1 活动选择问题

假设有一系列活动，每个活动都有一个开始时间和结束时间。目标是选择尽可能多的互不重叠的活动。活动列表如下：

活动名称	开始时间	开始时间
A	0	6
B	1	2
C	2	3
D	4	5
E	5	7

（1）制定贪心选择准则
在满足时间不重叠的前提下总是选择结束时间最早的活动。该问题采用贪心策略是可以得到全局最优解的。

（2）预演贪心算法
首先选择结束时间最早的活动，然后按序遍历剩下的活动：

• 首先选择活动 B（1-2）。活动结束时间为2
• 遇到活动 C（2-3）。C的开始时间2不小于B的结束时间2。该活动结束时间为3，满足条件
• 遇到活动 D（4-5）。D的开始时间4不小于C的结束时间3。该活动结束时间为5，满足条件
• 遇到活动 A（0-6）。A的开始时间0小于D的结束时间5。不满足条件
• 遇到活动 E（5-7）。E的开始时间5不小于D的结束时间5。该活动结束时间为7
• 遍历结束

最后选择了B，C，D，E共4个活动。

（3）Python3实现

def activity_selection(activities):# 对活动按结束时间进行排序sort_activities = sorted(activities.items(), key=lambda x: x[1][1])n = len(activities)selected_activities = []# 选择第一个活动selected_activities.append(sort_activities[0][0])# 该活动的结束时间last_end_time = sort_activities[0][1][1]for i in range(1, n):# 如果当前活动的开始时间大于或等于上一个选择活动的结束时间if sort_activities[i][1][0] >= last_end_time:selected_activities.append(sort_activities[i][0])# 更新活动的结束时间last_end_time = sort_activities[i][1][0]return selected_activities# 活动名称:（开始时间, 结束时间）
activities = {'A':(0, 6),'B':(1, 2),'C':(2, 3),'D':(4, 5),'E':(5, 7),
}optimal_activities = activity_selection(activities)for name in optimal_activities:print(f"选择的活动为：{name} 开始时间: {activities[name][0]}, 结束时间: {activities[name][1]}")

结果

选择的活动为：B 开始时间: 1, 结束时间: 2
选择的活动为：C 开始时间: 2, 结束时间: 3
选择的活动为：D 开始时间: 4, 结束时间: 5
选择的活动为：E 开始时间: 5, 结束时间: 7

1.3.2 01背包问题

给定一个背包，其最大承载重量为 $W$，以及一组物品，每个物品都有一个重量和一个价值。目标是选择物品，使得在不超过背包承载重量的情况下，物品的总价值最大。具体如下：

物品	重量	价值(元)
A	1	1
B	3	4
C	4	5
D	5	7

假设背包的最大承载重量 $W=7$。

（1）制定贪心选择准则
优先选择单位重量价值最高的，该问题采用贪心策略不一定得到全局最优解。

（2）预演贪心算法
在不超过最大承重的基础上优先选择单位重量价值最高的，然后按单位重量价值遍历剩下的物品：

• 首先选择物品D，因为其价值/重量比为$7/5=1.4$，此时书包容量为2；
• 遇到物品B，其价值/重量比为$\frac{4}{3}$，但是书包容量小于其重量3；
• 遇到物品C，其价值/重量比为$5/4=1.25$，但是书包容量小于其重量4；
• 遇到物品A，其价值/重量比为$1/1=1$，书包容量大于其重量1；可以选择
• 结束

最后选择的物品为D和A，其价值为7+1=8。很明显，上述根据贪心策略得到的解不是全部最优解，最优解为选择物品3和4，最大价值为9。

（3）Python3实现

class Item:def __init__(self, name, value, weight):self.name = nameself.value = valueself.weight = weightself.ratio = value / weight  # 价值/重量比def knapsack_greedy(capacity, items):# 按照价值/重量比降序排序items.sort(key=lambda x: x.ratio, reverse=True)total_value = 0  # 记录总价值total_weight = 0  # 记录总重量selected_name = []for item in items:if total_weight + item.weight <= capacity:total_weight += item.weighttotal_value += item.valueselected_name.append(item.name)return selected_name# 示例物品（价值, 重量）
items = [Item('A', 1, 1),Item('B', 4, 3),Item('C', 5, 4),Item('D', 7, 5),
]capacity = 7  # 背包容量selected_name = knapsack_greedy(capacity, items)
print("贪心算法选择的物品:", selected_name)

结果

贪心算法选择的物品: ['D', 'A']

1.3.3 最优解分析

利用贪心策略能够得到最优解的问题主要有下面两个重要特性：

（1）当前选择不影响后续选择：一旦做出某个选择，后续的选择仍然可以独立于这个选择进行。

• 01背包问题中：后面的选择会受到已经选择的物品重量的影响。
• 活动选择问题：因为每次都选的是结束时间最早的， 当前的选择不会影响后面的选择。

（2）问题具有最优子结构：可以通过组合其子问题的最优解来构建整个问题的最优解。

• 活动选择问题中：如果把结束时间分别定为T，和T+M，分别求解满足这两个结束时间的最多可参加的活动，活动集合分别为A和B，那么A肯定是B的子集。
• 背包问题中，最大承载重量为4的书包可装的物品，不一定是最大承载重量为5的书包承载物品的子集。

2 贪心策略的应用

2.1 应用：计算单源最短路径

单源最短路径问题是图论中的一个经典问题，旨在找到从给定起始节点（源节点）到图中所有其他节点的最短路径。该问题可以应用于多种实际场景，例如地图导航、网络路由和交通规划等。
本问题是针对边权非负的图，使用Dijkstra算法结合贪心策略逐步找到源节点到其它节点的最短路径。

import matplotlib.pyplot as plt
import networkx as nxdef dijkstra(graph, start):distances = {vertex: float('inf') for vertex in graph}distances[start] = 0unvisited = set(graph.keys())previous_vertices = {vertex: None for vertex in graph}# 贪心策略：每次从未访问的节点中选择当前距离最小的节点进行处理while unvisited:current_vertex = min((vertex for vertex in unvisited),key=lambda vertex: distances[vertex])if distances[current_vertex] == float('inf'):breakfor neighbor, weight in graph[current_vertex].items():distance = distances[current_vertex] + weight# 贪心策略：如果通过当前节点到达邻接节点的距离小于已知的距离，则更新该距离。if distance < distances[neighbor]:distances[neighbor] = distanceprevious_vertices[neighbor] = current_vertexunvisited.remove(current_vertex)return distances, previous_vertices# 从 Dijkstra 算法计算的前驱节点信息中提取从源节点到特定目标节点的最短路径。
def get_shortest_path(previous_vertices, start, end):path = []current_vertex = endwhile current_vertex is not None:path.append(current_vertex)current_vertex = previous_vertices[current_vertex]path.reverse()return pathdef visualize_graph(graph, shortest_paths, previous_vertices, start):G = nx.Graph()for vertex, edges in graph.items():for neighbor, weight in edges.items():G.add_edge(vertex, neighbor, weight=weight)pos = nx.spring_layout(G)  # 计算节点的位置# 绘制图形nx.draw(G, pos, with_labels=True, node_size=700, node_color='lightblue', font_size=16)# 绘制边和边的权重edge_labels = nx.get_edge_attributes(G, 'weight')nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_color='red', font_size=12)# 高亮显示起始节点nx.draw_networkx_nodes(G, pos, nodelist=[start], node_color='orange')# 高亮显示最短路径for vertex in shortest_paths:if vertex is not None and previous_vertices[vertex] is not None:nx.draw_networkx_edges(G, pos, edgelist=[(vertex, previous_vertices[vertex])], edge_color='green', width=2)plt.title("Graph Visualization with Dijkstra's Algorithm", size=16)plt.show()# 示例图的表示：字典形式，邻接表
graph = {'A': {'B': 1, 'C': 4},'B': {'A': 1, 'C': 2, 'D': 5},'C': {'A': 4, 'B': 2, 'D': 1},'D': {'B': 5, 'C': 1}
}# 计算从起始节点 'A' 到所有其他节点的最短路径
start_vertex = 'A'
shortest_paths, previous_vertices = dijkstra(graph, start_vertex)# 输出结果
print("从节点", start_vertex, "到各个节点的最短路径:")
for vertex, distance in shortest_paths.items():print(f"{vertex}: {distance}")# 可视化图
visualize_graph(graph, shortest_paths, previous_vertices, start_vertex)

结果

从节点 A 到各个节点的最短路径:
A: 0
B: 1
C: 3
D: 4

2.2 应用：霍夫曼编码字符串

霍夫曼编码（Huffman Coding）是一种广泛使用的无损数据压缩算法，由大卫·霍夫曼于1952年提出。它利用字符频率的统计信息，通过构建霍夫曼树来为每个字符分配一个变长的二进制编码，从而有效地减少数据的存储空间。

import heapq
from collections import defaultdict# 定义霍夫曼树的节点
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.freqdef build_huffman_tree(frequencies):# 创建优先队列（最小堆），将每个字符及其频率作为节点加入堆中heap = [Node(char, freq) for char, freq in frequencies.items()]heapq.heapify(heap)  # 将列表转换为堆# 当堆中节点数量大于1时，继续合并节点while len(heap) > 1:# 取出频率最小的两个节点（贪心选择）left = heapq.heappop(heap)right = heapq.heappop(heap)# 创建新的父节点，其频率为左右子节点频率之和merged = Node(None, left.freq + right.freq)merged.left = leftmerged.right = right# 将新节点放回堆中heapq.heappush(heap, merged)return heap[0]  # 返回树的根节点def generate_codes(node, prefix="", codebook=None):if codebook is None:codebook = {}if node is not None:if node.char is not None:  # 如果是叶子节点codebook[node.char] = prefix  # 将编码存入字典# 递归遍历左子树，路径前缀加上"0"generate_codes(node.left, prefix + "0", codebook)# 递归遍历右子树，路径前缀加上"1"generate_codes(node.right, prefix + "1", codebook)return codebookdef huffman_encoding(data):# 统计每个字符的频率frequencies = defaultdict(int)for char in data:frequencies[char] += 1  # 计算每个字符出现的次数# 构建霍夫曼树root = build_huffman_tree(frequencies)# 生成霍夫曼编码return generate_codes(root)def huffman_decoding(encoded_data, huffman_codes):# 反转霍夫曼编码字典，以便根据编码解码reverse_codes = {v: k for k, v in huffman_codes.items()}current_code = ""decoded_output = []# 遍历编码数据for bit in encoded_data:current_code += bit  # 构建当前编码if current_code in reverse_codes:  # 如果当前编码在反转字典中decoded_output.append(reverse_codes[current_code])  # 解码得到字符current_code = ""  # 重置当前编码return ''.join(decoded_output)  # 返回拼接的解码字符串# 示例数据
data = "tanxinshi一zhongcelue"# 进行霍夫曼编码
huffman_codes = huffman_encoding(data)
print("霍夫曼编码:")
for char, code in huffman_codes.items():print(f"{char}: {code}")# 编码字符串
encoded_data = ''.join(huffman_codes[char] for char in data)
print("\n编码后的数据:", encoded_data)# 解码字符串
decoded_data = huffman_decoding(encoded_data, huffman_codes)
print("解码后的数据:", decoded_data)

结果

霍夫曼编码:
o: 0000
a: 0001
e: 001
u: 0100
l: 0101
z: 0110
x: 0111
s: 1000
g: 1001
一: 1010
h: 1011
n: 110
i: 1110
t: 11110
c: 11111编码后的数据: 11110000111001111110110100010111110101001101011000011010011111100101010100001
解码后的数据: tanxinshi一zhongcelue

3 策略优缺点

3.1 优点

• 简单易理解：
  贪心算法的实现通常较为简单，易于理解和实现。它通过逐步选择局部最优，减少了算法的复杂性。
• 高效：
  许多贪心算法的时间复杂度较低，通常为 $O(nlogn)$ 或$ O(n)$，这使得它们在处理大规模数据时非常有效。由于贪心算法只需进行一次遍历，通常不需要多次计算。
• 直观性：
  贪心算法通常符合直觉，特别是在处理某些问题时，如最小生成树和最短路径问题（例如 Dijkstra 算法），通过局部最优选择能够快速得到解。

3.2 缺点

• 不保证全局最优：
  贪心算法在很多情况下并不能保证得到全局最优解。在某些问题中，局部最优选择可能导致最终解不是最优的。例如，在背包问题的某些变体中，贪心策略可能无法找到最佳解。
• 难以找到合适的贪心选择：
  在一些复杂的问题中，确定一个有效的贪心选择并不明显，可能需要进行深入的分析和试错。
• 无法应对复杂约束：
  对于具有复杂约束条件的问题，贪心算法可能无法找到符合约束的解，或需要额外的步骤进行调整。

3.3 总结

• 当遇见非常棘手的问题时，贪心算法也是一种解决办法，哪怕找不到最优解，也会是近似最优解；
• 要想利用贪心算法获得全局最优解，需要对问题进入深入分析；
• 贪心是一种策略，可与很多算法深度融合；