GENIA

贪心算法

2022-12-17

1.贪心算法

概念与实例

贪心算法是一种在每个决策点取当前最优解的算法。它的目的是在每个决策点尽可能地选择最优解，希望能够导致整个问题的最优解。

贪心算法的步骤如下：

  1. 定义问题的最优子结构。这意味着问题的最优解可以从子问题的最优解中得出。
  2. 选择局部最优解。在每个决策点，贪心算法选择当前看起来最优的解决方案。
  3. 确定贪心策略。贪心策略是贪心算法在每个决策点选择局部最优解的方法。
  4. 验证贪心策略的正确性。在求解问题时，需要证明贪心策略能够得出问题的最优解。
  5. 应用贪心算法。在贪心算法的框架下，按照贪心策略的方法逐步求解问题。

贪心算法的一个经典例子是最短路径问题（选择排序也是）。在最短路径问题中，我们希望从一个起点出发，找到一条到达终点的路径，使得这条路径的长度最短。贪心算法可以通过每次选择距离起点最近的未访问过的节点来求解最短路径问题。这样，每次选择都是当前看起来最优的选择，因此称为贪心策略。

以下是用python实现最短路径问题的例子：

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
#定义路径结构体，包含起点、终点和路径长度三个属性
class Path:
    def __init__(self, start, end, length):
        self.start = start
        self.end = end
        self.length = length
#定义贪心算法的函数，需要传入起点、终点和所有路径的列表
def greedy(start, end, paths):
    result = []  # 用来保存最终的路径
    visited = set()  # 用来记录已经访问过的节点
    current = start  # 当前所在的节点
    while current != end:  # 当前节点不是终点就继续循环
        # 找到从当前节点出发的未访问过的路径中距离最短的路径
        min_path = min(
            [p for p in paths if p.start == current and p.end not in visited],
            key=lambda x: x.length
        )
        result.append(min_path)  # 将路径加入结果列表
        visited.add(min_path.end)  # 将终点标记为已访问
        current = min_path.end  # 更新当前节点
    return result
#假设我们有以下路径：
paths = [
    Path('A', 'B', 5),
    Path('A', 'C', 3),
    Path('B', 'C', 2),
    Path('B', 'D', 4),
    Path('C', 'D', 6),
]
#调用贪心算法函数求解最短路径问题
result = greedy('A', 'D', paths)

# 打印结果
for path in result:
    print(f"{path.start} -> {path.end}: {path.length}")

输出结果为：

1
2
3
A -> C: 3
C -> B: 2
B -> D: 4

贪心的局限性

1.不能保证求得的最后解是最佳的
2.不能用来求最大值或最小值的问题
3.只能求满足某些约束条件的可行解的范围

局部最优不等于全局最优。

弥补策略

1.分治法

分治法通过将问题分成若干个规模较小的子问题来求解。分治法可以用来解决最优化问题。

基本思想：将问题分成若干个子问题，然后递归地求解这些子问题，最后合并子问题的结果得到最终的答案。

2.动态规划

动态规划通过对问题进行分析，找出其最优子结构，并通过记忆化搜索来避免重复计算，从而得到问题的最优解。

基本思想：将问题分解成若干个子问题，然后按照拓扑关系依次求解这些子问题，最后将子问题的解合并起来。

2.数字三角形

题目标签：动态规划 2020 省赛

按照标签这道题确实应该用动态规划来做，但是题目放水了，实际上用贪心就可以解决。

根据 “此外，向左下走的次数与向右下走的次数相差不能超过 1。” 这个条件，可以对题目做一些简化。

如果输入的行数N为奇数，则最后一定会走到最后一行的中点。

如果输入的行数N为偶数，则最后一定会走到最后一行的中间两个数。

将不可能走到的数置为一个非常小的数，从倒数第二行的第一个数开始遍历，每次加上下面两个数之间的较大值，层层累加，即可得到最长路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
list0=[]
N=eval(input())
#将输入的数据存放在一个二维列表中，一个行为一个元素
for i in range(N):
        nums=list(map(int,input().split()))
        list0.append(nums)
#将走不到的位置置成极小值
for i in range(N//2+1,N):
        for j in range(0,i-N//2):
                list0[i][j]=-100
                list0[i][-j-1]=-100
#回溯相加
for i in range(N-2,-1,-1):
        for j in range(0,i+1):
                list0[i][j]+=max(list0[i+1][j],list0[i+1][j+1])

print(list0[0][0])

我尝试了奇数和偶数的案例，本地运行都没有问题，测试平台上却发生了奇怪的错误：

去掉split()方法中的参数就不再发生段错误了，具体是什么原因？

有一个注意点：碰到这一类问题，不能局限于题目给的测试样例进行推算，确定循环的范围。这道题一开始提交的时候只能通过两个测试案例，就是因为我想当然的将range(0,i-N//2)写成了range(0,i-2)。

Tags: 算法
dp基础：背包问题 →