4.2　理解算法策略

一个精心设计的算法尽可能地将问题划分为更小的子问题，从而最大限度地优化可用资源的使用。设计算法有不同的算法策略，算法策略包含下面列出的三种典型策略，还有些策略没有列入进来。

这里，我们介绍以下三种策略：

  • 分治策略
  • 动态规划策略
  • 贪心算法策略

4.2.1　分治策略

分治策略就是找到一种方法，将规模较大的问题分解成可以相互独立解决的规模较小的子问题，然后将这些子问题产生的解合并起来，生成问题整体的解，这就是所谓的分治策略。

从数学上讲，如果问题（P）有n个输入且需要对数据集d进行处理，则用分治策略为问题设计求解方案会将问题分解成k个子问题，记为P1至Pk，每个子问题将处理数据集d的一个分区。通常，假设P1至Pk依次处理数据分区d1至dk。

我们看一个实例。

实例——适用于Apache Spark的分治策略

Apache Spark是一个用于解决复杂分布式问题的开源框架，它使用了分治策略来解决问题。为了处理问题，它将问题分为多个子问题，并且彼此独立地处理。我们将通过从一个列表中计数单词的简单的例子来说明这一点。

假设我们有以下单词列表：

我们要计算此列表中每个单词出现的频率。为此，我们将采用分治策略来有效解决此问题。

图4-3展示了分治策略的实现流程。

图　4-3

在图4-3中，我们将一个问题划分为以下几个阶段：

  • 分割（splitting）：在这个阶段中，输入数据被分为可以相互独立处理的分区，这称为分割。图4-3中我们有三个分区。
  • 变换（Mapping）：可以在分区上独立运行的任何操作都称为变换。在图4-3中，变换操作将分区中的每个单词转换为键值对，对应于三个分区，有三个并行运行的变换器。
  • 混合（shuffling）：混合是将相似的键组合在一起的过程。一旦相似的键聚集在一起，聚合函数就可以在它们的值上运行。请注意，混合是性能密集型的操作，因为需要将原本分布在网络各处的相似键聚集在一起。
  • 聚合（reducing）：在相似键的值上运行一个聚合函数的操作叫作聚合。在图4-3中，我们要计算每个单词的个数。

我们看看如何通过编写代码来实现此目的。为了演示分治策略，我们需要使用一个分布式的计算框架。为此，我们将在Apache Spark上运行Python：

1. 首先，为了使用Apache Spark，我们创建一个Apache Spark的运行环境：

2. 现在，我们创建一个包含一些单词的示例列表。我们将把这个列表转换成Spark的本地分布式数据结构，称为弹性分布式数据集（Resilient Distributed Dataset，RDD）：

3. 现在，我们使用map函数将单词转换为键值对（如图4-4所示）。

图　4-4

4. 我们使用reduce函数进行聚合，并获得最终结果（如图4-5所示）。

图　4-5

这演示了我们是如何使用分治策略来计算单词出现次数的。

007-1a 诸如Microsoft Azure、Amazon Web Services和Google Cloud之类的现代云计算基础设施通过直接或间接在幕后实施分治策略来实现可扩展性。

4.2.2　动态规划策略

动态规划是由理查德·贝尔曼（Richard Bellman）在20世纪50年代提出的一种用于优化某类算法的策略。它基于智能缓存机制，尝试重用大量计算，这种智能缓存机制称为记忆。

当我们要解决的问题可以拆分为若干子问题时，动态规划可带来良好的性能优势。子问题部分涉及了一些会在不同的子问题中重复的计算，我们的想法是执行一次计算（这是耗时的步骤），然后在其他子问题上重复使用计算结果。这在解决递归问题时尤其有用，因为这些问题可能会多次计算相同的输入。

4.2.3　贪心算法

在深入展开讨论之前，我们先定义两个术语：

  • 算法开销：在我们尝试找出确定型问题的最优解时，都要花费一些时间。随着我们要求解的优化问题变得越来越复杂，找出最优解所花费的时间也会增加。我们用Ωi表示算法开销。
  • 最优解增量：给定的优化问题都存在一个最优解。在通常情况下，我们用自己选择的算法对解迭代地进行优化。对于给定的问题，总是存在当前问题的一个完美解，称为最优解。如前所述，根据待求解问题的类型，最优解有可能是未知的，或者说计算和验证最优解需要花费的时间长到人们无法接受。假设最优解是已知的，那么在第i轮迭代中，当前解与最优解的差称为最优解增量，用∆i表示。

对于复杂问题，我们有两种可行的策略：

  • 策略1：花更多时间寻找最接近最优解的解，使得∆i尽可能小。
  • 策略2：最小化算法开销Ωi，采用快刀斩乱麻的方法，只需使用可行解即可。

贪心算法基于策略2，它并不致力于找出全局最优解，而是选择最小化算法开销。

采用贪心算法是为多阶段问题找出全局最优解的一种快速简单的策略。它基于选择局部最优值而无须费力去验证局部最优值是否也是全局最优的。一般来说，除非我们很幸运，否则贪心算法找到的解不会被当作全局最优解，因为寻找全局最优解通常是一项非常耗时的任务。因此，与分治算法和动态规划算法相比，贪心算法的速度很快。

通常，贪心算法定义如下：

1. 假设我们有一个数据集D。在这个数据集中，选择一个元素k。

2. 假设当前的候选解或可行解为S。考虑在S中包含k，如果可以将它包括进来，则将当前解更新为Union(S, k)。

3. 重复上述过程，直到S被填满或D被用完为止。

上一章目录下一章