【Princeton】算法(1):Union-Find

【Princeton】算法(1):Union-Find

在计算机科学(CS)中,算法(Algorithm)是描述一种有限、确定、有效,并且适合用计算机语言来实现的解决问题的方法,它是CS领域的基础与核心。

这里先通过一个动态连通性问题,来了解设计、分析算法的基本过程。

动态连通性

问题描述

动态连通性问题的描述如下:问题的输入是一系列的整数对,每个整数都能代表某种对象。当一对整数p、q输入时,则说明p、q所代表的对象是“相连”的。这里假设“相连”是一种等价关系,且相连后有如下几个性质:

  • 自反性:p和p是相连的,q和q是相连的
  • 对称性:q与p也是相连的
  • 传递性:如果q和r相连,则p和r也相连

由相连的对象相互连接组成的最大集合称为连通分量(Connected Components),如下图所示的两个连通分量:

连通分量

要求设计一种数据结构来存储所有输入的整数对之间的连通信息,基于它设计可以高效地连通对象、查询对象的连通性的Union-Find算法。

现实中,解决该问题的算法有广泛的应用范围。例如,用整数对来代表两台计算机,该算法就可以用来判断计算机之间通信线路是否畅通;用整数对来代表两个人,该算法就可以用来判断某个社交软件中多个人之间的朋友关系。

根据问题的要求,为Union-Find算法设置如下几个API:

Union-Find API

完成上述方法的设计后,可用以下用例来检查这些API的正确性:

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
int N = StdIn.readInt();
UF uf = new UF(N);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (!uf.connected(p, q)) {
uf.union(p, q);
StdOut.println(p + " " + q);
}
}
}

Quick-Find算法

Quick-Find算法以数组id[]作为数据结构,一个对象对应数组中的一个索引。该算法的思想,是保证当且仅当id[p]的值等于id[q]时,索引p和q对应的对象才是连通的,也就是说,同一个连通分量中的所有对象在数组id[]中对应的值必须全部相同。如下图所示:

Quick-Find

此时,要实现connected方法,只要由索引值p、q,判断id[p]和id[q]是否相等;find方法只需要返回某个对象在数组id[]中对应的值;而每次执行union方法时,都需要遍历整个数组id[],将已连通的分量全部赋上相同的值。

Quick-Find具体实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class QuickFindUF {
private int[] id;

public QuickFindUF(int N) {
id = new int[N];
for (int i = 0; i < N; i++) // 初始化数组
id[i] = i;
}

public boolean connected(int p, int q) {
return id[p] == id[q];
}

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

public void union(int p, int q) {
int pid = find(p);
int qid = find(q);
if (pid == qid)
return;

for (int i = 0; i < id.length; i++) // 遍历整个数组
if (id[i] == pid)
id[i] = qid;
}
}

Quick-Find中,每执行一次find只访问了一次数组,而执行一次union需要访问$(N+3)$到$(2N+1)$次数组。如果最后只得到一个连通分量,则至少需要调用$N-1$次union,总共至少需要访问$(N+3)(N-1) \sim N^2$次数组。

由此可知,Quick-Find算法的执行过程是平方级别的,面对大量的输入时该算法无法高效进行处理。

Quick-Union算法

Quick-Union主要提高了Quick-Find中union方法的速度。还是以一个数组id[]作为数据结构,但这个数组有了新的含义:一个对象还是对应id[]的一个索引,但id[]中存储的值代表了同一个连通分量中的另一个对象对应的索引值。在这里,id[]用父链接的形式代表了一片森林,且根节点及初始时各对象的链接到其本身。

Quick-Union

如图所示,每个对象都有它的根节点及父节点,3的父节点是4,2、4的父节点是9,而2、3、4的根节点都是9,9的父节点和根节点则是它本身,这样就形成一颗树。由多棵这样的树组成的集合则为森林。

实现该算法,connected方法要做的,就是确定两个对象的根节点的值是否相同;find方法则确定对象的根节点;union方法将两个对象的根节点的值统一。

Quick-Union具体实现为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private class QuickUnionUF {
private int[] id;

public QuickUnionUF(int N) {
id = new int[N];
for (int i = 0; i < N; i ++)
id[i] = i;
}

public int find(int p) {
while (p != id[p])
p = id[p]; // 循环,直到找出根节点
return p;
}

public boolean connected(int p, int q) {
return find(p) == find(q);
}

public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;

id[pRoot] = qRoot;
}
}

Quick-Union算法的成本依赖于输入。最好情况下,find方法只要访问一次数组就能得到它的根节点,而最坏情况下,则需要访问$2N+1$次数组。遇到大型的问题,Quick-Union在部分情况下比Quick-Find快了一些,但极端情况下,id[]中某棵树的高度不断增加,导致find的代价不断变大,此时该算法的性能比Quick-Find还要糟糕。

加权Quick-Union算法

Quick-Union算法的缺点在于一棵树的高度可能不断增长,而导致寻找根节点的代价不断变大。对此可采用的改进方法之一,便是进行加权

加权前后

所谓加权,在原Quick-Union算法的基础上,跟踪每一棵树中对象的个数,确保总是将较小树的根节点作为较大树的子节点,避免将一棵大树连接在小树下面,从而有效缩短树的高度。

要实现加权,只需要另外维护一个数组,来保存各根节点的分量数目,并在union方法增加部分代码,其具体实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class  WeightedQuickUnionUF {
private int[] id;
private int[] sz; // 各根节点对应的分量数目

public WeightedQuickUnionUF(int N) {
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
sz[i] = 1;
}
}

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

public boolean connected(int p, int q) {
return find(p) == find(q);
}

public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);

if (pRoot == qRoot)
return;

if (sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else {
id[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
}

将$N$个对象连结到多棵树上,形成的树中,高度最大为$\log N$。因此在加权Quick-Union中,对N个输入对,union过程最多需要访问$\log N$次数组,find寻找根节点时最多也只需要访问$\log N$次数组。面对大量输入时,该算法的性能就比较能接受了,且该算法实现起来也相对容易。

树的高度

该算法还可以进一步改进:在加权Quick-Union的基础上,进一步进行路径压缩(Path Compression)。在找到某个对象的根节点后,将这个对象的节点直接连接到根节点,这样整个树中节点寻找根节点的路径就能得到极大的压缩。

实际上,为了只添加少量代码,只将每个节点链接到其祖父节点上,虽然这样并没有将树完全展平,但只需要修改find方法中的一行代码,就将树基本展平,效果和完全展平相当。具体的修改如下:

1
2
3
4
5
6
7
public int find(int i) {
while(i != id[i]) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

总结比较一下在N个对象上进行M次Union-Find操作时,以上几种算法的性能:

比较

下面是研究某个问题的算法时,需要遵循的基本步骤:

  1. 完整而详细地定义问题,找出解决问题必需的基本抽象操作,定义一份API;
  2. 简洁地实现一种初级算法,给出一个精心组织的开发用例并使用实际数据作为输入;
  3. 当算法可解决的问题的最大规模达不到预期时,决定改进还是放弃该算法;
  4. 逐步改进实现算法,并通过经验性分析或数学分析验证改进后的效果;
  5. 用更高层次的抽象表示数据结构或算法来设计更高级的改进版本;
  6. 尽量为最坏情况下的性能提供保证,且处理普通数据时也要有良好的性能。

算法分析

编写好的程序将会运行多长的时间,将会占用多大的内存,这都是经常需要考虑的问题。对此,需要采用一些科学的方法,对一个算法的性能好坏作出大致的分析预测,了解最坏情况下算法性能的下界,避免程序出现性能瓶颈。

《计算机程序设计艺术》的作者D.E.Knuth认为,尽管有许多复杂的因素影响着程序的运行时间,原则上还是可以构建出一个数学模型来描述任意程序的运行时间。他的基本见解是,一个程序运行的总时间主要与:

  • 执行每条语句和耗时
  • 执行每条语句的频率
    这两点有关,前者取决于计算机、编译器和操作系统,后者就取决于我们所编写的程序的本身和输入。

程序中执行最频繁的指令,往往决定了程序执行的总时间。例如,下面的程序可用来统计某个文件中所有和为$0$的三个整数的数量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public calss ThreeSUM {
public staic int count(int[] a) {
int N = a.length;
int count = 0;
for (int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
for(int k = j+1; k < N; k++)
if(a[i] + a[j] + a[k] == 0)
count++;
return count;
}

public static void main(String[] args) {
int[] a = In.readInts(args[0]);
StdOut.println(count(a));
}
}

分析可知,对于大量的输入,3-SUM程序中执行次数最多的将是if语句,且执行次数为:$$g(N) = C_N^3 = \frac{N(N-1)(N-2)}{6} = \frac{N^3}{6} - \frac{N^2}{2} + \frac{N}{3} $$。

表达式中,其他项相比首项都要小很多,于是可以用$g(N) \sim af(N)$的近似方式,忽略较小的项以简化式子,同时以此对算法的开销作大致衡量。其中$f(N)$称为$g(N)$的增长数量级,$a$用来进一步修正偏差,它的值取决于计算机的具体型号。那么对上例即有:$$g(N) \sim \frac16 N^3$$

对程序中执行最为频繁的语句,其执行次数$g(N)$的增长数量级$f(N)$可用来表示程序运行时间的增长数量级。在分析各种算法性能的过程中,常遇到的增长数量级有下面几类:

函数

使用二分查找(Binary Search)来解决前面的3-SUM问题,其增长数量级能够从$N^3$降到$N^2 \log N$。

除了算法的增长阶数外,不同的输入模型也会造成算性能的剧烈变化。因此在进行算法分析时,常需要考虑一个算法运行时间的最好情况最坏情况。最好情况是算法代价的下界(low bound),程序运行的时间总是大于等于该值,最坏情况是算法代价的上界(upper bound,程序运行的时间总是小于等于该值。综合两种情况,就可以得到用以衡量一般情况的算法的平均性能。

常用$\Theta$、$O$和$\Omega$这几个符号来描述性能的界限:

三个符号

  • $O$用以描述算法性能的渐进上界,例如$O(N^2)$就表示N增长时,程序运行时间小于某个常数乘以$N^2$
  • $\Omega$用以描述最坏情况下的性能下限,例如$\Omega(N^2)$就表示N增长时,程序运行时间比某个常数乘以$N^2$要大
  • $\Theta$用以表示增长阶数,如$\Theta(N^2)$就是某个常数乘以$N^2$的简写

参考资料

  1. Algorithms-Coursera
  2. 算法(第四版)

Tip:本文涉及的图片及资料均整理翻译自普林斯顿大学的Robert Sedgewick教授在Coursera上讲授的的Algorithms课程以及他撰写的配套书籍的《算法(第四版)》,版权归其所有。翻译整理水平有限,如有不妥的地方欢迎指出。


更新历史:

  • 2017.11.15 完成初稿
  • 2018.02.16 内容更新
  • 2019.01.03 修改部分内容
  • 2019.03.25 修改部分内容
  • 2019.07.18 修改、补充内容

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×