union-find(并查集)算法

union-find(并查集)算法

Scroll Down

本文引用了算法(第四版)这本书进行分析

动态连通性

首先我们详细地说明一下问题:问题的输入是一列整数对,其中每个整数都表示一个某种类型的对象,一对整数 p q 可以被理解为“pq 是相连的”。我们假设“相连”是一种等价关系,这也就意味着它具有:

  • 自反性pp 是相连的;
  • 对称性:如果pq 是相连的,那么qp 也是相连的;
  • 传递性:如果 pq 是相连的且 qr 是相连的,那么 pr 也是相连的。

等价关系能够将对象分为多个等价类。在这里,当且仅当两个对象相连时它们才属于同一个等价类。我们的目标是编写一个程序来过滤掉序列中所有无意义的整数对(两个整数均来自于同一个等价类中)。换句话说,当程序从输入中读取了整数对 p q 时,如果已知的所有整数对都不能说明 pq 是相连的,那么则将这一对整数写入到输出中。如果已知的数据可以说明pq 是相连的,那么程序应该忽略 p q 这对整数并继续处理输入中的下一对整数。图 1.5.1 用一个例子说明了这个过程。为了达到所期望的效果,我们需要设计一个数据结构来保存程序已知的所有整数对的足够多的信息,并用它们来判断一对新对象是否是相连的。我们将这个问题通俗地叫做动态连通性问题。这个问题可能有以下应用。

05.d01z.061.png

图 1.5.1 动态连通性问题

网络

输入中的整数表示的可能是一个大型计算机网络中的计算机,而整数对则表示网络中的连接。这个程序能够判定我们是否需要在 pq 之间架设一条新的连接才能进行通信,或是我们可以通过已有的连接在两者之间建立通信线路;或者这些整数表示的可能是电子电路中的触点,而整数对表示的是连接触点之间的电路;或者这些整数表示的可能是社交网络中的人,而整数对表示的是朋友关系。在此类应用中,我们可能需要处理数百万的对象和数十亿的连接。

变量名等价性

某些编程环境允许声明两个等价的变量名(指向同一个对象的多个引用)。在一系列这样的声明之后,系统需要能够判别两个给定的变量名是否等价。这种较早出现的应用(如 FORTRAN 语言)推动了我们即将讨论的算法的发展。

数学集合

在更高的抽象层次上,可以将输入的所有整数看做属于不同的数学集合。在处理一个整数对 p q 时,我们是在判断它们是否属于相同的集合。如果不是,我们会将 p 所属的集合和 q 所属的集合归并到同一个集合。

为了进一步限定话题,我们会在本节以下内容中使用网络方面的术语,将对象称为触点,将整数对称为连接,将等价类称为连通分量或是简称分量。简单起见,假设我们有用 0 到gif.gif的整数所表示的gif1.gif个触点。这样做并不会降低算法的通用性,因为我们在第 3 章中将会学习一组高效的算法,将整数标识符和任意名称关联起来。

图 1.5.2 是一个较大的例子,意在说明连通性问题的难度。你很快就可以找到图左侧中部一个只含有一个触点的分量,以及左下方一个含有 5 个触点的分量,但让你验证其他所有触点是否都是相互连通的可能就有些困难了。对于程序来说,这个任务更加困难,因为它所处理的只有触点的名字和连接而并不知道触点在图像中的几何位置。我们如何才能快速知道这种网络中任意给定的两个触点是否相连呢?

05.d01z.062.png

图 1.5.2 中等规模的连通性问题举例(625 个触点,900 条边,3 个连通分量)

我们在设计算法时面对的第一个任务就是精确地定义问题。我们希望算法解决的问题越大,它完成任务所需的时间和空间可能就越多。我们不可能预先知道这其间的量化关系,而且我们通常只会在发现解决问题很困难,或是代价巨大,或是在幸运地发现算法所提供的信息比原问题所需要的更加有用时修改问题。例如,连通性问题只要求我们的程序能够判别给定的整数对 p q 是否相连,但并没有要求给出两者之间的通路上的所有连接。这样的要求会使问题更加困难,并得到另一组不同的算法,我们会在 4.1 节中学习它们。

为了说明问题,我们设计了一份 API 来封装所需的基本操作:初始化、连接两个触点、判断包含某个触点的分量、判断两个触点是否存在于同一个分量之中以及返回所有分量的数量。详细的 API 如表 1.5.1 所示。

表 1.5.1 union-find 算法的 API

|public class UF |
| --- | --- | --- |
| UF(int N) | 以整数标识(0 到 null)初始化 null 个触点 |
| void union(int p, int q) | 在 pq 之间添加一条连接 |
| int find(int p) | p(0 到 gif.gif所在的分量的标识符 |
| boolean connected(int p, int q) | 如果 pq 存在于同一个分量中则返回 true |
| int count() | 连通分量的数量|

如果两个触点在不同的分量中,union() 操作会将两个分量归并。find() 操作会返回给定触点所在的连通分量的标识符。connected() 操作能够判断两个触点是否存在于同一个分量之中。count() 方法会返回所有连通分量的数量。一开始我们有 N个分量,将两个分量归并的每次 union() 操作都会使分量总数减一。

我们马上就将看到,为解决动态连通性问题设计算法的任务转化为了实现这份 API。所有的实现都应该:

  • 定义一种数据结构表示已知的连接;
  • 基于此数据结构实现高效的 union()find()connected()count() 方法。

众所周知,数据结构的性质将直接影响到算法的效率,因此数据结构和算法的设计是紧密相关的。API 已经说明触点和分量都会用 int 值表示,所以我们可以用一个以触点为索引的数组id[] 作为基本数据结构来表示所有分量。我们将使用分量中的某个触点的名称作为分量的标识符,因此你可以认为每个分量都是由它的触点之一所表示的。一开始,我们有 N 个分量,每个触点都构成了一个只含有它自己的分量,因此我们将id[i] 的值初始化为 i,其中 i0N-1 之间。对于每个触点 i,我们将 find() 方法用来判定它所在的分量所需的信息保存在 id[i] 之中。connected() 方法的实现只用一条语句 find(p) == find(q),它返回一个布尔值,我们在所有方法的实现中都会用到 connected() 方法。

总之,我们的起点就是算法 1.5。我们维护了两个实例变量,一个是连通分量的个数,一个是数组id[]find()union() 的实现是本节剩余内容将要讨论的主题。

算法 1.5 union-find 的实现

public class UF
{
   private int[] id;     // 分量id(以触点作为索引)
   private int count;    // 分量数量
   public UF(int N)
   {  // 初始化分量id数组
      count = N;
      id = new int[N];
      for (int i = 0; i < N; i++)
         id[i] = i;
   }
   public int count()
   {  return count;  }
   public boolean connected(int p, int q)
   {  return find(p) == find(q);  }
   public int  find(int p)
   public void union(int p, int q)
   // 请见1.5.2.1节用例(quick-find)、1.5.2.3节用例(quick-union)和算法1.5(加权quick-union)
   public static void main(String[] args)
   {  // 解决由StdIn得到的动态连通性问题
      int N = StdIn.readInt();              // 读取触点数量
      UF uf = new UF(N);                    // 初始化N个分量
      while (!StdIn.isEmpty())
      {
         int p = StdIn.readInt();
         int q = StdIn.readInt();           // 读取整数对
         if (uf.connected(p, q)) continue;  // 如果已经连通则忽略
         uf.union(p, q);                    // 归并分量
         StdOut.println(p + " " + q);      // 打印连接
      }
      StdOut.println(uf.count() + "components");
   }
}
% java UF < tinyUF.txt
4 3
3 8
6 5
9 4
2 1
5 0
7 2
6 1
2 components

这份代码是我们对 UF 的实现。它维护了一个整型数组 id[],使得 find() 对于处在同一个连通分量中的触点均返回相同的整数值。union() 方法必须保证这一点。

为了测试 API 的可用性并方便开发,我们在 main() 方法中包含了一个用例用于解决动态连通性问题。它会从输入中读取 N 值以及一系列整数对,并对每一对整数调用 connected() 方法:如果某一对整数中的两个触点已经连通,程序会继续处理下一对数据;如果不连通,程序会调用 union() 方法并打印这对整数。在讨论实现之前,我们也准备了一些测试数据(如右侧的代码框所示):文件 tinyUF.txt 含有 10 个触点和 11 条连接,图 1.5.1 使用的就是它;文件 mediumUF.txt 含有 625 个触点和 900 条连接,如图 1.5.2 所示;例子文件 largeUF.txt 含有 100 万个触点和 200 万条连接。我们的目标是在可以接受的时间范围内处理和 largeUF.txt 规模类似的输入。

% more tinyUF.txt
10
4 3
3 8
6 5
9 4
2 1
8 9
5 0
7 2
6 1
1 0
6 7

% more mediumUF.txt
625
528 503
548 523
...
900条连接

% more largeUF.txt
1000000
786321 134521
696834 98245
...
200万条连接

为了分析算法,我们将重点放在不同算法访问任意数组元素的总次数上。我们这样做相当于隐式地猜测各种算法在一台特定的计算机上的运行时间在这个量乘以某个常数的范围之内。这个猜想基于代码,用实验验证它并不困难。我们将会看到,这个猜想是算法比较的一个很好的开始。

union-find 的成本模型。在研究实现 union-find 的 API 的各种算法时,我们统计的是数组的访问次数(访问任意数组元素的次数,无论读写)。

实现

quick-find 算法

一种方法是保证当且仅当 id[p] 等于 id[q]pq 是连通的。换句话说,在同一个连通分量中的所有触点在 id[] 中的值必须全部相同。这意味着 connected(p, q) 只需要判断 id[p] == id[q],当且仅当pq 在同一连通分量中该语句才会返回true。为了调用union(p, q) 确保这一点,我们首先要检查它们是否已经存在于同一个连通分量之中。如果是我们就不需要采取任何行动,否则我们面对的情况就是 p 所在的连通分量中的所有触点的id[] 值均为同一个值,而 q 所在的连通分量中的所有触点的 id[] 值均为另一个值。要将两个分量合二为一,我们必须将两个集合中所有触点所对应的id[] 元素变为同一个值,如表 1.5.2 所示。为此,我们需要遍历整个数组,将所有和 id[p] 相等的元素的值变为 id[q] 的值。我们也可以将所有和 id[q] 相等的元素的值变为 id[p] 的值——两者皆可。根据上述文字得到的find()union() 的代码简单明了,如下面的代码框所示。图 1.5.3 显示的是我们的开发用例在处理测试数据 tinyUF.txt 时的完整轨迹。

public int find(int p)
{  return id[p];  }

public void union(int p, int q)
{  // 将p和q归并到相同的分量中
   int pID = find(p);
   int qID = find(q);

   // 如果p和q已经在相同的分量之中则不需要采取任何行动
   if (pID == qID) return;

   // 将p的分量重命名为q的名称
   for (int i = 0; i < id.length; i++)
       if (id[i] == pID) id[i] = qID;
   count--;
}

quick-find

表 1.5.2 quick-find 概览

05.d01z.063.png

05.d01z.064.png

图 1.5.3 quick-find 的轨迹

quick-find 算法的分析

find() 操作的速度显然是很快的,因为它只需要访问 id[] 数组一次。但 quick-find 算法一般无法处理大型问题,因为对于每一对输入 union() 都需要扫描整个 id[] 数组。

命题 F。在 quick-find 算法中,每次 find() 调用只需要访问数组一次,而归并两个分量的 union() 操作访问数组的次数在 N+32N+1之间。

证明。由代码马上可以知道,每次 connected() 调用都会检查 id[] 数组中的两个元素是否相等,即会调用两次 find() 方法。归并两个分量的 union() 操作会调用两次 find(),检查 id[] 数组中的全部N元素并改变它们中 1 到N-1个元素的值。

假设我们使用 quick-find 算法来解决动态连通性问题并且最后只得到了一个连通分量,那么这至少需要调用**N-1 **次union(),即至少 (N-1)*(N+3)~N^2次数组访问——我们马上可以猜想动态连通性的 quick-find 算法是平方级别的。将这种分析推广我们可以得到,quick-find 算法的运行时间对于最终只能得到少数连通分量的一般应用是平方级别的。在计算机上用倍率测试可以很容易验证这个猜想(指导性的例子请见练习 1.5.23)。现代计算机每秒钟能够执行数亿甚至数十亿条指令,因此如果 N 较小的话这个成本并不是很明显。但是在现代应用中我们也很可能需要处理几百万甚至数十亿的触点和连接,例如我们的测试文件 largeUF.txt。如果你还不相信并且觉得自己的计算机足够快,请使用 quick-find 算法找出largeUF.txt 中所有整数对所表示的连通分量的数量。结论无可争议,使用 quick-find 算法解决这种问题是不可行的,我们需要寻找更好的算法。

quick-union 算法

我们要讨论的下一个算法的重点是提高 union() 方法的速度,它和 quick-find 算法是互补的。它也基于相同的数据结构——以触点作为索引的 id[] 数组,但我们赋予这些值的意义不同,我们需要用它们来定义更加复杂的结构。确切地说,每个触点所对应的 id[] 元素都是同一个分量中的另一个触点的名称(也可能是它自己)——我们将这种联系称为链接。在实现 find() 方法时,我们从给定的触点开始,由它的链接得到另一个触点,再由这个触点的链接到达第三个触点,如此继续跟随着链接直到到达一个根触点,即链接指向自己的触点(你将会看到,这样一个触点必然存在)。当且仅当分别由两个触点开始的这个过程到达了同一个根触点时它们存在于同一个连通分量之中。为了保证这个过程的有效性,我们需要union(p, q) 来保证这一点。它的实现很简单:我们由 pq 的链接分别找到它们的根触点,然后只需将一个根触点链接到另一个即可将一个分量重命名为另一个分量,因此这个算法叫做 quick-union。和刚才一样,无论是重命名含有 p 的分量还是重命名含有 q 的分量都可以,右侧的这段实现重命名了 p 所在的分量。图 1.5.5 显示了 quick-union 算法在处理 tinyUF.txt 时的轨迹。图 1.5.4 能够很好地说明图 1.5.5(见 1.5.2.4 节)中的轨迹,我们接下来要讨论的就是它。

private int find(int p)
{  // 找出分量的名称
   while (p != id[p]) p = id[p];
   return p;
}

public void union(int p, int q)
{  // 将p和q的根节点统一
   int pRoot = find(p);
   int qRoot = find(q);
   if (pRoot == qRoot) return;

   id[pRoot] = qRoot;

   count--;
}

quick-union

QQ截图20190724171330.png

图 1.5.4 quick-union 算法概述

森林的表示

quick-union 算法的代码很简洁,但有些难以理解。用节点(带标签的圆圈)表示触点,用从一个节点到另一个节点的箭头表示链接,由此得到数据结构的图像表示使我们理解算法的操作变得相对容易。我们的得到的结构是——从技术上来说,id[] 数组用父链接的形式表示了一片森林。为了简化图表,我们常常会省略链接的箭头(因为它们的指向全部朝上)和树的根节点中指向自己的链接。tinyUF.txt 的id[] 数组所对应的森林如图1.5.5 所示。无论我们从任何触点所对应的节点开始跟随链接,最终都将达到含有该节点的树的根节点。可以用归纳法证明这个性质的正确性:在数组被初始化之后,每个节点的链接都指向它自己;如果在某次union() 操作之前这条性质成立,那么操作之后它必然也成立。因此,quick-union 中的find() 方法能够返回根节点所对应的触点的名称(这样connected() 才能够判定两个触点是否在同一棵树中)。这种表示方法对于这个问题很实用,因为当且仅当两个触点存在于相同的分量之中时它们对应的节点才会在同一棵树中。另外,构造树并不困难:quick-union 中union() 的实现只用了一条语句就将一个根节点变为另一个根节点的父节点,从而归并了两棵树。

QQ截图20190724171330.png

图 1.5.5 quick-union 算法的轨迹(以及相应的森林)

quick-union 算法的分析

quick-union 算法看起来比 quick-find 算法更快,因为它不需要为每对输入遍历整个数组。但它能够快多少呢?分析 quick-union 算法的成本比分析 quick-find 算法的成本更困难,因为这依赖于输入的特点。在最好的情况下,find() 只需要访问数组一次就能够得到一个触点所在的分量的标识符;而在最坏情况下,这需要2N+1次数组访问,如图 1.5.6 中的 0 触点(这个估计是较为保守的,因为 while 循环中经过编译的代码对 id[p] 的第二次引用一般都不会访问数组)。由此我们不难构造一个最佳情况的输入使得解决动态连通性问题的用例的运行时间是线性级别的;另一方面,我们也可以构造一个最坏情况的输入,此时它的运行时间是平方级别的(请见图 1.5.6 和下面的命题 G)。幸好我们不需要面对分析 quick-union 算法的问题,我们也不会仔细对比 quick-union 算法和quick-find 算法的性能,因为我们下面将会学习一种比两者的效率都高得多的算法。目前,我们可以将 quick-union 算法看做是 quick-find 算法的一种改良,因为它解决了 quick-find 算法中最主要的问题(union() 操作总是线性级别的)。对于一般的输入数据这个变化显然是一次改进,但 quick-union 算法仍然存在问题,我们不能保证在所有情况下它都能比 quick-find 算法快得多(对于某些输入,quick-union 算法并不比 quick-find 算法快)。

定义。一棵树的大小是它的节点的数量。树中的一个节点的深度是它到根节点的路径上的链接数。树的高度是它的所有节点中的最大深度。

命题 G。quick-union 算法中的 find() 方法访问数组的次数为 1 加上给定触点所对应的节点的深度的两倍。union()connected() 访问数组的次数为两次 find() 操作(如果 union() 中给定的两个触点分别存在于不同的树中则还需要加 1)。

证明。请见代码。

同样,假设我们使用quick-union 算法解决了动态连通性问题并最终只得到了一个分量,由命题 G 我们马上可以知道算法的运行时间在最坏情况下是平方级别的。假设输入的整数对是有序的 0-1、0-2、0-3 等,N-1对之后我们的 N个触点将全部处于相同的集合之中且由quick-union 算法得到的树的高度为 N-1,其中 0 链接到 1,1 链接到 2,2 链接到 3,如此下去(请见图 1.5.6)。由命题 G 可知,对于整数对 0-i,union() 操作访问数组的次数为2i+1(触点 0 的深度为 i-1,触点i的深度为 0)。因此,处理N 对整数所需的所有find() 操作访问数组的总次数为3+5+6+........(2N-1)~N^2

QQ截图20190724171330.png

图 1.5.6 quick-union 算法的最坏情况

加权 quick-union 算法

幸好,我们只需简单地修改 quick-union 算法就能保证像这样的糟糕情况不再出现。与其在 union() 中随意将一棵树连接到另一棵树,我们现在会记录每一棵树的大小并总是将较小的树连接到较大的树上。这项改动需要添加一个数组和一些代码来记录树中的节点数,如算法 1.5 所示,但它能够大大改进算法的效率。我们将它称为加权 quick-union 算法(如图 1.5.7 所示)。该算法在处理 tinyUF.txt 时构造的森林如图 1.5.8 中左侧的图所示。即使对于这个较小的例子,该算法构造的树的高度也远远小于未加权的版本所构造的树的高度。

QQ截图20190724171330.png

图 1.5.7 加权 quick-union

加权 quick-union 算法的分析

图 1.5.8 显示了加权 quick-union 算法的最坏情况。其中将要被归并的树的大小总是相等的(且总是 2 的幂)。这些树的结构看起来很复杂,但它们均含有2^n个节点,因此高度都正好是n。另外,当我们归并两个含有 2^n 个节点的树时,我们得到的树含有 2^n+1 个节点,由此将树的高度增加到了 n+1。由此推广我们可以证明加权 quick-union 算法能够保证对数级别的性能。加权 quick-union 算法的实现如算法 1.5 所示。

% java WeightedQuickUnionUF < mediumUF.txt
528 503
548 523
...
3 components

% java WeightedQuickUnionUF < largeUF.txt
786321 134521
696834 98245
...
6 components

QQ截图20190724171330.png

图 1.5.8 加权 quick-union 算法的轨迹(森林)

算法 1.5(续) union-find 算法的实现(加权 quick-union 算法)

QQ截图20190724171330.png

根据正文所述的森林表示方法这段代码很容易理解。我们加入了一个由触点索引的实例变量数组 sz[],这样union() 就可以将小树的根节点连接到大树的根节点。这使得算法能够处理规模较大的问题。

命题 H。对于 N 个触点,加权 quick-union 算法构造的森林中的任意节点的深度最多为lgN

证明。我们可以用归纳法证明一个更强的命题,即森林中大小为k的树的高度最多为 lgk。在原始情况下,当 k 等于 1 时树的高度为 0。根据归纳法,我们假设大小为i 的树的高度最多为 lgi,其中 i<k。设i<=ji+j=k,当我们将大小为 i和大小为 j 的树归并时,quick-union 算法和加权 quick-union 算法中触点与深度示例如图 1.5.9 所示。小树中的所有节点的深度增加了 1,但它们现在所在的树的大小为 i+j=k,而 1+lgi=lg(i+i)<=lg(i+j)=lgk,性质成立。

QQ截图20190724171330.png

图 1.5.9 quick-union 算法与加权 quick-union 算法的对比(100 个触点,88 次 union() 操作)

推论。对于加权 quick-union 算法和 N 个触点,在最坏情况下 find()connected()union() 的成本的增长数量级为logN

证明。在森林中,对于从一个节点到它的根节点的路径上的每个节点,每种操作最多都只会访问数组常数次。

对于动态连通性问题,命题H 和它的推论的实际意义在于加权quick-union 算法是三种算法中唯一可以用于解决大型实际问题的算法。加权quick-union 算法处理N个触点和 M 条连接时最多访问数组 cMlgN 次,其中c 为常数。这个结果和 quick-find 算法(以及某些情况下的quick-union 算法)需要访问数组至少MN 次形成了鲜明的对比。因此,有了加权quick-union 算法我们就能保证能够在合理的时间范围内解决实际中的大规模动态连通性问题。只需要多写几行代码,我们所得到的程序在处理实际应用中的大型动态连通性问题时就会比简单的算法快数百万倍。

图 1.5.9 显示的是一个含有 100 个触点的例子。从图中我们可以很明显地看到,加权 quick-union 算法中远离根节点的节点相对较少。事实上,只含有一个节点的树被归并到更大的树中的情况很常见,这样该节点到根节点的距离也只有一条链接而已。针对大规模问题的经验性研究告诉我们,加权 quick-union 算法在解决实际问题时一般都能在常数时间内完成每个操作(如表 1.5.3 所示)。我们可能很难找到比它效率更高的算法了。

表 1.5.3 各种 union-find 算法的性能特点

| 算法 | 存在 null 个触点时成本的增长数量级(最坏情况下) |
| --- | --- | --- | --- |
| 构造函数 | union() | find() |
| quick-find 算法 | N | N | 1 |
| quick-union 算法 | N | 树的高度 | 树的高度 |
| 加权 quick-union 算法 | N | lgN | lgN |
| 使用路径压缩的加权 quick-union 算法 | N | 非常非常地接近但仍没有达到(请见练习 1.5.13) | 1(均摊成本) |
| 理想情况 | N | 1 | 1 |

最优算法

们可以找到一种能够保证在常数时间内完成各种操作的算法吗?这个问题非常困难并且困扰了研究者们许多年。在寻找答案的过程中,大家研究了 quick-union 算法和加权 quick-union 算法的各种变体。例如,下面这种路径压缩方法很容易实现。理想情况下,我们希望每个节点都直接链接到它的根节点上,但我们又不想像 quick-find 算法那样通过修改大量链接做到这一点。我们接近这种理想状态的方式很简单,就是在检查节点的同时将它们直接链接到根节点。这种方法乍一看很激进,但它的实现非常容易,而且这些树并没有阻止我们进行这种修改的特殊结构:如果这么做能够改进算法的效率,我们就应该实现它。要实现路径压缩,只需要为find() 添加一个循环,将在路径上遇到的所有节点都直接链接到根节点。我们所得到的结果是几乎完全扁平化的树,它和 quick-find 算法理想情况下所得到的树非常接近。这种方法即简单又有效,但在实际情况下已经不太可能对加权 quick-union 算法继续进行任何改进了(请见练习 1.5.24)。对该情况的理论研究结果非常复杂也值得我们注意:路径压缩的加权 quick-union 算法是最优的算法,但并非所有操作都能在常数时间内完成。也就是说,使用路径压缩的加权 quick-union 算法的每个操作在在最坏情况下(即均摊后)都不是常数级别的,而且不存在其他算法能够保证 union-find 算法的所有操作在均摊后都是常数级别的(在非常一般的 cell probe 模型之下)。使用路径压缩的加权 quick-union 算法已经是我们对于这个问题能够给出的最优解了。

均摊成本的图像

与对其他任何数据结构实现的讨论一样,我们应该按照 1.4 节中的讨论在实验中用典型的用例验证我们对算法性能的猜想。图 1.5.10 详细显示了我们的动态连通性问题的开发用例在使用各种算法处理一份含有 625 个触点的样例数据(mediumUF.txt)时的性能。绘制这种图像很简单(请见练习 1.5.16):在处理第 i 个连接时,用一个变量 cost 记录其间访问数组(id[]sz[])的次数,并用一个变量 total 记录到目前为止数组访问的总次数。我们在 (i, cost) 处画一个灰点,在 (i, total/i) 处画一个红点,红点表示的是每个操作的平均成本,即均摊成本。图像能够帮助我们更好地理解算法的行为。对于 quick-find 算法,每次 union() 操作都至少访问数组 625 次(每归并一个分量还要加 1,最多再加 625),每次 connected() 操作都访问数组 2 次。一开始,大多数连接都会产生一个 union() 调用,因此累计平均值徘徊在 625 左右;后来,大多数连接产生的 connected() 调用会跳过 union(),因此累计平均值开始下降,但仍保持了相对较高的水平(能够产生大量 connected() 调用并跳过 union()的输入性能要好得多,例子请见练习 1.5.23)。对于 quick-union 算法,所有的操作在初始阶段访问数组的次数都不多;到了后期,树的高度成为一个重要因素,均摊成本的增长很明显。对于加权 quick-union 算法,树的高度一直很小,没有任何昂贵的操作,均摊成本也很低。这些实验验证了我们的结论,显然非常有必要实现加权 quick-union 算法,在解决实际问题时已经没有多少进一步改进的空间了。

QQ截图20190724171330.png

图 1.5.10 所有操作的总成本(625 个触点)

展望

直观感觉上,我们学习的每种 UF 的实现都改进了上一个版本的实现,但这个过程并不突兀,因为我们可以总结学者们对这些算法多年的研究。我们很明确地说明了问题,解决方法的实现也很简单,因此可以用经验性的数据评估各个算法的优劣。另外,还可以通过这些研究验证将算法的性能量化的数学结论。只要可能,我们在本书中研究各种基础问题时都会遵循类似于本节中讨论union-find 问题时的基本步骤,在这里我们要再次强调它们。

  • 完整而详细地定义问题,找出解决问题所必需的基本抽象操作并定义一份 API。
  • 简洁地实现一种初级算法,给出一个精心组织的开发用例并使用实际数据作为输入。
  • 当实现所能解决的问题的最大规模达不到期望时决定改进还是放弃。
  • 逐步改进实现,通过经验性分析或(和)数学分析验证改进后的效果。
  • 用更高层次的抽象表示数据结构或算法来设计更高级的改进版本。
  • 如果可能尽量为最坏情况下的性能提供保证,但在处理普通数据时也要有良好的性能。
  • 在适当的时候将更细致的深入研究留给有经验的研究者并继续解决下一个问题。

我们从 union-find 问题中可以看到,算法设计在解决实际问题时能够为程序的性能带来惊人的提高,这种潜力使它成为热门研究领域。还有什么其他类型的设计行为可能将成本降为原来的数百万甚至数十亿分之一呢?

设计高效的算法是一种很有成就感的智力活动,同时也能够产生直接的实际效益。正如动态连通性问题所示,为解决一个简单的问题我们学习了许多算法,它们不但有用有趣,也精巧而引人入胜。我们还将遇到许多新颖独特的算法,它们都是人们在数十年以来为解决许多实际问题而发明的。随着计算机算法在科学和商业领域的应用范围越来越广,能够使用高效的算法来解决老问题并为新问题开发有效的解决方案也越来越重要了。

支付宝 微信