算法学习 【第一周】 Ⅲ

算法学习 【第一周】 Ⅲ

一、前言

最近琐事比较多，更新比较慢，请大家见谅！

本期博客我们将学习算法策略之贪心算法的有关基础知识。

二、什么是贪心算法？

贪心算法是遵循在每个阶段做出局部最优选择的问题解决启发式的任何算法。[1]在许多问题中，贪心策略不会产生最优解，但贪心启发式算法可以产生局部最优解，在合理的时间内逼近全局最优解。

例如，旅行商问题（计算复杂度高）的贪心策略是以下启发式的：“在旅程的每一步，访问最近的未访问城市。” 这种启发式并不打算找到最佳解决方案，但它会在合理数量的步骤中终止；为如此复杂的问题找到最佳解决方案通常需要很多不合理的步骤。在数学优化中，贪心算法对具有拟阵性质的组合问题进行优化求解，并对具有子模结构的优化问题给出常数因子近似。

贪心算法无法为许多其他问题产生最佳解决方案，甚至可能产生唯一的最差可能解决方案。一个例子是上面提到的旅行商问题：对于每个城市数量，有一个城市之间的距离分配，最近邻启发式产生唯一的最差可能旅行。

贪心算法在解决问题的策略上"目光短浅”。贪心算法只根据当前信息做出选择，而且一旦做出选择，则不管将来有什么结果，这个选择都不会改变。换言之，贪心算法并不是从整体上做最优考虑，它所做出的选择只是某种意义上的局部最优。在实际应用中，很多问题都可以通过贪心算法得到最优解或最优解的近似解。

三、贪心算法的优缺点

1. 优点
   • 该算法更容易描述
   • 该算法可以比其他算法执行得更好（但并非在所有情况下）
2. 缺点
   • 贪心算法并不总是产生最优解

我们举个例子：

例如，假设我们想在下图中找到从根到叶的最长路径。让我们在这里使用贪心算法。

贪心算法具体步骤：

1. 从根节点20开始。右孩子的体重是3，左孩子的体重是2
2. 我们的问题是找到最大的路径。并且，此时的最优解是3。所以，贪心算法会选择3。
3. 最后一个3的独生子的体重是1。这给了我们最终的结果20 + 3 + 1 = 24。

但是这并不是最佳解决方法，我们还有可以有另一条路径可以得出比贪心算法更长的路径。

20 + 2 + 10 = 32，因此，贪心算法并不总是给出最优/可行的解决方案。

四、贪心选择

贪心选择是指原问题的整体最优解可以通过一系列局部最优的选择得到:先做出当前最优的选择，将原问题变为一个相似却规模更小的子问题，而后的每一步都是当前最优的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。

五、最优子结构

最优子结构是指原问题的最优解包含子问题的最优解。贪心算法通过一系列的局部最优解(子问题的最优解）得到全局最优解（原问题的最优解)，如果原问题的最优解和子问题的最优解没有关系，则求解子问题没有任何意义，无法采用贪心算法。例如，对于原问题S={a1,2，…，ai，…， an}，可以在通过贪心选择得到一个当前最优解{a}之后，转换为求解子问题S-{a分，继续求解该子问题，最后对所有子问题的最优解进行合并，即可得到原问题的最优解，如下图所示：

六、如何创建贪心算法？

贪心算法的求解过程：

• 第 1 步：在给定问题中，找到最佳子结构或子问题。
• 第 2 步：确定解决方案将包括哪些内容（例如，最大和、最短路径）。
• 第 3 步：创建一个遍历所有子问题并创建最佳解决方案的迭代过程。

七、最后我想说

本期博客主要介绍了有关贪心算法的一些基础知识，后续博客我们就会通过一系列的具体问题深入的了解学习一下贪心算法的具体应用。

最后，问大家一个不属于计算机领域的问题：如果我们在生活中也按照贪心算法那样去选择，你觉得会是什么样的呢？