算法数据结构学习
贪心算法
20486 min
2024-7-16
2024-11-9
type
status
date
slug
summary
tags
category
icon
password
简介
贪心算法简单来说就是选择局部最优解的方法，例如 给你各种硬币都不限数量，需要找最少的硬币数的方法那样，自然是从最大的开始选，那时便是局部最优解，但是很多时候局部最优解并非全局最优解，所以很多问题需要对其进行分解，对其中的某个子部分使用贪心的方法。
 
只有局部最优解能找到全局最优解的问题才可以直接使用。例如
455. 分发饼干 - 力扣（LeetCode）
455. 分发饼干 - 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。   示例 1: 输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。 示例 2: 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出 2。   提示： * 1 <= g.length <= 3 * 104 * 0 <= s.length <= 3 * 104 * 1 <= g[i], s[j] <= 231 - 1   注意：本题与 2410. 运动员和训练师的最大匹配数 [https://leetcode.cn/problems/maximum-matching-of-players-with-trainers/] 题相同。
455. 分发饼干 - 力扣（LeetCode）
https://leetcode.cn/problems/assign-cookies/
455. 分发饼干 - 力扣（LeetCode）
这里将饼干分给孩子们，可以简单的将尽量小的饼干分给胃口尽量大的孩子，然后一直进行下去，直到饼干分完或者孩子都吃了或者是不够吃之类的。
（PS：虽然官方题解说到了使用双指针遍历的时候降低时间复杂度，反正这样也能过后头再说吧hhh）
还有一些图中的路径生成树之类的算法，也是用到了贪心的思想，虽然他们的局部最优就是全局最优的性质就没有上面这种简单的题目这样好证明了
 
Kruskal算法、Prim算法和Dijkstra算法都属于贪心算法。贪心算法的核心思想是通过局部最优选择来希望最终达到全局最优。要证明这些算法在特定问题中“局部最优即全局最优”的性质，我们需要具体分析每个算法的特性和问题。
以下是AI给出的简单解释

1. Kruskal算法（最小生成树）

Kruskal算法是求解最小生成树（MST）的一种贪心算法。它的基本步骤是：
  1. 将图中的所有边按权值从小到大排序。
  1. 依次选择权值最小的边，若该边连接的两个点不在同一个连通分量中，则将这条边加入生成树中，直到生成树包含所有节点。
为什么局部最优就是全局最优：
  • Kruskal算法的贪心策略是每次选择当前权值最小的边加入到生成树中。为了证明其局部最优就是全局最优，关键是要使用切分定理（cut property）。切分定理表明，如果在图的某个切分（即把图的节点分成两部分）中，某条边是连接两部分的最小权边，那么这条边一定是最小生成树的一部分。
  • 通过选择最小边，Kruskal算法可以确保每一步的选择不会破坏生成树的最小权值和连通性，从而最终得到最优的生成树。

2. Prim算法（最小生成树）

Prim算法也是求解最小生成树（MST）的贪心算法。它的基本步骤是：
  1. 从任意一个节点开始，逐步扩展生成树，每次选择一条边，且这条边的权值最小且连接树中的节点和树外的节点。
  1. 重复该过程，直到生成树包含所有节点。
为什么局部最优就是全局最优：
  • Prim算法的贪心策略是每次选择一个当前最小的边来扩展生成树。这个选择可以通过局部最小边选择定理来证明，即在某个步骤，若某个边是当前生成树与剩余部分中最小的边，那么将这条边加入生成树不会影响最终的最小生成树。
  • 通过每一步都选择当前最小的边，Prim算法可以确保生成树在扩展过程中始终保持最优，且最终得到全局最优的生成树。

3. Dijkstra算法（单源最短路径）

Dijkstra算法是求解单源最短路径问题的贪心算法。它的基本步骤是：
  1. 初始化源点的距离为0，其他点的距离为无穷大。
  1. 从源点开始，逐渐扩展到其他点，每次选择当前未访问点中距离源点最近的点，更新其邻接点的最短路径。
  1. 继续这个过程，直到所有点的最短路径都被确定。
为什么局部最优就是全局最优：
  • Dijkstra算法的贪心策略是每次选择当前未访问的点中距离源点最近的点，并且更新其邻接点的最短路径。这个选择可以通过最短路径性质来证明。最短路径性质表明，若从源点到某个节点的路径是最短路径，那么沿着这条路径的任何一个节点到源点的路径，也必定是最短路径。
  • 由于每次选择距离源点最近的节点，并且更新它的邻接点，这确保了路径的最短性。最终，所有节点的最短路径都能通过这种局部最优的选择方式得到全局最优解。

总结：

  • Kruskal算法：通过选择最小权值的边并利用切分定理，保证了生成树的最小化。
  • Prim算法：通过选择连接当前树和外部节点的最小边，并利用局部最小边选择定理，确保了生成树的最小化。
  • Dijkstra算法：通过选择当前未访问节点中最短的路径，并利用最短路径性质，确保了最短路径的最优性。
这些算法通过局部最优的选择（每次选择最小边或最短路径）来确保最终的全局最优解。
 
现在我们基于leetcode上的一些题目，来写一下这俩算法
首先是Dijkstra算法
743. 网络延迟时间 - 力扣（LeetCode）
743. 网络延迟时间 - 有 n 个网络节点，标记为 1 到 n。 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。   示例 1： [https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png] 输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 输出：2 示例 2： 输入：times = [[1,2,1]], n = 2, k = 1 输出：1 示例 3： 输入：times = [[1,2,1]], n = 2, k = 2 输出：-1   提示： * 1 <= k <= n <= 100 * 1 <= times.length <= 6000 * times[i].length == 3 * 1 <= ui, vi <= n * ui != vi * 0 <= wi <= 100 * 所有 (ui, vi) 对都 互不相同（即，不含重复边）
743. 网络延迟时间 - 力扣（LeetCode）
https://leetcode.cn/problems/network-delay-time/description/
743. 网络延迟时间 - 力扣（LeetCode）
 
先将这个输入转化一下，然后基于DIJKSTRA算法找到每个点的最短路径。
在找最短路径的过程之中，每次选取没有被确定的且离起点距离最短的点，用它来更新剩下的所有点的距离，这里便用到了贪心的思想，我代码中也写了大致的注释。
 
 
再就是来个Kruskal算法吧，这个是找最小生成树的，感觉也是可以拿来找最短路径之类的功效。
1584. 连接所有点的最小费用 - 力扣（LeetCode）
1584. 连接所有点的最小费用 - 给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。 连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。 请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。   示例 1： [https://assets.leetcode.com/uploads/2020/08/26/d.png] 输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 输出：20 解释： [https://assets.leetcode.com/uploads/2020/08/26/c.png] 我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。 注意到任意两个点之间只有唯一一条路径互相到达。 示例 2： 输入：points = [[3,12],[-2,5],[-4,1]] 输出：18 示例 3： 输入：points = [[0,0],[1,1],[1,0],[-1,1]] 输出：4 示例 4： 输入：points = [[-1000000,-1000000],[1000000,1000000]] 输出：4000000 示例 5： 输入：points = [[0,0]] 输出：0   提示： * 1 <= points.length <= 1000 * -106 <= xi, yi <= 106 * 所有点 (xi, yi) 两两不同。
1584. 连接所有点的最小费用 - 力扣（LeetCode）
https://leetcode.cn/problems/min-cost-to-connect-all-points/
1584. 连接所有点的最小费用 - 力扣（LeetCode）
话说这一题也需要用到之前的并查集的相关知识。
遵循Kruskal算法的思想，将这些所有点连成边，将边再进行排序，从最短的开始遍历，只要这个边两点不是之前已经连起来过的（PS：这里如何判断两个点是不是已经联通了的呢，就需要用到并查集，后面的把边添加到结果中去的时候，也要把这两点联通。），就把这条边加到最小生成树中去，在这一题中便是将这条边的距离累加到res中去，话说复杂度还是有点偏高的针对这道题。
上一篇
Trie算法
下一篇
并查集
Catalog