• 【贪心算法】原理思想、算法步骤，应用示例（找零问题、活动选择问、霍夫曼编码、最小生成树问题、车辆路径问题）

            贪心算法是一种基于贪心策略的优化算法，它在每一步选择中都采取当前状态下的最优决策，而不考虑未来的后果。通常，这种算法对于解决一些最优化问题非常有效，尤其是那些可以通过局部最优解来达到全局最优解的问题。

    1 贪心算法的基本思想：

    1. 建立贪心选择的标准： 在每一步选择中，根据某个标准选择当前最优的解。
    2. 做出选择： 基于建立的标准，做出当前最优的选择。
    3. 更新问题： 通常，做出选择后，问题将被更新为一个子问题。解决子问题，继续应用贪心策略。

    2 示例：找零问题

    问题描述： 给定一些面额不同的硬币，如1元、5元、10元，要找零n元，找零的硬币数量要尽可能少。

    贪心策略： 在每一步选择中，选择面额最大的硬币，直到找零的总金额达到n。

    算法步骤：

    1. 初始化一个空列表，用于存储找零的硬币。
    2. 从面额最大的硬币开始，将尽可能多的这个硬币加入列表，直到总金额超过n。
    3. 如果总金额等于n，算法结束。否则，将面额减小到次大的硬币，重复步骤2。

    Python 代码示例：

    1. def greedy_change(n, coins):
    2.     coins.sort(reverse=True)  # 按面额降序排列
    3.     change = []  # 存储找零的硬币
    4.     total = 0  # 当前找零的总金额
    5.  
    6.     for coin in coins:
    7.         while total + coin <= n:
    8.             change.append(coin)
    9.             total += coin
    10.  
    11.     return change
    12.  
    13. # 示例
    14. n = 63
    15. coin_denominations = [1, 5, 10, 20, 50]
    16. result = greedy_change(n, coin_denominations)
    17. print("Greedy Change for", n, ":", result)

    在这个例子中，贪心算法首先选择面额最大的硬币（50元），然后选择10元，最后选择3个1元，完成找零过程。尽管这个算法可能无法得到最优解，但它通常能够得到一个近似最优解，而且计算效率高。

    3 示例： 活动选择问题（Activity Selection Problem）：

    • 问题描述： 给定一系列活动，每个活动都有开始时间和结束时间，目标是选择尽可能多的互不相交的活动。
    • 贪心策略： 在每一步选择中，选择结束时间最早的活动，以便腾出更多时间给其他活动。
    • 应用场景： 会议室安排、课程表安排等。
    • Python 代码示例：
      1. def activity_selection(activities):
      2.     # 按照结束时间排序
      3.     sorted_activities = sorted(activities, key=lambda x: x[1])
      4.     selected_activities = [sorted_activities[0]]  # 选择第一个活动
      5.     last_end_time = sorted_activities[0][1]
      6.  
      7.     # 选择互不相交的活动
      8.     for activity in sorted_activities[1:]:
      9.         if activity[0] >= last_end_time:
      10.             selected_activities.append(activity)
      11.             last_end_time = activity[1]
      12.  
      13.     return selected_activities
      14.  
      15. # 示例
      16. activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
      17. result = activity_selection(activities)
      18. print("Selected Activities:", result)

      在这个示例中，我们首先将活动按照结束时间进行排序，然后从第一个活动开始，依次选择结束时间不与已选择活动相交的活动，直到无法选择更多活动为止。

    4 示例：霍夫曼编码（Huffman Coding）：

    • 问题描述： 给定一组字符及其出现的频率，构建一个最优的二进制编码，使得出现频率高的字符具有较短的编码。
    • 贪心策略： 构建霍夫曼树，选择出现频率最低的两个节点合并，重复此过程直到只剩一个节点。
    • 应用场景： 数据压缩、图像编码等。
    • Python 代码示例：
      1. import heapq
      2. from collections import defaultdict
      3.  
      4. # 定义霍夫曼树的节点类
      5. class HuffmanNode:
      6.     def __init__(self, char, freq):
      7.         self.char = char
      8.         self.freq = freq
      9.         self.left = None
      10.         self.right = None
      11.  
      12.     def __lt__(self, other):
      13.         return self.freq < other.freq
      14.  
      15. # 构建霍夫曼树
      16. def build_huffman_tree(freq_map):
      17.     # 利用最小堆来实现构建霍夫曼树的过程
      18.     min_heap = [HuffmanNode(char, freq) for char, freq in freq_map.items()]
      19.     heapq.heapify(min_heap)
      20.  
      21.     while len(min_heap) > 1:
      22.         left = heapq.heappop(min_heap)
      23.         right = heapq.heappop(min_heap)
      24.         merged = HuffmanNode(None, left.freq + right.freq)
      25.         merged.left = left
      26.         merged.right = right
      27.         heapq.heappush(min_heap, merged)
      28.  
      29.     return min_heap[0]
      30.  
      31. # 生成霍夫曼编码
      32. def generate_huffman_codes(root, current_code, codes):
      33.     if root is not None:
      34.         if root.char is not None:
      35.             codes[root.char] = current_code
      36.         generate_huffman_codes(root.left, current_code + '0', codes)
      37.         generate_huffman_codes(root.right, current_code + '1', codes)
      38.  
      39. # 霍夫曼编码
      40. def huffman_coding(text):
      41.     freq_map = defaultdict(int)
      42.     for char in text:
      43.         freq_map[char] += 1
      44.  
      45.     root = build_huffman_tree(freq_map)
      46.     codes = {}
      47.     generate_huffman_codes(root, '', codes)
      48.  
      49.     # 将原始文本编码为霍夫曼编码
      50.     encoded_text = ''.join(codes[char] for char in text)
      51.     return encoded_text, codes
      52.  
      53. # 示例
      54. text_to_encode = "huffman coding is fun!"
      55. encoded_text, huffman_codes = huffman_coding(text_to_encode)
      56.  
      57. # 打印结果
      58. print("Original Text:", text_to_encode)
      59. print("Encoded Text:", encoded_text)
      60. print("Huffman Codes:", huffman_codes)

      这段代码演示了如何使用贪心算法构建霍夫曼树，并生成字符的霍夫曼编码。在实际应用中，霍夫曼编码通常用于数据压缩，以便更有效地存储和传输数据。

      在这个示例中，我们首先统计了给定文本中每个字符的出现频率，并构建了一个霍夫曼树。然后，通过遍历霍夫曼树，生成每个字符的二进制编码。最终，我们将原始文本编码为霍夫曼编码。霍夫曼编码通常用于数据压缩，通过给出出现频率高的字符较短的编码来减小数据的存储空间。

    5  示例：最小生成树问题（Minimum Spanning Tree）：

    • 问题描述： 给定一个连通的无向图，找到一个最小权重的树，使得图中所有节点都连接在一起。
    • 贪心策略： 使用Kruskal算法或Prim算法，每次选择边权重最小的边加入生成树。
    • 应用场景： 网络设计、电缆布线等。
    • Python 代码示例： 
        1. import heapq
        2.  
        3. def prim(graph):
        4.     n = len(graph)
        5.     visited = [False] * n
        6.     min_heap = [(0, 0)]  # (权重, 节点)的最小堆
        7.     minimum_spanning_tree = []
        8.  
        9.     while min_heap:
        10.         weight, node = heapq.heappop(min_heap)
        11.         if not visited[node]:
        12.             visited[node] = True
        13.             minimum_spanning_tree.append((weight, node))
        14.  
        15.             for neighbor, edge_weight in graph[node]:
        16.                 heapq.heappush(min_heap, (edge_weight, neighbor))
        17.  
        18.     return minimum_spanning_tree
        19.  
        20. # 示例
        21. graph = {
        22.     0: [(1, 2), (3, 1)],
        23.     1: [(0, 2), (3, 3), (2, 1)],
        24.     2: [(1, 1), (3, 5)],
        25.     3: [(0, 1), (1, 3), (2, 5)]
        26. }
        27.  
        28. result = prim(graph)
        29. print("Minimum Spanning Tree:", result)

        在这个示例中，我们使用Prim算法构建了一个最小生成树。算法从起始节点开始，选择与当前生成树连接的边中权重最小的边，然后将连接的节点加入生成树。这一过程重复直到所有节点都加入生成树为止。

    6 示例：车辆路径问题（Vehicle Routing Problem）：

    • 问题描述： 有一组客户点和一个中心仓库，目标是找到一条路径，使得所有客户都被访问，并且路径总长度最短。
    • 贪心策略： 从仓库出发，选择离当前位置最近的客户点，重复此过程直到所有客户都被访问。
    • 应用场景： 物流配送、快递路线规划等。
    • Python 代码示例：
      1. import numpy as np
      2.  
      3. def euclidean_distance(point1, point2):
      4.     # 计算两点之间的欧几里德距离
      5.     return np.linalg.norm(np.array(point1) - np.array(point2))
      6.  
      7. def vehicle_routing(customers, warehouse):
      8.     route = [warehouse]  # 路线的起始点是仓库
      9.     remaining_customers = set(customers)
      10.  
      11.     while remaining_customers:
      12.         # 计算当前位置到所有剩余客户点的距离，并选择最近的客户点
      13.         current_location = route[-1]
      14.         nearest_customer = min(remaining_customers, key=lambda customer: euclidean_distance(current_location, customer))
      15.         
      16.         # 将最近的客户点添加到路线中
      17.         route.append(nearest_customer)
      18.         remaining_customers.remove(nearest_customer)
      19.  
      20.     # 返回最终路线
      21.     return route
      22.  
      23. # 示例
      24. warehouse_location = (0, 0)
      25. customer_locations = [(1, 2), (3, 5), (6, 8), (9, 4), (7, 1)]
      26.  
      27. final_route = vehicle_routing(customer_locations, warehouse_location)
      28.  
      29. # 打印结果
      30. print("Warehouse Location:", warehouse_location)
      31. print("Customer Locations:", customer_locations)
      32. print("Final Route:", final_route)

      这段代码演示了如何使用贪心算法解决车辆路径问题。在这个问题中，我们有一组客户点和一个中心仓库，目标是找到一条路径，使得所有客户都被访问，并且路径总长度最短。通过选择每次最近的客户点进行访问，贪心算法可以得到一个近似最优解。在实际应用中，车辆路径问题常常出现在物流配送和快递路线规划等场景中。

  • 相关阅读:
    【51单片机】认识单片机
    Aptos 深度解读：机遇、挑战与风险
    go 语言之 select
    SpringBoot内置Tomcat报错RFC7230 and RFC3986终极方案（修改Http11Processor源码）
    支付宝小程序集成MQTT
    三元前驱体废水除钴项目，出水1mg/l以下
    【每日一题Day47】LC1774最接近目标价格的甜点成本 | 回溯 哈希表
    [iOS- Mac终端上传Git and 生成Token]
    对象映射的那些事儿及MapStruct入门
    视图解析器常见功能、处理静态资源、类型转换器
  • 原文地址：https://blog.csdn.net/qq_35831906/article/details/134389919