当前位置：首页 > news >正文

一文带你理解算法策略

news 来源：原创 2024/5/19 21:10:58

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

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

分治策略

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

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

我们看一个实例。

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

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

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

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

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

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

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

动态规划策略

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

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

贪心算法

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

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