每个程序员都应该知道的 40 个算法（一）（4）

每个程序员都应该知道的 40 个算法（一）（3）https://developer.aliyun.com/article/1506326

插值搜索的性能

如果数据分布不均匀，插值搜索算法的性能将很差。该算法的最坏情况性能为O(N)，如果数据相对均匀，最佳性能为 O(log(log N))。

实际应用

在给定数据存储库中高效准确地搜索数据对许多现实生活应用至关重要。根据您选择的搜索算法，您可能需要首先对数据进行排序。选择正确的排序和搜索算法将取决于数据的类型和大小，以及您试图解决的问题的性质。

让我们尝试使用本章介绍的算法来解决某个国家移民局新申请人与历史记录匹配的问题。当有人申请签证进入该国时，系统会尝试将申请人与现有的历史记录进行匹配。如果至少找到一个匹配项，那么系统会进一步计算个人过去被批准或拒绝的次数。另一方面，如果没有找到匹配项，系统会将申请人分类为新申请人，并为其发放新的标识符。在历史数据中搜索、定位和识别个人的能力对系统至关重要。这些信息很重要，因为如果某人过去曾申请过并且已知申请被拒绝，那么这可能会对该个人当前的申请产生负面影响。同样，如果某人的申请过去已知被批准，那么这个批准可能会增加该个人当前申请获批准的机会。通常，历史数据库将有数百万行数据，我们需要一个精心设计的解决方案来将新申请人与历史数据库进行匹配。

假设数据库中的历史表如下所示：

在这个表中，第一列“个人 ID”与历史数据库中的每个唯一申请人相关联。如果历史数据库中有 3000 万个唯一申请人，那么将有 3000 万个唯一的个人 ID。每个个人 ID 标识历史数据库系统中的一个申请人。

第二列是“申请 ID”。每个申请 ID 标识系统中的一个唯一申请。一个人过去可能申请过多次。这意味着在历史数据库中，我们将有比个人 ID 更多的唯一申请 ID。如上表所示，约翰·多只有一个个人 ID，但有两个申请 ID。

上表仅显示了历史数据集的一部分样本。假设我们的历史数据集中有接近 100 万行数据，其中包含过去 10 年申请人的记录。新申请人以每分钟约 2 人的平均速度持续到达。对于每个申请人，我们需要执行以下操作：

• 为申请人发放新的申请 ID。
  
• 查看历史数据库中是否有与申请人匹配的记录。
  
• 如果找到匹配项，则使用历史数据库中找到的个人 ID。我们还需要确定在历史数据库中申请已被批准或拒绝的次数。
  
• 如果没有找到匹配项，那么我们需要为该个人发放新的个人 ID。
  

假设一个新的人员带着以下的证件到达：

• “名字”： “约翰”
  
• 姓氏：多
  
• 出生日期：2000-09-19
  

现在，我们如何设计一个能够执行高效和具有成本效益的搜索的应用程序呢？

搜索数据库中新申请的一个策略可以设计如下：

• 按出生日期对历史数据库进行排序。
  
• 每次有新人到来时，都要为申请人发放新的申请 ID。
  
• 获取所有与该出生日期匹配的记录。这将是主要搜索。
  
• 在出现匹配项的记录中，使用名字和姓氏进行次要搜索。
  
• 如果找到匹配项，请使用个人 ID来引用申请人。计算批准和拒绝的次数。
  
• 如果找不到匹配项，请为申请人发放新的个人 ID。
  

让我们尝试选择正确的算法来对历史数据库进行排序。我们可以安全地排除冒泡排序，因为数据量很大。希尔排序将表现更好，但仅当我们有部分排序的列表时。因此，归并排序可能是对历史数据库进行排序的最佳选择。

当有新人到来时，我们需要在历史数据库中定位并搜索该人。由于数据已经排序，可以使用插值搜索或二分搜索。因为申请人可能根据出生日期均匀分布，所以可以安全地使用二分搜索。

最初，我们基于出生日期进行搜索，这将返回一组共享相同出生日期的申请人。现在，我们需要在共享相同出生日期的小子集中找到所需的人。由于我们已成功将数据减少到一个小子集，任何搜索算法，包括冒泡排序，都可以用于搜索申请人。请注意，我们在这里稍微简化了次要搜索问题。如果找到多个匹配项，我们还需要通过汇总搜索结果来计算批准和拒绝的总数。

在现实场景中，每个个体都需要在次要搜索中使用一些模糊搜索算法进行识别，因为名字可能拼写略有不同。搜索可能需要使用某种距离算法来实现模糊搜索，其中相似度高于定义的阈值的数据点被视为相同。

总结

在本章中，我们介绍了一组排序和搜索算法。我们还讨论了不同排序和搜索算法的优缺点。我们量化了这些算法的性能，并学会了何时使用每个算法。

在下一章中，我们将学习动态算法。我们还将研究设计算法的实际示例以及页面排名算法的细节。最后，我们将学习线性规划算法。

第四章：设计算法

本章介绍了各种算法的核心设计概念。它讨论了设计算法的各种技术的优缺点。通过理解这些概念，您将学会如何设计高效的算法。

本章首先讨论了在设计算法时可用的不同选择。然后，它讨论了表征我们试图解决的特定问题的重要性。接下来，它以著名的“旅行推销员问题”（TSP）为案例，并应用我们将要介绍的不同设计技术。然后，它介绍了线性规划并讨论了其应用。最后，它介绍了线性规划如何用于解决现实世界问题。

通过本章结束时，您应该能够理解设计高效算法的基本概念。

本章讨论了以下概念：

• 设计算法的各种方法
  
• 了解选择算法正确设计所涉及的权衡
  
• 制定现实世界问题的最佳实践
  
• 解决现实世界的优化问题
  

让我们首先看一下设计算法的基本概念。

介绍设计算法的基本概念

根据美国传统词典的定义，算法如下：

“一组有限的明确指令，给定一些初始条件，可以按照规定的顺序执行，以实现特定目标，并具有可识别的一组结束条件。”

设计算法是为了以最有效的方式提出这个“一组有限的明确指令”来“实现特定目标”。对于一个复杂的现实世界问题，设计算法是一项繁琐的任务。为了提出一个良好的设计，我们首先需要充分了解我们试图解决的问题。我们首先需要弄清楚需要做什么（即了解需求）然后再看如何做（即设计算法）。了解问题包括解决问题的功能和非功能性需求。让我们看看这些是什么：

• 功能性需求正式指定了我们要解决的问题的输入和输出接口以及与之相关的功能。功能性需求帮助我们理解数据处理、数据操作和需要实施的计算，以生成结果。
  
• 非功能性需求设置了算法性能和安全方面的期望。
  

请注意，设计算法是在给定一组情况下以最佳方式解决功能和非功能性需求，并考虑到运行设计算法的可用资源。

为了提出一个能够满足功能和非功能需求的良好响应，我们的设计应该尊重以下三个关注点，如第一章《算法概述》中所讨论的：

• 关注点 1：设计的算法是否能产生我们期望的结果？
  
• 关注点 2：这是否是获得这些结果的最佳方式？
  
• 关注点 3：算法在更大数据集上的表现如何？
  

在本节中，让我们逐一看看这些关注点。

关注点 1 - 设计的算法是否能产生我们期望的结果？

算法是对现实世界问题的数学解决方案。为了有用，它应该产生准确的结果。如何验证算法的正确性不应该是事后想到的事情；相反，它应该融入到算法的设计中。在制定如何验证算法之前，我们需要考虑以下两个方面：

• 定义真相：为了验证算法，我们需要一些已知的给定输入的正确结果。在我们试图解决的问题的上下文中，这些已知的正确结果被称为真相。真相很重要，因为在我们迭代地努力将算法演变为更好的解决方案时，它被用作参考。
  
• 选择度量标准：我们还需要考虑如何量化与定义真相的偏差。选择正确的度量标准将帮助我们准确量化算法的质量。
  

例如，对于机器学习算法，我们可以使用现有的标记数据作为真相。我们可以选择一个或多个度量标准，如准确度、召回率或精确度，来量化与真相的偏差。需要注意的是，在某些用例中，正确的输出不是一个单一的值。相反，正确的输出被定义为给定一组输入的范围。在设计和开发算法时，目标是迭代改进算法，直到它在需求中指定的范围内。

关注点 2 - 这是获得这些结果的最佳方式吗？

第二个关注点是找到以下问题的答案：

这是最佳解决方案吗？我们能验证不存在比我们的解决方案更好的解决方案吗？

乍一看，这个问题看起来很简单。然而，对于某类算法，研究人员已经花费了数十年的时间，试图验证算法生成的特定解决方案是否也是最佳解决方案，以及是否存在其他解决方案可以给出更好的结果。因此，首先了解问题、其需求和可用于运行算法的资源是很重要的。我们需要承认以下声明：

我们应该努力寻找这个问题的最佳解决方案吗？找到并验证最佳解决方案是如此耗时和复杂，以至于基于启发式的可行解决方案是我们最好的选择。

因此，理解问题及其复杂性是重要的，有助于我们估计资源需求。

在我们深入研究之前，首先让我们定义这里的一些术语：

• 多项式算法：如果一个算法的时间复杂度为O(n**^k )，我们称之为多项式算法，其中k是一个常数。
  
• 证书：在迭代结束时产生的候选解决方案被称为证书。当我们迭代解决特定问题时，我们通常会生成一系列证书。如果解决方案朝着收敛前进，每个生成的证书都会比前一个更好。在某个时刻，当我们的证书满足要求时，我们将选择该证书作为最终解决方案。
  

在第一章《算法概述》中，我们介绍了大 O 符号，它可以用来分析算法的时间复杂度。在分析时间复杂度的上下文中，我们关注以下不同的时间间隔：

• 算法产生提议解决方案（证书）所需的时间，称为证书(t[r])
  
• 验证提议解决方案（证书）所需的时间，t[s]
  

表征问题的复杂性

多年来，研究界根据问题的复杂性将问题分为各种类别。在尝试设计解决方案之前，首先尝试对问题进行表征是有意义的。一般来说，问题有三种类型：

• 类型 1：我们可以保证存在一个多项式算法来解决这些问题
  
• 类型 2：我们可以证明它们不能通过多项式算法解决的问题
  
• 类型 3：我们无法找到多项式算法来解决这些问题，但也无法证明这些问题不存在多项式解决方案
  

让我们来看看各种问题类别：

• 非确定性多项式（NP）：要成为 NP 问题，问题必须满足以下条件：
  
• 可以保证存在一个多项式算法，可用于验证候选解决方案（证书）是否最优。
  
• 多项式（P）：这些问题可以被视为 NP 的子集。除了满足 NP 问题的条件外，P 问题还需要满足另一个条件：
  
• 可以保证至少存在一个多项式算法可用于解决它们。
  

P和NP问题之间的关系如下图所示：

如果一个问题是 NP，那么它也是 P 吗？这是计算机科学中仍未解决的最大问题之一。由 Clay 数学研究所选定的千禧年大奖问题宣布为解决此问题提供 100 万美元奖金，因为它将对人工智能、密码学和理论计算机科学等领域产生重大影响：

让我们继续列举各种问题类别：

• NP 完全：NP 完全类别包含所有 NP 问题中最难的问题。NP 完全问题满足以下两个条件：
  
• 没有已知的多项式算法来生成证书。
  
• 已知有多项式算法可以验证所提出的证书是否最优。
  
• NP 难：NP 难类别包含至少与 NP 类别中的任何问题一样困难的问题，但它们本身不需要属于 NP 类别。
  

现在，让我们尝试绘制一个图表来说明这些不同的问题类别：

请注意，研究界尚未证明 P = NP。尽管尚未证明，但极有可能 P ≠ NP。在这种情况下，NP 完全问题不存在多项式解。请注意，前面的图表是基于这一假设的。

问题 3 - 算法在更大的数据集上的表现如何？

算法以一定方式处理数据以产生结果。一般来说，随着数据规模的增加，处理数据和计算所需结果的时间也会越来越长。术语“大数据”有时用于粗略识别预计对基础设施和算法工作具有挑战性的数据集，因为它们的规模、多样性和速度。设计良好的算法应该是可扩展的，这意味着它应该以一种能够有效运行的方式设计，利用可用资源并在合理的时间内生成正确的结果。在处理大数据时，算法的设计变得更加重要。为了量化算法的可扩展性，我们需要牢记以下两个方面：

• 随着输入数据增加，资源需求的增加：估算这样的需求称为空间复杂性分析。
  
• 随着输入数据增加，运行所需时间的增加：估算这一点称为时间复杂性分析。
  

请注意，我们生活在一个被数据爆炸所定义的时代。术语“大数据”已经成为主流，因为它捕捉到了现代算法通常需要处理的数据的规模和复杂性。

在开发和测试阶段，许多算法只使用少量数据样本。在设计算法时，重要的是要考虑算法的可扩展性方面。特别重要的是要仔细分析（即测试或预测）算法在数据集增大时的性能影响。

理解算法策略

一个精心设计的算法试图通过尽可能将问题分解为更小的子问题，以最有效地优化可用资源的使用。设计算法有不同的算法策略。算法策略涉及算法列表中包含缺失算法的三个方面。

本节中我们将介绍以下三种策略：

• 分而治之策略
  
• 动态规划策略
  
• 贪婪算法策略
  

理解分而治之策略

其中一种策略是找到一种方法将一个较大的问题分解为可以独立解决的较小问题。这些子问题产生的子解决方案然后组合在一起生成问题的整体解决方案。这就是分而治之策略。

从数学上讲，如果我们正在为一个需要处理数据集d的n个输入的问题（P）设计解决方案，我们将问题分解为k个子问题，P[1]到P[k]。每个子问题将处理数据集d的一个分区。通常，我们将有P**[1]到P**[k]处理d[1]到d[k]。

让我们看一个实际的例子。

实际例子 - 将分而治之应用于 Apache Spark

Apache Spark 是一个用于解决复杂分布式问题的开源框架。它实现了分而治之的策略来解决问题。为了处理问题，它将问题分解为各种子问题，并独立处理它们。我们将通过使用一个简单的例子来演示这一点，从一个列表中计算单词的数量。

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

wordsList = [python, java, ottawa, news, java, ottawa]

我们想要计算列表中每个单词的频率。为此，我们将应用分而治之策略以高效地解决这个问题。

分而治之的实现如下图所示：

前面的图显示了问题被分解为以下阶段：

1. 分割：输入数据被分成可以独立处理的分区。这就是分割。在前面的图中我们有三个分割。
   
2. 映射：任何可以在分割上独立运行的操作都称为映射。在前面的图中，映射操作将分区中的每个单词转换为键值对。对应于三个分割，有三个并行运行的映射器。
   
3. 洗牌：洗牌是将相似的键放在一起的过程。一旦相似的键放在一起，聚合函数就可以对它们的值进行运算。请注意，洗牌是一个性能密集型的操作，因为需要将最初分布在网络中的相似键放在一起。
   
4. 减少：对相似键的值运行聚合函数称为减少。在前面的图中，我们需要计算单词的数量。
   

让我们看看如何编写代码来实现这一点。为了演示分而治之的策略，我们需要一个分布式计算框架。我们将在 Apache Spark 上运行 Python：

1. 首先，为了使用 Apache Spark，我们将创建一个 Apache Spark 的运行时上下文：

import findspark
findspark.init()
from pyspark.sql import SparkSession
spark = SparkSession.builder.master("local[*]").getOrCreate()
sc = spark.sparkContext

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

wordsList = ['python', 'java', 'ottawa', 'ottawa', 'java','news']
wordsRDD = sc.parallelize(wordsList, 4)
# Print out the type of wordsRDD
print (wordsRDD.collect())

1. 现在，让我们使用map函数将单词转换为键值对：

1. 让我们使用reduce函数来聚合并得到最终结果：

这显示了我们如何使用分而治之策略来计算单词的数量。

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

理解动态规划策略

动态规划是理查德·贝尔曼在 1950 年代提出的一种优化某些类别算法的策略。它基于一种智能缓存机制，试图重复使用繁重的计算。这种智能缓存机制称为记忆化。

当我们试图解决的问题可以分解为子问题时，动态规划可以带来良好的性能优势。这些子问题部分涉及在这些子问题中重复的计算。其思想是执行该计算一次（这是耗时的步骤），然后在其他子问题中重复使用它。这是通过记忆化实现的，特别适用于解决可能多次评估相同输入的递归问题。

理解贪婪算法

在深入研究本节内容之前，让我们先定义两个术语：

• 算法开销：每当我们尝试找到某个问题的最优解时，都需要一些时间。随着我们试图优化的问题变得越来越复杂，找到最优解所需的时间也会增加。我们用*Ω[i]*表示算法开销。
  
• 与最优解的差异：对于给定的优化问题，存在一个最优解。通常，我们使用我们选择的算法迭代优化解决方案。对于给定的问题，总是存在一个完美的解决方案，称为最优解。正如讨论的那样，根据我们试图解决的问题的分类，最优解可能是未知的，或者计算和验证它可能需要不合理的时间。假设最优解已知，则在第i次迭代中，当前解决方案与最优解的差异称为与最优解的差异，用*Δ[i]*表示。
  

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

• **策略 1：**花费更多时间找到最接近最优解的解决方案，使Δ[i]尽可能小。
  
• **策略 2：**最小化算法开销Ω[i]。使用快速且简单的方法，只使用可行的解决方案。
  

贪婪算法是基于策略 2 的，我们不会努力寻找全局最优解，而是选择最小化算法开销。

使用贪婪算法是一种快速简单的策略，用于找到多阶段问题的全局最优值。它基于选择局部最优值，而不努力验证局部最优值是否也是全局最优值。一般来说，除非我们很幸运，贪婪算法不会得到可以被认为是全局最优的值。然而，找到全局最优值是一项耗时的任务。因此，与分而治之和动态规划算法相比，贪婪算法更快。

一般来说，贪婪算法定义如下：

1. 假设我们有一个数据集D。在这个数据集中，选择一个元素k。
   
2. 假设候选解或证书是S。考虑将k包含在解决方案S中。如果可以包含，那么解决方案就是Union(S, e)。
   
3. 重复这个过程，直到S填满或D用尽。
   

实际应用-解决 TSP

让我们首先看一下 TSP 的问题陈述，这是一个在上世纪 30 年代被提出的众所周知的问题。TSP 是一个 NP 难问题。首先，我们可以随机生成一个满足访问所有城市条件的旅行路线，而不考虑最优解。然后，我们可以努力改进每次迭代的解决方案。迭代中生成的每个旅行路线称为候选解（也称为证书）。证明证书是最优的需要指数级增加的时间。相反，使用基于不同启发式的解决方案，这些解决方案生成的旅行路线接近于最优但并非最优。

旅行商需要访问给定的城市列表才能完成他们的工作：

注意以下内容：

• 列表中的城市之间的距离是已知的，
  
• 给定列表中的每个城市都需要被访问一次。
  

我们能为销售员生成旅行计划吗？什么是可以最小化旅行商所走总距离的最优解？

以下是五个加拿大城市之间的距离，我们可以用于 TSP：

请注意，目标是获得一个从初始城市出发并返回到初始城市的旅行路线。例如，一个典型的旅行路线可以是 Ottawa–Sudbury–Montreal–Kingston–Toronto–Ottawa，成本为484 + 680 + 287 + 263 + 450 = 2,164。这是销售员需要旅行的最短距离吗？什么是可以最小化旅行商所走总距离的最优解？我将留给你去思考和计算。

使用蛮力策略

解决 TSP 的第一个解决方案是使用蛮力策略找到销售员访问每个城市一次并返回到初始城市的最短路径。因此，蛮力策略的工作方式如下：

1. 评估所有可能的旅行路线。
   
2. 选择一个我们可以得到最短距离的方案。
   

问题在于对于n个城市，存在*(n-1)!种可能的旅行路线。这意味着五个城市将产生4! = 24*种旅行路线，我们将选择对应最短距离的那个。很明显，这种方法只适用于我们没有太多城市的情况。随着城市数量的增加，蛮力策略由于生成的排列数量庞大而变得不稳定。

让我们看看如何在 Python 中实现蛮力策略。

首先，注意到一个旅行路线{1,2,3}表示从城市 1 到城市 2 和城市 3 的旅行路线。旅行路线中的总距离是旅行路线中覆盖的总距离。我们将假设城市之间的距离是它们之间的最短距离（即欧几里得距离）。

让我们首先定义三个实用函数：

• distance_points：计算两点之间的绝对距离
  
• distance_tour：计算销售员在给定旅行中需要覆盖的总距离
  
• generate_cities：随机生成一个位于宽度为500，高度为300的矩形内的n个城市的集合
  

让我们看一下以下代码：

import random
from itertools import permutations
alltours = permutations 
def distance_tour(aTour):
    return sum(distance_points(aTour[i - 1], aTour[i]) 
               for i in range(len(aTour)))
aCity = complex
def distance_points(first, second): return abs(first - second)
def generate_cities (number_of_cities):
    seed=111;width=500;height=300
    random.seed((number_of_cities, seed))
    return frozenset(aCity(random.randint(1, width), random.randint(1, height))
                     for c in range(number_of_cities))

在上面的代码中，我们从itertools包的permutations函数实现了alltours。我们还用复数表示了距离。这意味着：

• 计算两个城市a和b之间的距离就是简单的distance (a,b)，
  
• 我们可以通过调用generate_cities(n)来创建n个城市。
  

现在让我们定义一个名为brute_force的函数，它生成所有可能的城市旅游路线。一旦生成了所有可能的路线，它将选择最短距离的路线：

def brute_force(cities):
    "Generate all possible tours of the cities and choose the shortest 
     tour."
    return shortest_tour(alltours(cities))
def shortest_tour(tours): return min(tours, key=distance_tour)

现在让我们定义一些实用函数，可以帮助我们绘制城市。我们将定义以下函数：

• visualize_tour：绘制特定旅游路线中的所有城市和链接。它还会突出显示旅游路线的起始城市。
  
• visualize_segment：由visualize_tour使用，用于绘制路段中的城市和链接。
  

看看以下代码：

%matplotlib inline
import matplotlib.pyplot as plt
def visualize_tour(tour, style='bo-'): 
    if len(tour) > 1000: plt.figure(figsize=(15, 10))
    start = tour[0:1]
    visualize_segment(tour + start, style)
    visualize_segment(start, 'rD') 
def visualize_segment (segment, style='bo-'):
    plt.plot([X(c) for c in segment], [Y(c) for c in segment], style, clip_on=False)
    plt.axis('scaled')
    plt.axis('off')
def X(city): "X axis"; return city.real
def Y(city): "Y axis"; return city.imag

让我们实现一个名为tsp()的函数，它可以执行以下操作：

1. 根据算法和请求的城市数量生成旅游路线
   
2. 计算算法运行所花费的时间
   
3. 生成一个图
   

一旦定义了tsp()，我们就可以使用它来创建一条旅游路线：

请注意，我们已经用它来为 10 个城市生成旅游路线。当n=10 时，它将生成*(10-1)! = 362,880个可能的排列。如果n*增加，排列的数量会急剧增加，而暴力方法无法使用。

使用贪婪算法

如果我们使用贪婪算法来解决 TSP 问题，那么在每一步，我们可以选择一个看起来合理的城市，而不是找到一个可以得到最佳整体路径的城市。因此，每当我们需要选择一个城市时，我们只需选择最近的城市，而不必验证这个选择是否会得到全局最优路径。

贪婪算法的方法很简单：

1. 从任何城市开始。
   
2. 在每一步中，通过移动到尚未访问过的最近邻居的城市来构建旅游路线。
   
3. 重复步骤 2。
   

让我们定义一个名为greedy_algorithm的函数，可以实现这个逻辑：

def greedy_algorithm(cities, start=None):
    C = start or first(cities)
    tour = [C]
    unvisited = set(cities - {C})
    while unvisited:
        C = nearest_neighbor(C, unvisited)
        tour.append(C)
        unvisited.remove(C)
    return tour
def first(collection): return next(iter(collection))
def nearest_neighbor(A, cities):
    return min(cities, key=lambda C: distance_points(C, A))

现在，让我们使用greedy_algorithm为 2,000 个城市创建一条旅游路线：

请注意，生成 2,000 个城市的旅游路线只花了 0.514 秒。如果我们使用了暴力方法，它将生成*(2000-1)!*个排列，几乎是无穷大。

请注意，贪婪算法是基于启发式的，没有证据表明解决方案将是最优的。

现在，让我们来看看 PageRank 算法的设计。

介绍 PageRank 算法

作为一个实际的例子，让我们来看看 PageRank 算法，最初被谷歌用来对用户查询的搜索结果进行排名。它生成一个数字，量化了搜索结果在用户执行的查询上下文中的重要性。这是由斯坦福大学的两位博士生拉里·佩奇和谢尔盖·布林在 20 世纪 90 年代末设计的，他们后来创办了谷歌。

PageRank 算法是以拉里·佩奇的名字命名的，他在斯坦福大学与谢尔盖·布林一起创建了它。

让我们首先正式定义 PageRank 最初设计的问题。

问题定义

每当用户在网络上的搜索引擎上输入查询时，通常会得到大量的结果。为了使结果对最终用户有用，重要的是使用某些标准对网页进行排名。显示的结果使用这个排名来总结用户的结果，并且依赖于底层算法定义的标准。

实现 PageRank 算法

PageRank 算法最重要的部分是找到计算每个页面重要性的最佳方法。为了计算一个从0到1的数字，可以量化特定页面的重要性，该算法结合了以下两个组件的信息：

• 用户输入的查询特定信息：这个组件估计了用户输入的查询的上下文中，网页内容的相关性。页面的内容直接取决于页面的作者。
  
• 与用户输入的查询无关的信息：这个组件试图量化每个网页在其链接、浏览和邻域的重要性。这个组件很难计算，因为网页是异质的，而且很难制定可以应用于整个网络的标准。
  

为了在 Python 中实现 PageRank 算法，首先让我们导入必要的库：

import numpy as np import networkx as nx import matplotlib.pyplot as plt %matplotlib inline

为了演示的目的，让我们假设我们只分析网络中的五个网页。让我们称这组页面为myPages，它们一起在一个名为myWeb的网络中：

myWeb = nx.DiGraph() myPages = range(1,5)

现在，让我们随机连接它们以模拟实际网络：

connections = [(1,3),(2,1),(2,3),(3,1),(3,2),(3,4),(4,5),(5,1),(5,4)] myWeb.add_nodes_from(myPages) myWeb.add_edges_from(connections)

现在，让我们绘制这个图：

pos=nx.shell_layout(myWeb) nx.draw(myWeb, pos, arrows=True, with_labels=True) plt.show()

它创建了我们网络的可视表示，如下所示：

在 PageRank 算法中，网页的模式包含在一个称为转换矩阵的矩阵中。有一些算法不断更新转换矩阵，以捕捉不断变化的网络状态。转换矩阵的大小是n x n，其中n是节点的数量。矩阵中的数字是访问者由于出站链接而下一个转到该链接的概率。

在我们的情况下，上面的图显示了我们拥有的静态网络。让我们定义一个函数，用于创建转换矩阵：

请注意，这个函数将返回G，它代表我们图的转换矩阵。

让我们为我们的图生成转换矩阵：

请注意，我们图的转换矩阵是5 x 5。每一列对应图中的每个节点。例如，第 2 列是关于第二个节点的。访问者从节点 2 导航到节点 1 或节点 3 的概率为 0.5。请注意，转换矩阵的对角线是0，因为在我们的图中，节点没有到自身的出站链接。在实际网络中，这可能是可能的。

请注意，转换矩阵是一个稀疏矩阵。随着节点数量的增加，大多数值将为0。

理解线性规划

线性规划背后的基本算法是由乔治·丹齐格在 1940 年代初在加州大学伯克利分校开发的。丹齐格在为美国空军工作时，利用这个概念进行了物流供应和容量规划的实验。二战结束后，丹齐格开始为五角大楼工作，并将他的算法成熟为一种他称之为线性规划的技术。它被用于军事作战规划。

今天，它被用来解决与根据某些约束最小化或最大化变量相关的重要现实问题。这些问题的一些例子如下：

• 根据资源最小化修理汽车的时间
  
• 在分布式计算环境中分配可用的分布式资源以最小化响应时间
  
• 根据公司内资源的最佳分配来最大化公司的利润
  

制定线性规划问题

使用线性规划的条件如下：

• 我们应该能够通过一组方程来阐明问题。
  
• 方程中使用的变量必须是线性的。
  

定义目标函数

请注意，前面三个例子的目标都是关于最小化或最大化一个变量。这个目标在数学上被公式化为其他变量的线性函数，并被称为目标函数。线性规划问题的目标是在保持指定约束条件的情况下最小化或最大化目标函数。

指定约束条件

在尝试最小化或最大化某些东西时，现实世界中存在一些需要遵守的约束。例如，当试图最小化修理汽车所需的时间时，我们还需要考虑到可用的技工数量是有限的。通过线性方程指定每个约束是制定线性规划问题的重要部分。

线性规划的实际应用-容量规划

让我们看一个实际应用案例，线性规划可以用来解决一个现实世界的问题。假设我们想要最大化一家制造两种不同类型机器人的尖端工厂的利润：

• 高级模型（A）：这提供了完整的功能。制造每个高级模型的单位都会带来 4200 美元的利润。
  
• 基本模型（B）：这只提供基本功能。制造每个基本模型的单位都会带来 2800 美元的利润。
  

制造机器人需要三种不同类型的人。制造每种类型机器人所需的确切天数如下：

工厂以 30 天为周期运行。一个 AI 专家在一个周期内可用 30 天。两名工程师在 30 天内休假 8 天。因此，工程师在一个周期内只有 22 天可用。一个技术员在 30 天周期内可用 20 天。

以下表格显示了工厂中我们拥有的人数：

这可以建模如下：

• 最大利润= 4200A + 2800B
  
• 这取决于以下内容：
  
• A ≥ 0：生产的高级机器人数量可以是0或更多。
  
• B ≥ 0：生产的基本机器人数量可以是0或更多。
  
• 3A + 2B ≤ 20：这是技术员可用性的约束。
  
• 4A+3B ≤ 30：这是 AI 专家可用性的约束。
  
• 4A+ 3B ≤ 44：这是工程师可用性的约束。
  

首先，我们导入名为pulp的 Python 包，用于实现线性规划：

import pulp

然后，我们在这个包中调用LpProblem函数来实例化问题类。我们将实例命名为利润最大化问题：

# Instantiate our problem class
model = pulp.LpProblem("Profit maximising problem", pulp.LpMaximize)

然后，我们定义两个线性变量，A和B。变量A表示生产的高级机器人数量，变量B表示生产的基本机器人数量：

A = pulp.LpVariable('A', lowBound=0, cat='Integer') 
B = pulp.LpVariable('B', lowBound=0, cat='Integer')

我们将目标函数和约束定义如下：

# Objective function
model += 5000 * A + 2500 * B, "Profit"
# Constraints
model += 3 * A + 2 * B <= 20 
model += 4 * A + 3 * B <= 30
model += 4 * A + 3 * B <= 44

我们使用solve函数生成解决方案：

# Solve our problem
model.solve()
pulp.LpStatus[model.status]

然后，我们打印A和B的值以及目标函数的值：

线性规划在制造业中被广泛使用，以找到应该使用的产品的最佳数量，以优化可用资源的使用。

现在我们来到了本章的结尾！让我们总结一下我们学到了什么。

摘要

在本章中，我们看了各种设计算法的方法。我们看了选择正确的算法设计所涉及的权衡。我们看了制定现实世界问题的最佳实践。我们还看了如何解决现实世界的优化问题。从本章中学到的经验可以用来实现设计良好的算法。

在下一章中，我们将专注于基于图的算法。我们将首先研究表示图的不同方法。然后，我们将研究建立在各种数据点周围进行特定调查的技术。最后，我们将研究从图中搜索信息的最佳方法。