算法：贪婪算法、分而治之

算法：贪婪算法、分而治之

1.贪婪算法

设计算法以实现给定问题的最佳解决方案。在贪婪算法方法中，决策是从给定的解决方案域做出的。由于贪婪，选择了似乎提供最佳解决方案的最接近的解决方案。

贪心算法试图找到一个本地化的最优解决方案，最终可能导致全局优化的解决方案。但是，通常贪婪算法不提供全局优化的解决方案。

计数硬币

这个问题是通过选择最不可能的硬币来计算到期望的值，并且贪婪的方法迫使算法选择最大可能的硬币。如果我们提供₹1,2,5和10的硬币，我们被要求计算₹18，那么贪婪程序将是

• 1 - 选择一个₹10硬币，剩余计数为8
• 2 - 然后选择一个₹5硬币，剩余计数为3
• 3 - 然后选择一个₹2硬币，剩余计数为1
• 4 - 最后，选择一个₹1个硬币可以解决问题

虽然，它似乎工作正常，但这个数量我们只需要选择4个硬币。但是，如果我们稍微改变问题，那么相同的方法可能无法产生相同的最佳结果。

对于货币系统，我们有硬币值为1,7,10的值，计算值为18的硬币绝对是最佳的，但对于15的计数，它可能会使用超过必要的硬币。例如，贪婪的方法将使用10 + 1 + 1 + 1 + 1 + 1，总共6个硬币。而只使用3个硬币(7 + 7 + 1)就可以解决同样的问题

因此，我们可以得出结论，贪婪的方法选择了一个立即优化的解决方案，并且可能在全局优化成为主要问题的地方失败。

实例1

大多数网络算法都使用贪婪的方法。以下是其中一些列表 -

• 旅行推销员问题
• Prim的最小生成树算法
• Kruskal的最小生成树算法
• Dijkstra的最小生成树算法
• 图 - 地图着色
• 图 - 顶点覆盖
• 背包问题
• 作业调度问题

有许多类似的问题使用贪婪的方法来找到最佳解决方案。

2.分而治之

在分而治之的方法中，手头的问题被分成较小的子问题，然后每个问题都独立解决。当我们继续将子问题划分为更小的子问题时，我们最终可能会达到无法进行更多划分的阶段。解决那些“原子”最小可能的子问题(分数)。最后合并所有子问题的解决方案以获得原始问题的解决方案。

从广义上讲，我们可以通过三个步骤来理解 分而治之的 方法。

分割/歇

此步骤涉及将问题分解为更小的子问题。子问题应该代表原始问题的一部分。此步骤通常采用递归方法来划分问题，直到子问题不再可被整除为止。在这个阶段，子问题本质上是原子的，但仍然代表了实际问题的某些部分。

征服/解决

这一步收到了许多较小的子问题需要解决。通常，在这个层面上，问题被认为是自己“解决”的。

合并/合并

当解决较小的子问题时，该阶段递归地组合它们直到它们形成原始问题的解决方案。这种算法方法递归地工作并且征服和合并步骤的工作如此接近以至于它们看起来像一个。

实例2

以下计算机算法基于 分而治之的 编程方法 -

• 合并排序
• 快速排序
• 二进制搜索
• Strassen的矩阵乘法
• 最近的一对(点)

有多种方法可以解决任何计算机问题，但所提到的是分而治之的方法的一个很好的例子。

3.动态规划

动态编程方法类似于将问题分解为更小但更小的子问题的分而治之。但不同的是，分而治之，这些子问题并没有独立解决。相反，记住这些较小子问题的结果并用于类似或重叠的子问题。

动态编程用于我们遇到问题的地方，可以将其划分为类似的子问题，以便可以重复使用它们的结果。大多数情况下，这些算法用于优化。在解决现有子问题之前，动态算法将尝试检查先前解决的子问题的结果。结合子问题的解决方案以实现最佳解决方案。

所以我们可以说 -

• 该问题应该能够分成较小的重叠子问题。
• 通过使用较小子问题的最佳解决方案可以实现最佳解决方案。
• 动态算法使用Memoization。

对照

与解决局部优化的贪婪算法相反，动态算法被激励用于问题的整体优化。

与分而治之的算法相比，其中解决方案被组合以实现整体解决方案，动态算法使用较小子问题的输出，然后尝试优化更大的子问题。动态算法使用Memoization来记住已经解决的子问题的输出。

实例3

使用动态编程方法可以解决以下计算机问题 -

• 斐波纳契数系列
• 背包问题
• 河内塔
• 由Floyd-Warshall完成的所有最短路径
• Dijkstra的最短路径
• 项目安排

动态编程可以自上而下和自下而上的方式使用。当然，大多数情况下，参考之前的解决方案输出比CPU周期重新计算更便宜。

4.基本概念算法

本章介绍与数据结构相关的基本术语。

数据定义

数据定义定义具有以下特征的特定数据。

• 原子 - 定义应该定义一个单一的概念。
• 可追踪 - 定义应该能够映射到某些数据元素。
• 准确 - 定义应该是明确的。
• 清晰简洁 - 定义应该是可以理解的。

数据对象

数据对象表示具有数据的对象。

数据类型

数据类型是对诸如整数，字符串等各种类型的数据进行分类的一种方式，其确定可以与相应类型的数据一起使用的值，可以对相应类型的数据执行的操作的类型。有两种数据类型

• 内置数据类型
• 派生数据类型

内置数据类型

语言具有内置支持的那些数据类型称为内置数据类型。例如，大多数语言提供以下内置数据类型。

• 整型
• 布尔值(true，false)
• 浮动(十进制数)
• 人物和弦乐

派生数据类型

那些可以以一种或另一种方式实现的独立于实现的数据类型称为派生数据类型。这些数据类型通常由主数据类型或内置数据类型以及相关操作的组合构建。例如 -

• 名单
• 排列
• 堆
• 队列

基本操作

数据结构中的数据由某些操作处理。所选择的特定数据结构很大程度上取决于需要对数据结构执行的操作的频率。

• 遍历
• 搜索
• 插入
• 删除
• 排序
• 合并