topic
贪心算法（Greedy Algorithm）是一种在求解优化问题时常用的算法策略。它在每一步都选择当前看起来最优的解决方案，而不考虑整体问题的最优解。 贪心算法通常在每一步都做出局部最优选择，希望通过一系列局部最优选择来达到全局最优解。
虽然贪心算法在某些情况下可以快速找到较好的解决方案，但它并不能保证总是得到最优解。
例如，在找零问题中，贪心算法可能会每次都选择最大面额的硬币，而不考虑找零的总数量。这可能导致找零数量过多。
在实际应用中，贪心算法常用于在时间复杂度要求较高或问题规模较大时找到可行的近似解。但在使用贪心算法时，需要仔细分析问题的性质，确保每一步的局部最优选择能够引导到全局最优解。
一个著名的使用贪心算法的例子是背包问题（Knapsack Problem），其中需要选择物品，使它们的总价值最大化，同时满足背包的容量限制。贪心算法在每一步都会选择价值最高的物品放入背包，但并不保证得到最优解。 总的来说，贪心算法是一种简单而直观的算法策略，适用于一些特定类型的问题，但对于复杂问题可能需要其他更高级的算法来找到最优解。
2、贪心算法的历史贪心算法的发展历程如下：
- 起源：贪心算法最早是在1950年代由哈夫曼（Huffman）提出的哈夫曼编码算法。
- 发展：随后，贪心算法在最短路径、最小生成树等问题中得到了广泛的应用。
- 研究：20世纪70年代，贪心算法开始得到系统性的研究，出现了一系列重要的贪心算法，如Dijkstra算法、Prim算法、Kruskal算法等。 - 应用范围扩大：随着计算机技术的不断发展，贪心算法的应用范围也在不断扩大。
3、贪心算法的应用CPU调度算法CPU 调度是一个进程，它允许并同时调度 CPU 中的多个进程，以便最大限度地利用 CPU。
cpu调度算法
这通常发生在一个进程由于资源不可用而处于暂停状态时，为了避免 CPU 时间浪费，我们为该时件安排了一个新进程。
多种算法有助于 CPU 调度，它们利用贪婪方法。这些算法的目的是最大限度地提高 CPU 利用率并最大程度地减少进程执行所需的时间。有多种类型的调度算法：
先到先得
顾名思义，它根据先到先得来安排流程。它是一种非抢占式算法。
最短作业优先
它既是抢占式调度算法，也是非抢占式调度算法。在此算法中，我们以最短的突发时间为进程提供最高优先级。它的抢占式版本称为最短作业优先算法。
优先排期
它既是先发制人的，也是非先发制人的。在这种技术中，我们为每个进程分配优先级，然后按优先级顺序执行。它主要使用优先级队列进行执行。
循环调度
在这个算法中，我们为每个进程分配一个固定的时隙。如果该进程未在该时间段内完全执行，它将在下一轮中完成剩余的执行。它是先发制人的。
多级队列计划
这也是一种基于优先级的算法。它为具有不同优先级的进程维护多个队列。
最小生成树最小生成树是连接的加权无向图的子集，它连接所有顶点，没有周期。在 MST 中，所有边的总重量都是最小的。
Dijkstra 最短路径算法该算法用于查找图中两个顶点之间的最短路径，使边之间的权重之和最小。我们需要最大化或最小化某些东西的所有这些算法都利用了贪婪的方法。
网络路由查找最短路径
内存管理中的拟合算法此算法为操作系统中的进程分配不同的内存块。
在拟合算法中，我们利用指针来跟踪所有可用的内存块。指针还决定是接受还是拒绝任何传入进程的内存块分配请求。它根据三种不同的拟合内存管理算法做出此决定：
首次拟合算法
指针将该内存块分配给它首先发现足以满足该进程的进程。
最佳拟合算法
该算法将最小足够可用的内存块分配给进程。
最差拟合算法
它分配内存中可用的最大足够内存块。
旅行推销员问题
这是贪婪算法解决的标准问题之一。在这个问题中，我们的目标是利用贪婪技术找到最短的路径。目标是只访问每个城市一次，然后返回最初的起点。
小数背包问题
这是一个优化问题。在分数背包问题中，我们尝试从所有可能的物品集中找到一个项目的子集。我们根据问题确保它们的总重量小于或等于给定的限值。我们还确保它们的价值最大化。
4、贪心算法的局限性贪婪方法的工作原理是在算法的每一步都找到最佳结果。这有时会导致结果不准确。
例如，假设我们希望在下图中找到最长的路径：
二叉树
如果我们遵循贪婪的方法，我们将在每个节点上做出最佳选择。在这种情况下，路径将为：12→16→6→35，结果是 69。
然而，实际上，实际最长的路径是 12→4→22→98，结果是 136。在这里，使用贪婪的方法不可能达到 136。在这种情况下，贪婪算法给出了错误的结果。
5、贪心算法举例：Prims算法求解最小生成树算法步骤
初始化最小生成树的顶点。搜索将树连接到新顶点的所有边。找到所有选定边的最小值。将此值添加到树中。递归执行上述步骤以达到最小生成树。举例：举个
理解 Prim 算法中的各个阶段
示例图
1. 选择任意一个随机顶点，在这里说“A”。
2. 从此节点中选择权重最小的边，并将其添加到现有节点中。
3. 选择我们可以包含的最近顶点。
4. 递归重复上述步骤，以获得基于最小生成树的生成树。
生成树的各个阶段如下图所示：
step by step
最终得到的生成树如下图所示：
final result
6、贪心算法 vs 动态规划
贪心算法 vs 动态规划
7、总结贪婪方法是设计算法的最重要技术之一。这主要是因为它有许多实际应用，并且适用于各种各样的问题。
总的来说，贪心算法是一种简单而直观的算法策略，适用于一些特定类型的问题，但对于复杂问题可能需要其他更高级的算法来找到最优解。
继续肝～～～～～～
