【数据结构和算法】-贪心算法

贪心算法（又称贪婪算法）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤为有效，它通过将问题分解为一系列更小的子问题，并依次解决这些子问题，从而得到原问题的解。

贪心算法的基本思路是从问题的某一个初始解出发，逐步逼近给定的目标，以尽可能快地求得更好的解。当某个步骤不能再继续前进时，算法就停止执行。贪心算法并不是对所有问题都能得到整体最优解，关键是贪心策略的选择。选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

贪心算法的主要特点包括：

1. 局部最优选择：在每一步，算法都根据某种局部最优的准则进行选择，以期望通过这种方式得到全局最优解。
2. 简化问题：每做一次贪心选择，就将所求问题简化为一个规模更小的子问题。
3. 迭代进行：贪心算法通常以自顶向下的方式进行，通过迭代的方法逐步得到问题的解。

贪心算法可以解决的问题通常具有一些特殊的性质，如贪心选择性质和最优子结构性质。贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到。最优子结构性质是指问题的最优解包含其子问题的最优解。这些性质是贪心算法能够成功解决问题的关键。
接下来我们看几个例子：

找零问题

一个贪心算法的实际例子是找零问题，即给定一些面值的硬币，如何用最少数量的硬币来凑齐一个给定的金额。这个问题可以使用贪心算法来解决，基本思路是从面值最大的硬币开始，尽可能多地使用这种硬币，直到剩余的金额无法再使用这种硬币为止，然后转而使用面值次大的硬币，依此类推。

例如，假设我们有面值为1元、50分、25分、10分、5分和1分的硬币，我们需要凑齐93分。按照贪心算法的思想，我们可以按照硬币面值从大到小的顺序进行考虑：

1. 首先考虑面值最大的1元硬币，但93分不足以使用1元硬币，所以我们跳过1元硬币。
2. 接着考虑50分硬币，因为93分大于50分，所以我们可以使用一枚50分硬币，此时剩余金额为43分。
3. 然后考虑25分硬币，因为43分大于25分，所以我们可以使用一枚25分硬币，此时剩余金额为18分。
4. 接下来考虑10分硬币，因为18分大于10分，所以我们可以使用一枚10分硬币，此时剩余金额为8分。
5. 再考虑5分硬币，因为8分大于5分，所以我们可以使用一枚5分硬币，此时剩余金额为3分。
6. 最后，我们使用三枚1分硬币来凑齐剩余的3分。

通过贪心算法，我们使用了6枚硬币来凑齐93分，这是使用最少数量硬币的方法。

需要注意的是，贪心算法并不总是能得到最优解，但在某些情况下，如硬币找零问题中硬币面值设计合理时，贪心算法可以得到最优解。因此，在选择使用贪心算法时，需要确保问题满足贪心算法的前提条件和特性。

以下是使用贪心算法解决找零问题的 Python 代码示例：

def make_change(amount, coins):
    # coins 列表应按照面值从大到小的顺序排列
    coins.sort(reverse=True)
    change = []  # 用于存储找零的硬币列表
    remaining = amount  # 剩余需要凑齐的金额

    for coin in coins:
        # 当剩余金额大于等于当前硬币的面值时，就使用该硬币
        while remaining >= coin:
            change.append(coin)
            remaining -= coin
        # 如果剩余金额已经为0，则无需继续考虑后面的硬币
        if remaining == 0:
            break

    # 如果最终剩余金额不为0，说明无法用给定的硬币凑齐
    if remaining != 0:
        return None  # 或者可以抛出异常或返回其他错误标识

    return change

# 示例：假设有面值为 [1, 5, 10, 25] 的硬币，需要凑齐93分
coins = [1, 5, 10, 25]
amount = 93
change_list = make_change(amount, coins)

if change_list is not None:
    print("找零的硬币列表为：", change_list)
    print("所需硬币总数为：", len(change_list))
else:
    print("无法用给定的硬币凑齐金额")
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

在这段代码中，我们首先定义了一个函数 make_change，它接受两个参数：amount（需要凑齐的金额）和 coins（可用的硬币面值列表）。然后，我们按照硬币面值从大到小的顺序对硬币进行排序。接着，我们遍历排序后的硬币列表，尽可能多地使用当前硬币来凑齐剩余金额，直到剩余金额为0或者无法再使用当前硬币为止。最后，我们检查是否还有剩余的金额无法凑齐，如果有则返回 None 或抛出异常，否则返回找零的硬币列表。

注意，这段代码假设硬币面值列表已经按照从大到小的顺序排列。如果硬币面值列表未排序，你需要在调用 make_change 函数之前先对 coins 进行排序。此外，这段代码只考虑了找零硬币的数量，没有考虑找零硬币的总面值是否等于原始金额，这在实际情况中通常是隐含的，因为每一步都是根据剩余金额来选取硬币的。

网络路由流量分配

实际生产中，贪心算法常用于各种优化问题，其中一个常见的例子是在网络路由中使用贪心算法进行流量分配。下面我将给出一个简化的例子，即使用贪心算法解决带权重的网络流量分配问题。

假设我们有一个网络，其中节点代表路由器或交换机，边代表它们之间的连接，边的权重代表连接的带宽。我们的目标是分配流量，使得每条连接的带宽都得到充分利用，同时避免过载。

为了简化问题，我们假设每个节点都有一个固定的流量需求，流量只能从源节点流向目标节点，且每条边的带宽都是固定的。贪心策略可以是每次选择剩余带宽最大的边来分配流量。

以下是一个简单的 Python 代码示例，用于解决这个问题：

import heapq
from collections import defaultdict

class Network:
    def __init__(self, edges, demands):
        # edges: [(source, target, capacity), ...]
        # demands: {source: target_demand, ...}
        self.graph = defaultdict(list)
        self.capacities = {}
        self.demands = demands
        self.allocated = defaultdict(int)
        
        for source, target, capacity in edges:
            self.graph[source].append(target)
            self.graph[target].append(source)
            self.capacities[(source, target)] = capacity
            self.capacities[(target, source)] = capacity
        
        # 初始化最大堆，按照剩余带宽从大到小排序
        self.max_heap = [(capacity, source, target) for source, target, capacity in edges]
        heapq.heapify(self.max_heap)
    
    def allocate_flow(self):
        while self.max_heap:
            capacity, source, target = heapq.heappop(self.max_heap)
            
            # 如果源节点的需求已经被满足，则跳过
            if self.allocated[source] >= self.demands[source]:
                continue
            
            # 计算可以分配的流量
            allocatable = min(capacity - self.allocated[(source, target)], self.demands[source] - self.allocated[source])
            
            # 分配流量
            self.allocated[(source, target)] += allocatable
            self.allocated[source] += allocatable
            
            # 更新剩余带宽到最大堆中
            remaining_capacity = capacity - self.allocated[(source, target)]
            if remaining_capacity > 0:
                heapq.heappush(self.max_heap, (remaining_capacity, source, target))
            
            # 检查是否所有需求都已满足
            if self.allocated[source] == self.demands[source]:
                break
        
        # 检查是否所有需求都得到满足
        return all(allocated == demand for source, demand in self.demands.items() for allocated in [self.allocated[source], self.allocated.get((source, target), 0][::2])

# 示例使用
edges = [
    ('A', 'B', 10),
    ('A', 'C', 5),
    ('B', 'C', 8),
    ('B', 'D', 7),
    ('C', 'D', 6)
]
demands = {'A': 8, 'B': 4, 'C': 2}

network = Network(edges, demands)
if network.allocate_flow():
    print("流量分配成功!")
    for source, target in network.capacities:
        print(f"从 {source} 到 {target} 分配了 {network.allocated[(source, target)]} 单位流量")
else:
    print("流量分配失败，无法满足所有需求!")
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

在这个示例中，Network 类表示网络，它维护了一个图结构（通过邻接表表示）以及每条边的带宽。allocate_flow 方法使用贪心策略来分配流量，每次都从剩余带宽最大的边开始分配。如果成功分配了所有流量，它会打印出每条边分配的流量；否则，它会报告分配失败。

注意，这个简化示例没有考虑许多实际网络流量分配问题中的复杂因素，比如流量的动态变化、多路径路由、故障恢复等。在实际生产环境中，网络流量分配通常更加复杂，并且会结合其他算法和技术来实现高效和可靠的流量管理。

贪心算法的前提条件和特性

贪心算法需要满足的前提条件和特性主要包括以下几点：

1. 最优子结构：问题的最优解可以通过子问题的最优解来推导得到。这意味着，如果我们将问题分解为若干个子问题，并且每个子问题都使用了贪心策略得到最优解，那么由这些子问题的最优解组合起来就能得到原问题的全局最优解。

2. 贪心选择性质：每一步的最优选择都可以导致最终的全局最优解。也就是说，贪心算法在每一步都做出在当前看来最好的选择，并希望这样的局部最优选择能够导致全局最优解。这种性质要求我们在设计贪心算法时，能够确定每一步的局部最优选择策略。

3. 无后效性：即某个状态以后的过程不会影响以前的状态，只与当前状态有关。这意味着贪心算法在做出选择后，不会因为后面的选择而改变之前的选择。

4. 可行性：贪心算法所做出的选择必须是可行的，即必须满足问题的约束条件。

贪心是解决局部最优，大家一定要注意，并不一定是全局最优，全局最优需要用到其他的比如动态规划等算法。后续我们会逐步介绍。