算法基础¶

我们知道，一个程序由两部分组成：数据和算法。数据是程序处理的对象，而算法则是处理数据的步骤和方法。算法在计算机科学中占据着核心地位，因为它们决定了程序的效率和性能。在本章中，我们将介绍算法的基本概念、分类以及常见的算法设计技巧。

算法及算法分析的基本概念¶

算法，简单地说就是一套方法或步骤，用于解决特定的问题。而在计算机上的算法，往往也有一种特殊的性质，即它们必须是可计算的（computable），也就是说，一个好的算法必须满足两个条件： - 有穷性（Finiteness）：算法必须在有限的步骤内完成，不能无限循环。 - 确定性（Definiteness）：算法的每一步都必须是明确的，没有歧义。 实际上，很多算法实际上是无限终止的，例如遗传算法、模拟退火等。这些时候，我们往往会设置一个终止条件，例如达到一定的迭代次数或满足某个精度要求。但无论如何，这些算法在实际运行中都必须在有限时间内终止，否则就无法称之为一个好的算法。

衡量算法的效率¶

对于同一组数据，不同的算法往往会在不同的时间内完成任务。例如，我们要在一堆有序的数据中找到某个数值（不保证该数值一定在表中存在），我提出以下两种方法： - 方法一：从头到尾依次检查每个数值，直到找到目标数值为止（线性查找）。在C++中，该查找方式是std::find。 - 方法二：先和表里的中间数值比较，如果目标数值较小，则继续在前半部分查找，否则在后半部分查找。重复这个过程，直到找到目标数值为止（二分查找）。在C++中，该查找方式是std::binary_search。 假设我们有n个数据。那么，我们可以列出一个表格，来比较这两种方法在不同数据规模下需要的比较次数：

我们发现，算法的不同会导致程序比较的次数有一些差异。为了更好地描述算法的效率，我们引入以下两个定义：

定义（时间复杂度）：时间复杂度（Time Complexity）是指算法在执行过程中所需的时间与输入数据规模之间的关系。

定义（空间复杂度）：空间复杂度（Space Complexity）是指算法在执行过程中所需的存储空间与输入数据规模之间的关系。

而在实际表示中，有五种方法来描述算法的时间/空间复杂度，分别为： - 大O符号（Big O Notation）：假设算法在数据规模为\(n\)的时候所需要的时间为\(T(n)\)，如果存在正常数\(c>0\)和\(n_0>0\)，使得对于所有\(n \ge n_0\)都有\(T(n) \le c \cdot f(n)\)，那么我们就说算法的时间复杂度为\(O(f(n))\)。 - 大\(\Omega\)符号（Big Omega Notation）：如果存在正常数\(c>0\)和\(n_0>0\)，使得对于所有\(n \ge n_0\)都有\(T(n) \ge c \cdot f(n)\)，那么我们就说算法的时间复杂度为\(\Omega(f(n))\)。 - 大\(\Theta\)符号（Big Theta Notation）：如果算法的时间复杂度同时满足\(O(f(n))\)和\(\Omega(f(n))\)，那么我们就说算法的时间复杂度为\(\Theta(f(n))\)。该符号也叫做“同阶”符号，表示算法的时间复杂度与\(f(n)\)在数量级上是相同的。 - 小o符号（Small o Notation）：如果对于所有正常数\(c>0\)，都存在\(n_0>0\)，使得对于所有\(n \ge n_0\)都有\(T(n) < c \cdot f(n)\)，那么我们就说算法的时间复杂度为\(o(f(n))\)。 - 小\(\omega\)符号（Small omega Notation）：如果对于所有正常数\(c>0\)，都存在\(n_0>0\)，使得对于所有\(n \ge n_0\)都有\(T(n) > c \cdot f(n)\)，那么我们就说算法的时间复杂度为\(\omega(f(n))\)。 在上述做法中，又属大O符号和大\(\Theta\)符号最为常用。空间复杂度的表示类似，这里不再赘述。

常规情况下，我们会尽量使描述算法复杂度的辅助函数\(f(n)\)尽可能地简单，也就是往往仅保留最“决定性”的一项。例如，假设一个算法的时间复杂度为\(T(n) = 3n^3 + 5n^2 + 2n + 8\)，那么我们可以说该算法的时间复杂度为\(O(n^3)\)，因为当\(n\)足够大时，\(n^3\)项会主导整个函数的增长。而更简单起见，我们往往有一个“链条”，即 $\(O(1) \subset O(\log n) \subset O(n) \subset O(n \log n) \subset O(n^2) \subset O(2^n) \subset O(n!)\)$ 来表示不同复杂度的增长速度。

问题的复杂性及其初步判断¶

而问题的复杂性则是指解决某个问题所需的资源（时间和空间）与输入数据规模之间的关系。问题的复杂性和算法的复杂度密切相关却不完全相同：复杂度仅用来衡量某一个具体的算法的效率，而一个问题往往有较多算法来解决，问题的“复杂性”则是指所有可能的算法中，最优算法的复杂度。

我们举一个例子：在一些无序的数中，试着找到一个最大值。怎样确定该问题的复杂性呢？我们可以考虑所有可能的算法，发现无论采用何种方法，都至少需要检查每个数值一次，才能确保找到最大值。因此，该问题的复杂性为\(O(n)\)。

实际上很多问题无法通过简单的分析来判断其复杂性。但对于一些简单的问题，判断复杂性可以辅助检查算法的正确性。例如，排序问题的复杂性下界为\(O(n \log n)\)，因此如果我们设计了一个排序算法，其时间复杂度为\(O(n^2)\)，那么我们就可以断定该算法不是最优的。

而NP问题则是指那些可以在多项式时间内由非确定性图灵机[^2]解决的问题。换句话说，如果一个问题属于NP类，那么“验证该问题的一个给定解是正确的”是可以在多项式时间内完成的，或者说是一个P问题。

目前已经知道，**所有的P问题都一定是NP问题**，也就是$\text{P} \subseteq \text{NP}$。但是否$\text{P} = \text{NP}$则是一个未解问题，且被认为是计算机科学中最重要的未解问题之一。目前相当多人对该问题持悲观态度，但无论上述问题的答案如何，对计算机科学的影响都会是深远的。

而常说的“NP难的”问题，则是指那些至少和NP问题一样难的问题。也就是说，如果一个问题是NP难的，那么任何NP问题都可以在多项式时间内归约到该问题上。换句话说，解决这个NP难的问题至少和解决所有NP问题一样困难。那自然也有些NP难的问题本身就是NP问题，这类问题被称为NP完全问题。NP完全问题是一个非常重要的概念，因为如果我们能够找到一个多项式时间算法来解决任何一个NP完全问题，那么我们就可以证明$\text{P} = \text{NP}$。反之，如果我们能够证明没有多项式时间算法能够解决任何一个NP完全问题，那么我们就可以证明$\text{P} \neq \text{NP}$。常见的NP完全问题包括旅行商问题、顶点覆盖问题、3-SAT问题等。第一个被证明是NP完全的问题是布尔可满足性问题（SAT），这是由计算机科学家斯蒂芬·库克在1971年提出的，称为库克定理，之后证明所有问题是NP完全问题的过程都可以归结为将该问题归约到SAT问题上。

那有没有一些问题，其复杂性还要比NP完全问题更高？那显然是有的。不过绝大多数问题依然是P问题或NP问题，且大多数实际应用中的问题也都是P问题或NP问题。因此，在实际编程中，我们通常只需要关注P问题和NP问题，而不需要过多地考虑更高复杂度的问题。我们在这里给出一个链条，来表示不同复杂度类之间的关系：
$$\text{P} \subseteq \text{NP} \subseteq \text{EXP} \subseteq \text{NEXP} \subseteq \text{REC} \subsetneq  \text{RE} \subsetneq \text{ALL}$$

常见精确算法思想¶

算法可以简单地分为两类：精确算法和近似算法。精确算法是指能够在有限时间内找到问题的最优解的算法，通常适用于那些问题规模较小或者对解的精度要求较高的场景；而近似算法则是“差不多就行”的算法，通常适用于那些问题规模较大或者对解的精度要求不高的场景。

查表¶

查表法指的是预先计算出问题所有可能的结果，然后根据需要直接查表得出结果。在日常生活中，我们经常看到查表的影子，例如速算20以内乘法时，我们往往会直接记住大乘法表，而不是每一次都重新计算一次；又如投篮时，我们实际上是根据经验来调整投篮的力度和角度（实际上可以认为是人脑在查表），而不是每次都重新计算抛物线。

查表严格说来不能算是一个“算法”，因为实际上该方法并没有提供一个解决问题的手段，而是通过牺牲空间来换取时间，从而达到快速解决问题的目的。查表法的优势是时间复杂度极低，结合哈希表等数据结构，查找时间可以达到\(O(1)\)。缺点是它的空间复杂度往往很大，且实际上在大多数情况下因为可能的解太多了而并不实用，或者计算任务并非人力所能及³。查表往往只在问题规模非常小、问题的解数量非常有限、对时间的要求非常高的场景下使用。

虽然很多人并不喜欢该方法，但在实际编程中，查表法却是一个非常实用的技巧，尤其是在需要频繁计算某些结果时，用查表替代计算往往能显著提升程序的性能。例如我们如果需要一些素数，可以预先计算出一定范围内的素数表，然后在需要时直接查表，而不是每次都重新计算。

请编写一个程序，这个程序接受一些整数，然后输出这些整数是不是素数。

**输入**：m+1行，第一行是一个整/数m，表示接下来有m个整数需要判断；接下来的m行，每行一个整数n。n的数值在0到1000之间。

**输出**：m行，每行一个字符串，表示对应的整数是不是素数。如果是素数，输出“YES”，否则输出“NO”，如果输入的是1，输出“NA”。

我们可以先预处理出1000以内的所有素数，然后对于每个输入的整数，直接判断它是否在素数列表中即可。

我们知道，数组的索引天然是自然数，非常适宜做这种标记，在筛完之后只需要按索引查询即可；想到“按索引查询”，立刻想到顺序表`vector`。于是，我们得以模拟过程，得到如下代码：

模拟¶

模拟法指的是通过逐步模拟问题的过程来解决问题。这种方法通常适用于那些问题本身具有明确的步骤或过程，可以通过逐步执行这些步骤来达到最终目标。其优势在于它直观易懂，且适用于各种复杂的问题。缺点是时间复杂度往往较高，尤其是在问题规模较大时，模拟法可能会变得非常低效。

有时候，容易想到的模拟法并不是最好的算法，如果能够通过数学推导、逻辑分析等方法来优化算法，往往能得到更高效的解决方案。因此，在使用模拟法时，我们也要注意其效率，尽量避免不必要的计算和重复操作。

给定一个n，试着求下列表达式的值：
$$42 \times \sum_{i=1}^{n} \sum_{j=1}^{n}(i+j)(ij) , 1\le n \le 998244353 $$

提示：若$i$和$j$取值无关，则有$\sum_i \sum_j f(i)g(j) =( \sum_i f(i)) (\sum_j g(j))$

**输入**：一行，一个整数n。

**输出**：一行，一个整数，表示结果。

分析上述题目，如果用双重循环枚举$i$和$j$，时间复杂度是$O(n^2)$。我们已经知道，$n$的最大值是998244353，这个数量级的平方显然是无法接受的。我们需要对题目进行分析，推导出一个更高效的计算方法。另一方面，整数`int`的范围是$-2^{31}$到$2^{31}-1$，大约是$-21$亿到$21$亿，而题目中要求的结果显然远远超过了这个范围，因此我们需要使用更大范围的整数类型`long long`，该数据类型的范围大约是$-9$万亿到$9$万亿，题目中的结果应该在这个范围内。

所以要求解这个问题，我们可以先将表达式进行展开。展开的过程略，总之最终结果是$7n^2(n+1)^2(2n+1)$。直接输出这个结果即可。

代码过于简单，留作练习。

枚举¶

枚举法指的是通过穷举所有可能的解来找到问题的答案。这种方法通常适用于那些问题规模较小，或者解的数量有限的情况。其优势在于它能够确保找到最优解，且实现简单直观。缺点是时间复杂度往往较高，尤其是在问题规模较大时，枚举法可能会变得非常低效。

在枚举的时候，我们一定要尽可能地缩小枚举的范围、减少枚举的次数。例如，在求解组合问题时，我们可以通过剪枝、排序等方法来减少不必要的枚举，从而提升算法的效率。

公鸡每只5元，母鸡每只3元，小鸡三只1元，100元钱买100只鸡，请问公鸡、母鸡、小鸡各买多少只刚好凑足100元钱？请编写程序计算所有可能的购买方案。

**输入**：无。

**输出**：每行三个整数，分别表示公鸡、母鸡、小鸡的数量。按公鸡数量从小到大排序输出。

该问题实际上可以抽象为以下方程组：
$$
x + y + z = 100 \\
5x + 3y + \frac{1}{3}z = 100
$$
其中，$x$表示公鸡的数量，$y$表示母鸡的数量，$z$表示小鸡的数量。一个简单的思路是写一个双重循环，枚举公鸡和母鸡的数量，然后计算出小鸡的数量，最后判断是否满足条件。显然，上述题目中公鸡和母鸡的数量都不会超过20，因此枚举的时间复杂度$O(n^2)$是可以接受的。

当然，如果我们能通过分析，推导出一个更高效的枚举方法，那就更好了。实际上我们可以将方程组两边同时乘以3，得到：
$$
x + y + z = 100 \\
15x + 9y + z = 300
$$
这样，我们就可以通过消元法，消去$z$并进一步化简，得到：
$$7x + 4y = 100$$
更进一步地，把$y$移到等式右边，我们发现$7x$必须是$25-y$的4的倍数，因此我们可以直接以4为步长枚举$x$，这样就可以进一步减少枚举的次数。

代码实现如下：

贪心¶

贪心法指的是在每一步选择中都采取当前状态下最优的选择，从而希望通过一系列局部最优的选择来达到全局最优。这种方法通常适用于那些问题具有“贪心选择性质”的情况，即通过局部最优选择能够得到全局最优解。其优势在于它实现简单，且时间复杂度通常较低。缺点是，对于相当多的问题而言，贪心得到的解是错误的，因此在使用贪心法时，我们需要仔细分析问题，确保其满足贪心选择性质。

有一个理发师要为一群顾客理发。每个顾客都有一个理发时间，理发师希望通过合理安排顾客的理发顺序，使得所有顾客的平均等待时间最小。请编写程序，计算最小的平均等待时间。

**输入**：第一行一个整数n，表示顾客的数量；第二行n个空格分隔的整数，表示每个顾客的理发时间。

**输出**：一行，一个整数，表示最小的平均等待时间（向下取整）。

该问题可以通过贪心算法来解决。我们可以将顾客按照理发时间从小到大排序，然后依次为每个顾客理发。这样，理发时间较短的顾客会先被理发，从而减少了后续顾客的等待时间。

上述算法的正确性证明非常简单。不妨设有n个顾客，其理发时间分别为$t_1,t_2,\dots,t_n$。对于排在第$i$个顾客，他的等待时间为前面所有顾客的理发时间之和，即：
$$W_i = \sum_{j=1}^{i-1} t_j$$
因此，所有顾客的总等待时间为：
$$W = \sum_{i=1}^{n} W_i = \sum_{i=1}^{n} \sum_{j=1}^{i-1} t_j$$
我们可以交换求和顺序，得到：
$$W = \sum_{j=1}^{n} t_j \cdot (n - j)$$
上述乘积求最小值看起来非常困难。但是我们只需要利用排序不等式：顺序和大于乱序和大于反序和。也就是说，我们只需要将$t_j$按从小到大排序，就能使得总等待时间最小。

分治和减治¶

分治法指的是将一个复杂的问题分解为若干个规模较小的子问题，分别解决这些子问题，然后将它们的解合并，得到原问题的解。这种方法通常适用于那些问题具有“最优子结构性质”的情况，即原问题的最优解可以通过子问题的最优解来构建。其优势在于它能够显著降低问题的复杂度，且适用于各种复杂的问题。缺点是实现相对复杂，且在某些情况下可能会导致重复计算。另，如果子问题之间不独立（即子问题的解会相互影响），或子问题的解决方法不一致，那么分治法就不适用了。

减治法是分治的一个变体。分治法在把问题分解之后，这些子问题都是要独立解决的；而减治法则不会解决被分解后的所有问题。相反，减治法通常只会解决其中的一个或几个子问题，然后通过这些子问题的解来构建原问题的解。减治法的优势在于它能够进一步降低问题的复杂度，且适用于那些子问题之间存在依赖关系的情况，例如二分查找等。缺点是实现相对复杂，且在某些情况下可能会导致重复计算。

现有一堆芯片需要测试。每个芯片要么是好的，要么是坏的。现在有一种测试方法，可以将两个芯片放在一起进行测试。好的芯片总是能够正确地测试另一个芯片，而坏的芯片则无法保证测试结果的正确性。已经知道好芯片的数量比坏芯片多。请设计算法，用最少的测试次数找出一个好的芯片。

我们可以使用类似淘汰赛的分治方式来找出一个好的芯片。我们将所有芯片两两配对进行测试，测试结果有三种可能：

很多分治算法都可以写成递归的形式，例如归并排序、快速排序等。递归的实现方式往往更加简洁明了，但需要注意递归的深度和栈空间的使用，避免出现栈溢出的问题。然而，所有的递归都可以写成显式栈的迭代形式，而怎样把递归写成显式栈则是一个需要练习的技巧，该技巧在实用主义的编程中能有效防止栈溢出，具体操作方式见上一章。

动态规划¶

动态规划法指的是将一个复杂的问题分解为若干个子问题，先解决这些子问题，然后通过子问题的解来构建原问题的解。其优势在于它能够显著降低问题的复杂度，且适用于各种复杂的问题。缺点是实现相对复杂，且需要额外的存储空间来保存子问题的解。

一个动态算法是正确的，当且仅当满足以下条件： - 最优子结构性质： 原问题的最优解可以通过子问题的最优解来构建。 - 重叠子问题性质： 子问题之间存在重叠，即同一个子问题可能会被多次计算。 - 无后效性： 一旦子问题的解被确定，它就不会再受到后续决策的影响。 如果一个问题不满足重叠子问题性质，那么它通常不适合使用动态规划来解决，而更适合使用分治法来解决。

动态规划往往以递推的形式实现，即通过迭代的方式逐步计算出子问题的解，最终得到原问题的解。动态规划的关键在于确定状态转移方程，即如何通过子问题的解来构建原问题的解。

值得注意的是贪心与动态规划之间的区别与联系。贪心和动态规划均通过局部决策来解决全局最优化问题，但贪心每一步只看眼前最优，不能回头，而动态规划会保存子问题状态，“更为综合”地保证全局最优。在实际解题中，关键在于判断一个问题更适合用贪心（需证明局部最优能导出全局最优）、动态规划（需设计合理的状态与转移），还是其他算法来解决；这一能力可以通过不断练习来加强。

计数和概率递推等非最优化问题的递推解法也常习惯性地称作“动态规划”，但严格来说它们并不属于动态规划的范畴。下文对此不做区分。

小明正在爬楼梯。小明每次可能爬1级台阶，也可能爬2级台阶。假设小明要爬n级台阶，请问他有多少种不同的爬楼梯方式？

**输入**：一行，一个整数n，表示台阶的数量。

**输出**：一行，一个整数，表示不同的爬楼梯方式。

该问题可以通过递推来解决。我们可以定义一个数组`dp`，其中`dp[i]`表示爬到第$i$级台阶的不同方式数。显然，`dp[0]=1`（不需要爬任何台阶），`dp[1]=1`（只有一种方式爬到第一级台阶）。对于$i \geq 2$，我们可以通过以下递推关系来计算`dp[i]`：
$$dp[i] = dp[i-1] + dp[i-2]$$
这是因为要到达第$i$级台阶，可以从第$i-1$级台阶爬1级上来，或者从第$i-2$级台阶爬2级上来。

这个递推也可以认为是动态规划的最初级阶段。

对于新手而言，动态规划问题可能比较困难，需要仔细分析问题，找出合适的状态和递推关系。

给定一个整数序列。定义**子序列**为从这个母序列中删除一些元素（也可以不删除）后，剩下的元素按原来的顺序排列形成的序列。现在要求出它的一个子序列，该子序列的每一个元素都大于等于前一个元素，且该子序列的长度尽可能大。请编写程序，计算这个子序列的长度。

**输入**：第一行一个整数n，表示序列的长度；第二行n个空格分隔的整数，表示序列的元素。

**输出**：一行，一个整数，表示最长非降子序列的长度。

上述问题就是经典的**最长非降子序列**问题。这个问题向来是萌新杀手，难点在怎么定义状态和递推关系。能够自己推导出状态和递推关系的同学，已经掌握了动态规划的精髓。

下面我们来分析这个问题。一个朴素的想法是，不妨设`dp[i]`表示以第$i$个元素结尾的最长非降子序列的长度。对于任何元素，我们都遍历它前面的所有元素，如果前面的元素$A_j$小于等于当前元素$A_i$，那么我们就把$A_i$接到$A_j$的后面，这样就形成了一个更长的非降子序列。因此，我们可以得到以下递推关系：
$$ \forall A_j \leq A_i, \forall j < i, dp[i] = \max(dp[j] + 1) $$
代码写出来如下：

回到刚才，我们是用枚举法来求符合条件的$j$，进而求出`dp[i]`。如果我们能用更高效的方法来求出符合条件的$j$，就能进一步提高算法效率。我们知道，枚举是很笨的，有没有更高效的算法来解决这个问题呢？答案是有的。

我们跳出“模拟”的思维，换个角度来看这个问题。我们不再关心这个长度是怎么一步步推出来的，而是直接关注长度本身：**如果我们想构造一个尽可能长的非降子序列，那么在每一步，我们都希望这个序列的“尾巴”尽可能小，这样后面才能接上更多的数。**

局势瞬间明朗了起来。我们可以维护一个数组`tails`，其中`tails[k]`表示长度为$k+1$的非降子序列的最小结尾元素。怎么构建这个数组呢？我们只需要从左往右遍历原序列，对于每一个元素$A_i$，我们在`tails`中找到**第一个**大于$A_i$的元素，并将其替换为$A_i$。如果没有找到，则将$A_i$添加到`tails`的末尾。这样，`tails`数组的长度就是最长非降子序列的长度，顺便还能得到一个这样的子序列。

容易证明，`tails`数组是严格非降的，因此我们可以使用二分查找来提高查找效率。这样，整个算法的时间复杂度就降到了$O(n \log n)$。

vector<int> nums = ...; // 输入的整数序列
vector<int> tails;
for (int num : nums) {
    auto it = upper_bound(tails.begin(), tails.end(), num); // 找到第一个 > num 的位置
    if (it == tails.end()) {
        tails.push_back(num); // 可以扩展序列
    } else {
        *it = num; // 替换掉更大的末尾
    }
}

回溯和分支限界¶

回溯法指的是通过逐步构建解的候选解空间，并在发现某个候选解不满足条件时，回溯到上一步继续尝试其他可能的解。这种方法通常适用于那些问题具有“约束满足性质”的情况。其优势在于它能够找到所有满足条件的解，且适用于各种复杂的问题。缺点是时间复杂度往往较高，时间复杂度是指数级别的，尤其是在问题规模较大时，回溯法可能会变得非常低效。

为了杜绝上述低效问题，我们应该尽可能地减少回溯的次数，这就需要在回溯过程中进行剪枝，即在发现某个候选解一定不满足条件时，立即停止继续尝试该候选解的后续分支，从而减少不必要的计算。这就是“分支限界法”的思想。常见的剪枝方法包括可行性剪枝、最优性剪枝、启发式剪枝等。

• 可行性剪枝： 在回溯过程中，如果发现当前候选解已经不满足问题的约束条件，那么就立即停止继续尝试该候选解的后续分支。
• 最优性剪枝： 在回溯过程中，如果发现当前候选解已经无法达到最优解，那么就立即停止继续尝试该候选解的后续分支。
• 启发式剪枝： 在回溯过程中，利用问题的特性或经验知识，提前判断某个候选解是否有可能满足条件，从而决定是否继续尝试该候选解的后续分支。

国际象棋中，“后”这个棋子可以攻击同一行、同一列以及同一对角线上任意距离的棋子。现在我们在一个标准的国际象棋棋盘（8x8）上放置8个后，要求这些后互不攻击。请编写程序，计算所有可能的放置方案。

**输入**：无。

**输出**：每行8个整数，表示一个放置方案，每个整数表示该行后所在的列（从0开始计数）。按字典序排序输出所有方案。不考虑旋转对称性和镜像对称性。

该问题可以通过回溯法来解决。我们可以逐行放置后，对于每一行，我们尝试将后放在每一列上，并检查是否与之前放置的后冲突。如果不冲突，则继续放置下一行的后；如果冲突，则回溯到上一行，尝试其他列。这样，我们可以遍历所有可能的放置方案。

具体实现时，我们可以使用一个数组`positions`来记录每一行后所在的列。我们还需要一个函数来检查当前放置的后是否与之前的后冲突。代码实现如下：

线性规划¶

线性规划法指的是通过构建线性目标函数和线性约束条件，来求解最优化问题。这种方法通常适用于那些问题可以用线性方程组或不等式组来描述的情况。其优势在于它能够高效地求解大规模的最优化问题，且有成熟的算法和工具可供使用。缺点是它仅适用于线性问题，对于非线性问题则无法直接应用。

某工厂生产两种产品A和B。每种产品的利润分别为3元和5元。生产每种产品需要消耗一定的资源：生产1个A需要2单位资源，生产1个B需要3单位资源。工厂每天可用的资源总量为18单位。请问工厂每天应该生产多少个A和B，以最大化利润？

**输入**：无。

**输出**：一行，两个整数，分别表示每天生产的A和B的数量。

该问题可以通过线性规划来解决。我们可以定义变量$x$和$y$，分别表示每天生产的A和B的数量。我们的目标是最大化利润函数：
$$\text{Maximize } Z = 3x + 5y$$
同时，我们需要满足资源约束条件：
$$2x + 3y \leq 18$$
$$x \geq 0, y \geq 0$$

我们可以使用单纯形法或其他线性规划算法来求解这个问题。通过计算，我们可以得到最优解为$x=3$，$y=4$，即每天生产3个A和4个B，可以最大化利润。

为了帮助同学们解决上述问题，我们介绍一下“单纯形法”的基本思想。单纯形法是一种用于求解线性规划问题的迭代算法。其基本思想是从一个可行解出发，沿着可行域的边界移动，逐步找到更优的解，直到达到最优解为止。具体步骤如下： - 初始化：选择一个初始可行解，通常是通过引入松弛变量来构建一个基本可行解。 - 迭代：在当前可行解的邻域中寻找一个更优的解。如果找到了更优的解，则更新当前解；否则，终止迭代。 - 终止：当无法找到更优的解时，当前解即为最优解。 以上述题目为例，我们先将约束条件转化为等式形式，引入松弛变量\(s\)，得到： $$ 2x + 3y + s = 18 \ x \geq 0, y \geq 0, s \geq 0 $$ 然后，我们可以利用枚举等手段，并通过迭代过程（枚举进入基变量和离开基变量）逐步优化，直到无法继续优化为止。最终，我们可以得到最优解。

当然，也有其他的手段来解决动态规划问题，例如使用现成的线性规划库（如GLPK、CPLEX等）来求解，或数形结合（仅限于几何意义明确的问题）。线性规划的应用范围非常广泛，涵盖了经济学、运筹学、工程学等多个领域，是一种非常重要的优化工具。

常见近似算法思想¶

随机化算法¶

随机化算法指的是在算法的某些步骤中引入随机性，从而提高算法的效率或简化算法的设计。这种方法通常适用于那些问题规模较大，或者对解的精度要求不高的情况。其优势在于它能够显著降低问题的复杂度，且实现相对简单。缺点是结果具有一定的随机性，可能无法保证每次运行都得到最优解。

随机化算法可以分为两类：蒙特卡洛算法和拉斯维加斯算法。蒙特卡洛算法在有限时间内给出一个近似解，且有一定概率得到正确解；而拉斯维加斯算法则保证每次运行都能得到正确解，但运行时间是随机的。

在一场拍卖会中，我们希望选择一个出价高的竞拍者。一旦选定了某个竞拍者，就不能更改选择；我们也没有手段能够提前得知这些竞拍者的出价情况。这些竞拍者的出价是一个随机的序列。我们怎样才能使得选择的竞拍者的出价是最高价的概率最大呢？

我们可以使用随机化算法来解决这个问题。具体来说，我们先观察前$r$个竞拍者的出价，记录下其中的最高价$M$。然后，从第$r+1$个竞拍者开始，如果某个竞拍者的出价高于$M$，我们就选择这个竞拍者并结束选择；否则，继续观察下一个竞拍者。这样，我们可以最大化选择到最高价竞拍者的概率。现在的问题就变成，怎样求解$r$才能使得选择到最高价竞拍者的概率最大。

假设最高价出在位置$k$。我们能选到这个人当且仅当：

所以总的选中最优的概率为：

当$r$较大时，$\sum_{j=r}^{n-1} \frac{1}{j}$可以近似为$\ln(n) - \ln(r)$。因此，我们设$x=r/n$，则有：

上述算法是一个蒙特卡洛算法，因为它在有限时间内给出了一个近似解，且有一定概率得到正确解。拉斯维加斯算法则不是很常见，但在特定的领域比较常用，例如随机快速排序等。我们会在后续章节中介绍相关内容。

启发式算法¶

启发式算法指的是通过经验、直觉或启发式规则来指导搜索过程，从而找到问题的近似解。这种方法通常适用于那些问题规模较大，或者对解的精度要求不高的情况。其优势在于它能够显著降低问题的复杂度，且实现相对简单。缺点是结果具有一定的随机性，可能无法保证每次运行都得到最优解。

下文中的TSP，指的是旅行商问题（Traveling Salesman Problem），即给定一组城市和它们之间的距离，要求找到一条最短的路径，使得旅行商能够访问每个城市一次并返回起点。TSP是一个NP完全问题，当路径数量极多的时候，常规的精确算法（如动态规划、分支限界法等）完全无法在可以接受的时间内求解（上述算法的时间复杂度均为指数级别）。因此，启发式算法在解决TSP问题中得到了广泛应用。

贪心¶

贪心是最简单的启发式算法。其基本思想和上文精确算法中的“贪心”其实完全一致，甚至不如说上文中的“贪心”实际上是该算法“算对了”的一种特殊情况。具体来说，贪心算法从一个初始城市出发，每次选择距离当前城市最近的未访问城市作为下一个访问的城市，直到所有城市都被访问过为止。最后，返回起点，完成整个路径。贪心算法实现简单，且时间复杂度较低，但其结果往往不是最优解，因为它只考虑了局部最优选择，而忽略了全局最优解。

标题：贪心算法解决TSP问题的伪代码
输入：城市集合$C$，距离矩阵$D$
输出：近似最优路径$P$
P <- 空路径
visited <- 空集合
current <- 随机选择一个初始城市
添加current到P和visited
while 未访问的城市不为空:
  next <- 在未访问的城市中选择距离current最近的城市
  添加next到P和visited
  current <- next
添加起点到P
return $P$

爬山¶

爬山算法是一种简单的启发式算法，用于在极大的搜索空间中寻找近似最优解。其基本思想是从一个初始解出发，逐步探索邻域解，如果找到一个更优的邻域解，就移动到该解，并继续搜索，直到无法找到更优的邻域解为止。这样的“初始解”有很多方式来取得，例如随机、贪心、特定构造都可以。示例伪代码中的“邻域”可以通过交换路径中的两个城市来定义。爬山算法实现简单，但是容易陷入局部最优解，无法保证找到全局最优解。

标题：爬山算法解决TSP问题的伪代码
输入：城市集合$C$，距离矩阵$D$
输出：近似最优路径$P$
P <- 随机生成一个初始路径
while 存在更优的邻域路径:
  P' <- 在P的邻域中找到一个更优的路径
  if 路径$P'$的长度小于路径$P$的长度:
    P <- P'
return $P$

模拟退火¶

模拟退火算法是一种基于物理退火过程的启发式算法，用于在复杂的搜索空间中寻找近似最优解。其基本思想是通过引入随机性，偶尔接受一个较差的解，来避免陷入局部最优。具体来说，模拟退火算法从一个初始解出发，在每一步中随机选择一个邻域解，如果该邻域解更优，则接受该解；如果该邻域解更差，则以一定概率接受该解，这个概率随着时间的推移逐渐降低（类似于物理退火过程中的温度降低）。这样，算法在初期可以探索更多的解空间，随着时间的推移逐渐收敛到一个较优解。示例伪代码中的“邻域”同样可以通过交换路径中的两个城市来定义。模拟退火算法能够有效地避免陷入局部最优解，但其性能依赖于参数的选择，如初始温度和冷却速率。

标题：模拟退火算法解决TSP问题的伪代码
输入：城市集合$C$，距离矩阵$D$，初始温度$T_0$，冷却速率$\alpha$
输出：近似最优路径$P$
P <- 随机生成一个初始路径
T <- T_0
while $T > T_{min}$:
  P' <- 在P的邻域中随机选择一个路径
  \Delta E <- 路径P'的长度 - 路径P的长度
  if $\Delta E < 0$:
    P <- P'
  else:
    以概率e^{-\Delta E / T}接受路径P'
  T <- \alpha \cdot T
return $P$

遗传算法¶

遗传算法是一种基于自然选择和遗传学原理的启发式算法，用于在复杂的搜索空间中寻找近似最优解。其基本思想是通过模拟生物进化过程中的选择、交叉和变异等机制，逐步优化解的质量。具体来说，遗传算法从一个初始种群（即一组解）出发，通过评估每个解的适应度，选择适应度较高的解进行交叉和变异，生成新的种群。这个过程不断重复，直到满足终止条件（如达到最大迭代次数或找到足够好的解）。遗传算法广泛应用于各种优化问题，示例伪代码中的“交叉”可以通过交换两个路径的部分片段来实现，“变异”可以通过随机交换路径中的两个城市来实现；适应度通常定义为路径的总长度的倒数或相反数等。

标题：遗传算法解决TSP问题的伪代码
输入：城市集合$C$，距离矩阵$D$，种群大小$N$，最大迭代次数$G$
输出：近似最优路径$P$
初始化种群P_0，包含N个随机生成的路径
for $g = 1$ 到 $G$:
  评估种群中每个路径的适应度
  选择适应度较高的路径进行交叉和变异，生成新的种群P_g
return 种群中适应度最高的路径

遗传算法的优点是其全局搜索能力很强，能够有效地探索复杂的解空间；缺点是计算量较大，且参数调节较为复杂。在著名科幻小说《三体》第一部中，作者刘慈欣提到“遗传算法”这一概念，并将其作为故事情节的一部分，展示了科学与文学的结合。其具体操作为：通过随机初始化许多个三体问题的初始条件（如三个恒星的位置、速度），对其进行路径模拟，评估每个初始条件下三体系统的稳定性（适应度），选择适应度较高的初始条件进行交叉和变异，生成新的初始条件。经过多代迭代，最终找到一个较为稳定的三体系统配置。这一过程体现了遗传算法在解决复杂物理问题中的应用，同时也为小说增添了科学色彩。

蚁群算法¶

蚁群算法是一种基于蚂蚁觅食行为的启发式算法，用于在复杂的搜索空间中寻找近似最优解。其基本思想是通过模拟蚂蚁在寻找食物过程中释放信息素的行为，逐步优化解的质量。具体来说，蚁群算法从一个初始解出发，模拟多只蚂蚁在解空间中移动，每只蚂蚁根据路径上的信息素浓度选择下一步的移动方向。路径越短的信息素浓度越高，吸引更多的蚂蚁选择该路径。随着时间的推移，信息素会挥发，促使蚂蚁探索新的路径。示例伪代码中的“启发式信息”可以是城市之间的距离的倒数，表示距离越近的城市越有吸引力。蚁群算法的优点是其分布式搜索能力强，能够有效地探索复杂的解空间；缺点是计算量较大，且参数调节较为复杂。

标题：蚁群算法解决TSP问题的伪代码
输入：城市集合$C$，距离矩阵$D$，蚂蚁数量$M$，最大迭代次数$G$
输出：近似最优路径$P$
初始化信息素矩阵\tau
for $g = 1$ 到 $G$:
  for 每只蚂蚁$i = 1$ 到 $M$:
    构建路径P_i，根据信息素浓度和启发式信息选择下一城市
    计算路径P_i的长度
  更新信息素矩阵\tau，根据所有蚂蚁的路径长度调整信息素浓度
return 所有蚂蚁中路径长度最短的路径

A*搜索¶

A搜索算法是一种基于启发式搜索的路径规划算法，用于在图中寻找从起点到终点的最短路径。其基本思想是结合实际代价和启发式估计来指导搜索过程，从而高效地找到最优解。具体来说，A算法维护一个优先队列，存储待扩展的节点。每个节点都有一个评估函数\(f(n) = g(n) + h(n)\)，其中\(g(n)\)表示从起点到当前节点的实际代价，\(h(n)\)表示从当前节点到终点的启发式估计代价。A算法每次从优先队列中选择\(f(n)\)值最小的节点进行扩展，直到找到终点为止。示例伪代码中的“启发函数”可以是当前节点到终点的最短距离的估计，也可能是其他更复杂的估计方法。A搜索算法的优点是其能够高效地找到相对较优的解，且适用于各种路径规划问题，但启发式函数的选择对算法性能有较大影响。特别的，当启发函数满足可采纳性（即不高估实际代价）和一致性（即满足三角不等式）时，A*算法能够保证找到最优解。

标题：A*搜索算法解决TSP问题的伪代码
输入：城市集合$C$，距离矩阵$D$，启发式函数$h(n)$
输出：近似最优路径$P$
初始化优先队列Q
将起点节点加入队列Q
while 队列$Q$不为空:
  n <- 从队列Q中取出f(n)值最小的节点
  if $n$是终点节点:
    return 从起点到终点的路径
  扩展节点n的邻居节点，并计算它们的f(n)值
  将邻居节点加入队列Q

搜索和排序¶

搜索和排序是两个基本的算法问题，广泛应用于各种计算任务中。搜索问题涉及在数据结构中查找特定元素，而排序问题则涉及将一组元素按照某种顺序排列。下面我们将介绍一些常见的搜索和排序算法（在线性的数据结构上进行搜索和排序，暂不考虑非线性的数据结构如树、图等），且这里不涉及并行和分布式算法，也不涉及非精确的排序和搜索算法（如近似算法、概率算法等）。

排序算法¶

排序算法用于将一组元素按照某种顺序排列。

冒泡排序¶

冒泡排序重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。

vector<int> arr = ...; // 输入的数组
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
    for (int j = 0; j < n - i - 1; ++j) {
        if (arr[j] > arr[j + 1]) {
            swap(arr[j], arr[j + 1]); // 交换
        }
    }
}

选择排序¶

选择排序的工作原理是每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。

vector<int> arr = ...; // 输入的数组
int n = arr.size();
for (int i = 0; i < n - 1; ++i) {
    int min_idx = i; // 假设当前元素是最小的
    for (int j = i + 1; j < n; ++j) {
        if (arr[j] < arr[min_idx]) {
            min_idx = j; // 更新最小元素的索引
        }
    }
    swap(arr[i], arr[min_idx]); // 交换
}

插入排序¶

插入排序的工作原理是从左向右地构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

for (int i = 1; i < n; ++i) {
    int key = arr[i]; // 当前元素
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j]; // 向后移动
        j--;
    }
    arr[j + 1] = key; // 插入
}

快速排序¶

快速排序的工作原理是通过一个“基准”元素将数组分成两部分，左边部分的元素都小于基准，右边部分的元素都大于基准，然后递归地对这两部分进行排序。快速排序是一种分治算法。

void quicksort(int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2]; // 选择基准
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            swap(arr[i], arr[j]); // 交换
            i++;
            j--;
        }
    }
    quicksort(left, j); // 递归排序左半部分
    quicksort(i, right); // 递归排序右半部分
}

快排有一个变种：随机快排，即每次随机选择一个基准元素，从而避免在某些特定情况下退化为\(O(n^2)\)的时间复杂度。该算法是一个拉斯维加斯算法，因为它保证每次运行都能得到正确解，但运行时间是随机的。

归并排序¶

归并排序的工作原理是将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并在一起。归并排序也是一种分治算法。

void merge(int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}
void mergesort(int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergesort(left, mid); // 递归排序左半部分
    mergesort(mid + 1, right); // 递归排序右半部分
    merge(left, mid, right); // 合并
}

堆排序¶

堆排序的工作原理是将数组构建成一个最大堆（或最小堆），然后不断地将堆顶元素与数组的最后一个元素交换，并将堆的大小减1，重新调整堆，直到堆为空。

void heapify(int n, int i) {
    int largest = i; // 初始化最大元素为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        swap(arr[i], arr[largest]); // 交换
        heapify(n, largest); // 递归调整子树
    }
}
void heapsort() {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; --i) heapify(n, i); // 构建最大堆
    for (int i = n - 1; i > 0; --i) {
        swap(arr[0], arr[i]); // 交换堆顶和最后一个元素
        heapify(i, 0); // 重新调整堆
    }
}

vector<int> arr = ...; // 输入的数组
make_heap(arr.begin(), arr.end()); // 构建堆
sort_heap(arr.begin(), arr.end()); // 堆排序

priority_queue<int> pq; // 创建最大堆
for (int num : arr) {
    pq.push(num); // 插入元素
}
vector<int> sorted_arr;
while (!pq.empty()) {
    sorted_arr.push_back(pq.top()); // 获取堆顶元素
    pq.pop(); // 删除堆顶元素
}
reverse(sorted_arr.begin(), sorted_arr.end()); // 反转得到升序排列

常见排序算法的时间和空间复杂度比较

由上表可见，快速排序在平均情况下表现较好，但在最坏情况下可能退化为\(O(n^2)\)。归并排序和堆排序在最坏情况下也能保持\(O(n \log n)\)的时间复杂度。冒泡排序、选择排序和插入排序由于其简单性，适合处理小规模数据，但对于大规模数据则效率较低。

对于大多数情况，我们最好不要手写排序算法，而是直接使用标准库中的排序函数，如C++的std::sort，它通常混合了多种排序算法，能够高效地处理各种规模的数据。

搜索算法¶

搜索（查找）算法用于在数据结构中查找特定元素。

线性搜索¶

线性搜索基本思想是从数据结构的第一个元素开始，逐个比较每个元素与目标元素是否相等，直到找到目标元素或遍历完整个数据结构为止。最常见的线性搜索例如：找最大值、找最小值、在无序的数组中确认某个值的索引等。

vector<int> arr = ...; // 输入的数组
int target = ...; // 目标值
for (int i = 0; i < arr.size(); ++i) {
    if (arr[i] == target) {
        cout << "Found at index " << i << endl;
        break;
    }
}

双向搜索¶

双向搜索和普通的线性搜索类似，但是它从起点和终点同时开始搜索，直到两个搜索相遇。这一算法常用于状态空间对称的问题，例如在图中寻找最短路径等。在线性数据结构上，这个算法并不常见（但有时候也有奇效，例如其变体“双指针法”），但在图论中非常有用。

标题：双向搜索
输入：图$G$，起点$s$，终点$t$
输出：从$s$到$t$的路径
初始化两个队列Q_s和Q_t，分别用于从s和t开始的搜索
初始化两个集合visited_s和visited_t，分别记录从s和t访问过的节点
将s加入队列Q_s和集合visited_s
将t加入队列Q_t和集合visited_t
while 队列$Q_s$和$Q_t$均不为空:
  从队列Q_s中取出一个节点进行扩展
  如果该节点在集合visited_t中，则找到路径，返回结果
  否则，将该节点的邻居节点加入队列Q_s和集合visited_s

  从队列Q_t中取出一个节点进行扩展
  如果该节点在集合visited_s中，则找到路径，返回结果
  否则，将该节点的邻居节点加入队列Q_t和集合visited_t

二分搜索¶

二分查找是一种高效的搜索算法，适用于有序数组。它通过不断地将搜索范围缩小一半来查找目标值。二分查找也是一种分治算法。

vector<int> arr = ...; // 输入的有序数组
int target = ...; // 目标值
int left = 0, right = arr.size() - 1;
while (left <= right) {
    int mid = left + (right - left) / 2; // 防止溢出
    if (arr[mid] == target) {
        cout << "Found at index " << mid << endl;
        break;
    } else if (arr[mid] < target) {
        left = mid + 1; // 目标在右半部分
    } else {
        right = mid - 1; // 目标在左半部分
    }
}

哈希搜索¶

哈希搜索通过将数据映射到一个固定大小的数组（哈希表）中来实现快速查找。它适用于需要频繁插入、删除和查找的场景。哈希表的平均时间复杂度为\(O(1)\)，但在最坏情况下可能退化为\(O(n)\)。另外，在查找之前有一个建立哈希表的过程，这个过程是\(O(n)\)的；哈希表也有着较大的常数时间和较大的空间开销。我们通常不手写哈希表，而是使用标准库中的哈希容器，如C++的std::unordered_map和std::unordered_set。

unordered_map<int, int> hash_map; // 创建哈希表
hash_map[key] = value; // 插入或更新键值对
if (hash_map.find(key) != hash_map.end()) { // 查找键
    cout << "Found: " << hash_map[key] << endl;
}
hash_map.erase(key); // 删除键值对

快速选择¶

受到快速排序的启发，出现了一种名为“快速选择”的算法。快速选择是一种用于在无序数组中查找第k小（或第k大）元素的算法。它基于快速排序的分治思想，通过选择一个“基准”元素，将数组分成两部分，然后递归地在包含第k小元素的部分继续搜索。快速选择也是一种分治算法，但它只关注找到第k小元素，而不是对整个数组进行排序。

int quickselect(vector<int>& arr, int left, int right, int k) {
    if (left == right) return arr[left]; // 只有一个元素
    int pivot = arr[(left + right) / 2]; // 选择基准
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            swap(arr[i], arr[j]); // 交换
            i++;
            j--;
        }
    }
    if (k <= j) return quickselect(arr, left, j, k); // 在左半部分继续搜索
    if (k >= i) return quickselect(arr, i, right, k); // 在右半部分继续搜索
    return arr[k]; // 找到第k小元素
}

当然，如果使用STL的nth_element函数，可以更简单地实现快速选择。

vector<int> arr = ...; // 输入的数组
int k = 2; // 举例：查找第3小元素（k从0开始）
nth_element(arr.begin(), arr.begin() + k, arr.end()); // 部分排序
int kth_smallest = arr[k]; // 第3小元素

常见搜索算法的适用场景和时间复杂度比较 如果数据规模比较小或者仅查找一次，则线性搜索更好；如果数据量小且有序，则二分搜索更好；如果数据量大且需要频繁查找，则哈希搜索更好。这是因为，在数据量大的情况下，哈希表的常数时间开销会被其高效的查找性能所抵消。

复杂数据结构上的问题⁴¶

刚刚的搜索和排序算法都是在线性数据结构上进行的。现实中，很多问题需要在更复杂的数据结构上进行搜索和排序，例如树、图等。下面我们将介绍一些常见的复杂数据结构及其上的算法。由于树的遍历已经在《数据结构》章节中介绍过，这里不再赘述；图的遍历和树很像，只需要记得标记已经访问过的节点即可

树和图上的搜索¶

DFS、BFS¶

深度优先搜索和广度优先搜索是两个最基本的树图搜索算法。它们的基本思想分别是尽可能深入地搜索树或图的分支（DFS），以及逐层地搜索树或图的节点（BFS）。具体的操作方式可以参考前文的树遍历章节。

深搜和广搜的一个重要区别在于：深搜使用栈（递归调用隐式使用栈），空间复杂度低，但是不能保证找到最短路径；而广搜使用队列，空间复杂度较高，因为需要存储当前层的所有节点，但是广搜是完备的，能够找到最短路径。

迭代加深搜索¶

迭代加深搜索可以看成是一种结合了深搜和广搜两者优点的搜索算法。它通过多次执行深搜，每次限制搜索的深度，逐渐增加深度限制，直到找到目标节点为止。这样，迭代加深搜索既能保持深搜的低空间复杂度，又能保证找到最短路径。该算法常见于状态空间较大、深度未知的问题（如拼图、路径规划）。

标题：迭代加深搜索算法
输入：图的邻接表表示$graph$，起始节点$start$，目标节点$goal$，最大深度$max_depth$
输出：是否找到目标节点
for 深度$depth$从$0$到$max_depth$:
  if 深度限制搜索($graph$, $start$, $goal$, $depth$):
    return true // 找到目标节点
return false // 未找到目标节点

最短路问题¶

最短路问题是图论中的一个经典问题，旨在找到图中两个节点之间的最短路径。根据问题的不同，可以分为单源最短路问题和多源最短路问题。单源最短路问题指的是从某一个特定的节点出发，找到该节点到图中所有其他节点的最短路径；多源最短路问题则是找到图中所有节点之间的最短路径。

Dijkstra算法¶

Dijkstra算法是一种用于在带权图中找到单源最短路径的算法。其基本思想是通过贪心策略，逐步扩展已知的最短路径，直到找到所有节点的最短路径。Dijkstra算法使用一个优先队列来存储待扩展的节点，每次选择距离源节点最近的节点进行扩展，并更新其邻居节点的距离。但是，该算法不能处理负权边。

标题：Dijkstra算法
输入：图的邻接表表示$graph$，节点数$n$，源节点$source$
输出：源节点到所有节点的最短路径长度$dist$
初始化数组dist，使得dist[i] = \infty，对于源节点source，dist[source] = 0
创建一个优先队列pq，将源节点source和距离0加入队列
while 队列$pq$不为空:
  从队列中取出距离最小的节点u
  for 每个邻居节点$v$和边权重$weight(u, v)$在$graph[u]$中:
    if $dist[u] + weight(u, v) < dist[v]$:
      dist[v] <- dist[u] + weight(u, v) // 松弛操作
      将节点v和更新后的距离加入队列pq
return dist // 返回源节点到所有节点的最短距离

Bellman-Ford算法¶

Bellman-Ford算法是一种用于在带有负权边的图中找到单源最短路径的算法。其基本思想是通过反复松弛所有边，逐步更新节点的距离，直到找到所有节点的最短路径。Bellman-Ford算法可以处理负权边，但不能处理负权环路。

标题：Bellman-Ford算法
输入：图的边列表表示$edges$，节点数$n$，源节点$source$
输出：源节点到所有节点的最短路径长度$dist$
初始化数组dist，使得dist[i] = \infty，对于源节点source，dist[source] = 0
for $i$从$1$到$n-1$:
  for 每条边$(u, v)$在$edges$中:
    if $dist[u] + weight(u, v) < dist[v]$:
      dist[v] <- dist[u] + weight(u, v) // 松弛操作
for 每条边$(u, v)$在$edges$中:
  if $dist[u] + weight(u, v) < dist[v]$:
    return “图中存在负权环路” // 检查负权环路
return dist // 返回源节点到所有节点的最短距离

负权环路是指在图中存在一条环路，其边的权重之和为负数。负权环路会导致最短路径问题变得复杂，因为通过不断地绕行负权环路，可以使得路径长度无限减小，从而无法确定一个唯一的最短路径。因此，在使用Bellman-Ford算法时，需要检查是否存在负权环路，以确保算法的正确性。而有这个东西的图，在现实中其实并不常见，而且大多数情况下我们并不关心负权环路，或强行约束这类环路只能走一次等。如果有这类约束，可以考虑将图进行变换，消除负权环路后再进行最短路径计算。

那么怎么进行图的变换呢？一种常见的方法是使用Johnson算法，它通过添加一个新的节点并连接到所有其他节点，使用Bellman-Ford算法计算从新节点到所有节点的最短路径，然后调整原图中的边权重，使得所有边权重变为非负数。这样就可以使用Dijkstra算法来计算最短路径。这个算法已经超出了本书的范围，有兴趣的读者可以自行查阅相关资料。

Floyd-Warshall算法¶

Floyd-Warshall算法是一种解决多源最短路问题的算法。该算法的核心思想是动态规划。我们定义一个二维数组\(dist[i][j]\)，表示从节点\(i\)到节点\(j\)的最短路径长度。初始时，如果存在边\((i, j)\)，则\(dist[i][j]\)为该边的权重，否则为无穷大；对于所有节点\(i\)，\(dist[i][i]\)为0。然后，我们通过逐步引入中间节点，更新\(dist\)数组，直到考虑所有节点作为中间节点为止。

标题：Floyd-Warshall算法
输入：图的邻接矩阵表示$graph$，节点数$n$
输出：所有节点之间的最短路径长度$dist$
初始化二维数组dist，使得dist[i][j] = graph[i][j]，如果i = j则dist[i][j] = 0
for $k$从$0$到$n-1$:
  for $i$从$0$到$n-1$:
    for $j$从$0$到$n-1$:
      if $dist[i][k] + dist[k][j] < dist[i][j]$:
        dist[i][j] <- dist[i][k] + dist[k][j] // 更新最短路径长度
return $dist$

在上述代码中，graph是图的邻接矩阵表示，其中graph[i][j]表示从节点\(i\)到节点\(j\)的边权重，如果不存在边则为无穷大。最终返回的dist数组包含了所有节点之间的最短路径长度。

最大流问题¶

最大流问题是指在一个流网络中，找到从源节点到汇节点的最大流量。常见的最大流算法包括Ford-Fulkerson算法、Edmonds-Karp算法等，这里也仅介绍Ford-Fulkerson算法。

为了介绍最大流问题，我们首先要了解一些基本概念： - 流网络： 流网络是一个有向图，其中每条边都有一个非负的容量，表示该边能够承载的最大流量。流网络中有一个源节点和一个汇节点，源节点是流的起点，汇节点是流的终点。 - 流： 流是指在流网络中从源节点到汇节点的流量分布。流必须满足两个条件：容量约束，即每条边上的流量不能超过该边的容量；流守恒，即除了源节点和汇节点外，每个节点的流入量等于流出量。 - 最大流： 最大流是指在流网络中，从源节点到汇节点的最大可能流量。 也就是说，我们可以把流网络比作一个在许多城市之间运输货物的系统，源节点是货物的起点，汇节点是货物的终点，而边的容量则表示每条运输线路的最大运输能力。最大流问题就是要找到一种运输方案，使得从起点到终点的货物运输量最大化，同时不超过每条运输线路的最大运输能力。

最大流问题有一个非常重要的定理，称为“最小割定理”。该定理指出，在一个流网络中，最大流量等于最小割的容量。最小割是指将流网络划分为两个部分，使得源节点和汇节点分别位于不同的部分，并且割断的边的容量之和最小。这个定理揭示了最大流问题和最小割问题之间的密切关系。该定理的具体证明不在这里介绍，有兴趣的读者可以查阅相关资料。

Ford-Fulkerson算法就是利用该定理来求解最大流问题的：其通过不断地寻找增广路径来增加流量，直到无法找到增广路径为止（即找到了最小割）。增广路径是指从源节点到汇节点的一条路径，其中每条边都有剩余容量（即容量减去当前流量大于0）。我们可以使用DFS或BFS来寻找增广路径。

标题：Ford-Fulkerson算法
输入：流网络$G=(V, E)$，源节点$s$，汇节点$t$
输出：最大流量$max_flow$
初始化所有边的流量为0
max_flow <- 0
while 存在从$s$到$t$的增广路径$P$:
  计算增广路径P上的最小剩余容量c
  for 每条边$(u, v)$在增广路径$P$上:
    增加边(u, v)的流量c
    减少边(v, u)的流量c // 反向边
  max_flow <- max_flow + c
return $max_flow$

在线算法简介¶

上述所有的算法都适用于一口气能拿到所有数据的情况，即“离线算法”。但在现实中，很多情况下数据是流式到达的，我们无法一次性拿到所有数据，这时就需要“在线算法”或“异步算法”。

在线算法¶

在线算法是一类在数据逐步到达时，能够即时处理并给出结果的算法。与离线算法不同，在线算法不能等待所有数据到达后再进行处理，而是需要在每个数据点到达时做出决策。在线算法通常需要在有限的时间和空间内处理数据，因此设计在线算法时需要考虑时间复杂度和空间复杂度的权衡。

有一堆整数，希望找到其中位数。在以下三种情况下设计算法：

第一种情况非常简单。只需要知道这堆数有多少个，然后快速选择算法（见前文）就能在\(O(n)\)时间内找到中位数，这个也可以优化（如BFPRT算法），但写起来比较麻烦，这里就不赘述了。我们主要考虑的是第二种和第三种情况。

第二种情况是经典的“动态中位数查找”问题，虽然不能算是“异步算法”，但思想已经接近了。这个问题的常见方法是“对顶堆”。这种情况也是常见的情况，因为现代计算机的内存通常足够大，能够存储大量数据，但处理速度有限，无法等待所有数据到达后再处理它们。

标题：对顶堆法
输入：流式到达的整数序列
输出：当前已到达整数的中位数
大顶堆max_heap，用于存储较小的一半整数
小顶堆min_heap，用于存储较大的一半整数
for 每个到达的整数$num$:
  if $max_heap$为空或$num \leq max_heap.top()$:
    将num加入max_heap
  else:
    将num加入min_heap
  // 平衡两个堆的大小
  if $max_heap.size() > min_heap.size() + 1$:
    将max_heap的堆顶元素移动到min_heap
  else if $min_heap.size() > max_heap.size()$:
    将min_heap的堆顶元素移动到max_heap
  // 计算当前中位数
  if $max_heap.size() > min_heap.size()$:
    中位数为max_heap.top()
  else:
    中位数为(max_heap.top() + min_heap.top()) / 2

第三种情况就是真正的“异步算法”了。该情况实际上还有很多种变种。

能多次读取数据流¶

这种情况常见于硬盘数据处理。这种情况下，我们能够得到精确的中位数，精短算法是外存选择排序。

标题：外存选择排序法
输入：流式到达的整数序列，内存大小$M$
输出：当前已到达整数的中位数
将数据流分成若干块，每块大小不超过M
for 每块数据:
  将该块数据读入内存并排序
  将排序后的块写回外存
使用归并排序将所有排序后的块合并成一个有序序列
计算中位数并返回

只能读取一次数据流¶

这种情况常见于网络数据处理、传感器数据处理等。这种情况下，我们无法得到精确的中位数，只能得到一个近似值。常见的方法有很多，例如蓄水池抽样法、分桶（直方图）法、Greenwald-Khanna算法等。这里我们介绍分桶法。

标题：分桶法
输入：流式到达的整数序列，桶的数量$k$
输出：当前已到达整数的近似中位数
初始化k个桶，每个桶记录其范围和计数
for 每个到达的整数$num$:
  将num放入对应的桶中，并更新该桶的计数
计算总计数total
计算中位数所在的桶b，使得前b-1个桶的计数之和小于等于total/2且前b个桶的计数之和大于total/2
估计中位数为桶b的范围内的一个值（例如该范围的中点）
return 估计的中位数

由此可见，在线算法通常需要在有限的时间和空间内处理数据，因此设计在线算法时需要考虑时间复杂度和空间复杂度的权衡。此外，在线算法通常只能得到近似解，而无法保证精确解。因此，在设计在线算法时，需要根据具体问题的需求，选择合适的算法和数据结构。