算法(1):Union-Find

编写一段计算机程序一般都是实现一种已有的方法来解决某个问题,这种方法适用于各种计算机及编程语言。在计算机科学(Computer Science,CS)领域,用算法(Algorithm)这个词来描述一种有限、确定、有效的并适合用计算机语言来实现的解决问题的方法。

算法是CS的基础,也是这个领域研究的核心。

动态连通性

动态连通性问题是:有一组共N个对象,用0到N的数字来标记它们,两个对象间可以是相连的。假设有一个方法union,可以用来连接两个对象,则将两个对象传入这个方法,这两个对象就相连了。这里假设“相连”是一种等价关系,两个对象p与q相连后有:

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

一些对象和连接组成的集合可分裂为连通分量(Connected Components),连通分量是相互连接的对象组成的最大集合。

动态连通问题的关键在于,找到一个适用于大量对象的高效union方法,并实现它们之间的连通性的查询,即查询两个对象之间是否有连通的路径存在。
查询

如图所示,connected是一个用来查询两个对象的连通性的方法,其中0和7未连通,而8和9是连通的。对大量对象执行这些方法时,就需要有一个高效的算法,来解决这个问题。

此问题的算法可以应用到各种各样的对象上。在数码照片上,应用对象是可以照片上的每一个像素点;在计算机网络上,应用的对象可以是每一台计算机;在社交网络上,应用的对象可以是每一个人。

这里将用以解决该问题的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
29
//Quick-Find
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;
}
}

对N个对象进行N次union操作,Quick-Find的初始化过程需要访问N次数组,执行一次union需要访问N次数组,一次find只访问了一次数组,总共要进行$N^2$次的数组访问,平方量级的执行过程过于缓慢,遇到大型问题时无法高效处理。

Quick-Union算法

Quick-Union算法在于提高Quick-Find中union方法的速度。还是用以一个数组id[]作为数据结构,但这个数组有了新的含义。将数组看作一组树即一片森林,其中的每一个对象刚开始都是一棵树,数组中每个对象的值,代表该对象的父节点的索引值。

Quick-Union

如图所示,每个对象都有它的根节点及父节点,3的父节点索引是4,4的父节点索引是9,2的父节点索引也是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
29
//Quick-Union
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算法,对N个对象,初始化过程需要访问N次数组,union过程寻找根节点要访问N+次数组,find寻找根节点时也可能需要访问N次数组。对大型问题,Quick-Union在部分情况下比Quick-Find快了一些,但极端情况下可能比Quick-Find还糟糕。

加权Quick-Union算法

Quick-Union算法的缺点在于一棵树会不断增长,而使寻找某个对象的根节点的代价变大,最糟糕情况下可能要遍历整棵树才能找到某个对象的根节点。对此改进的方法之一,就是进行加权。

加权,是在Quick-Union算法中,跟踪每一棵树中对象的个数,确保总是将小树的根节点作为大树根节点的子节点,避免将一棵大树放在小树下面,这样就能有效缩短树的高度。

加权Quick-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
29
30
31
32
33
34
35
36
37
38
39
40
41
//Weighted Quick-Union
public class WeightedQuickUnionUF {
private int[] id;
private int[] sz;

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

sz = new int[N];
for (int i = 0; i < N; 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];
}
}
}

加权Quick-Union算法中,N个对象连接在一棵树上,形成的树的最大高度为$\lg\ N$。对N个对象,初始化过程需要访问N次数组,union过程需要访问$\lg\ N+$次数组,find寻找根节点时最多也只需要访问$\lg N$次数组。面对大型问题时,该算法的性能就比较能接受了,实现起来相对容易。而这个算法也还可以改进一些。

在加权Quick-Union的基础上再进行路径压缩是很容易实现的。理想情况下,希望每个对象节点都直接连接到根节点上,可以在找到某个对象的根节点后,将这个对象的节点直接连接在根节点上,这样整个树的路径就进行了极大的压缩。

实际上,为了只添加少量代码,我们只将每个节点指向它路径上的祖父节点,这样并没有将树完全展平,具体实现是将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个对象,如表所示,几种算法的性能往下越来越好。

算法分析

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

被誉为CS圣经之一的《计算机程序设计艺术》的作者D.E.Knuth认为,尽管有许多复杂的因素影响着程序的运行时间,原则上还是可以构建出一个数学模型来描述任意程序的运行时间。他的基本见解是,一个程序运行的总时间主要与执行每条语句和耗时、执行每条语句的频率这两点有关,前者取决于计算机、编译器和操作系统,而后者就取决于程序的本身和输入。

以下是一个叫3-SUM的程序:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//3-SUM
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));
}
}

它可以用来统计一个文本文件里所有和为0的三个整数的数量。其中if语句的执行次数为:$$\frac{N(N-1)(N-2)}{6} = \frac{N^3}{6} - \frac{N^2}{2} + \frac{N}{3} $$

以上表达式中,首项之后的其他项都比首项小了很多,于是用约等于号(~)来忽略这些较小的项,以此简化式子。上式就近似为$~\frac{N^3}{6}$,以这种近似模型来对程序的开销作出大致的衡量。

算法分析过程中,一般不会遇到太多不同的函数,因此可对算法的增长阶数进行分类。常遇到的增长阶数有下面几种:

函数

当一个算法的近似模型为以上的值时,由数学知识可知,该算法的开销从上到下依次递增。对上面的3-SUM问题,使用二分查找法来解决的话,能将程序的运行时间增长数量级从$N^3$降到$N^2 \log N$。

除对增长阶数分类外,不用的输入也会使算法的性能发生剧烈的变化,所以在进行算法分析时,也得考虑一个算法运行时间的最好情况和最坏情况。最好情况是算法代价的下限,程序运行的时间总是大于等于它,最坏情况是算法代价的上界,程序运行的时间不会长于它,两种情况综合起来可以得到用以衡量一般情况下的平均性能。

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

三个记号

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

编程作业:渗透问题

问题描述

给定一个由N*N个方格组成的方形水槽,其中每个方格是随机开启或关闭。相邻的开启方格可形成一条通路。如果存在一条从水槽顶端到底端的通路,则称该水槽渗透(Percolation)

渗透

假设其中的格子开启的概率为p,研究p的大小与整个系统渗透的概率之间的关系,当系统大小分别为20*20、100*100可以得到以下面的两个曲线。

20*20
100*100

要求编程建立一个模型,来验证当整个系统渗透时,格子的开启概率p的取值区间。(问题具体描述及要求)

问题分析

渗透模型

如图,将此抽象为Union-Find问题,一个方格抽象为一个节点,并用使用二维数组进行索引,二维数组索引值需要特别注意。为了方便判断整个系统是否渗透,可以在顶部和底部分别添加一个虚节点,它们分别与顶层所有节点及底层所有节点相连接。这样只要判断顶部和底部的虚节点是否连通,即可知整个系统是否渗透。

这时需要注意一个叫BackWash的问题:
backwash

解决这个问题的一个简单办法是维护两个数据结构,一个包含顶部及底部虚节点,另一个只包含顶部虚节点。

抽象好整个系统后,根据具体要求中的提示,用蒙特卡洛(Monte Carlo)法进行编程分析,确定渗透阈值p。先初始化所有的格子为关闭状态,之后随机开启一些格子,直到系统渗透;统计出开启的格子数,与全部格子数的比值即是作为p值;进行T次实验,得到足够多的p值后,算出所有p的平均值$\overline x $及方差$s^2$后,根据如下公式可以计算出置信区间在95%的的渗透阈值范围:$$\left [ \; \overline x - \frac {1.96 s}{\sqrt{T}}, \;\; \overline x + \frac {1.96 s}{\sqrt{T}} \; \right]$$

实现

(仅供参考)
Percolation.java

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// Programming Assignment 1:Percolation

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {

private static final boolean BLOCK = false;
private static final boolean OPEN = true;

private final int n; // 容器大小
private boolean[][] grid; // 容器数组
private int openedNum; // 开放数目
final WeightedQuickUnionUF gridUF; // 加权Quick-Union
final WeightedQuickUnionUF gridUF_backwash; // 防止backlash

//初始化
public Percolation(int n) {
if (n <= 0)
throw new IllegalArgumentException("n值非法!");

this.n = n;
openedNum = 0;
gridUF = new WeightedQuickUnionUF(n * n + 2); // 加上上、下虚节点
gridUF_backwash = new WeightedQuickUnionUF((n * n + 1)); // 只包含上虚节点
grid = new boolean[n][n];

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
grid[i][j] = BLOCK; // 初始化为封闭
}

//验证索引值
private void validate(int row, int col) {
if (row < 1 || col < 1 || col > n || row > n)
throw new IllegalArgumentException("行列索引值非法!");
}

//打开某节点并判断连通性
public void open(int row, int col) {

validate(row, col);

if (!grid[row - 1][col - 1]) {
grid[row - 1][col - 1] = OPEN; // 开启并计数
int position = map2Dto1D(row, col);
openedNum++;

if (row == 1) {
gridUF.union(0, position); // 如果是第一行的节点,与上方虚节点0相连
gridUF_backwash.union(0, position);
}
if (row > 1 && grid[row - 2][col - 1]) { // 判断节点上方是否开放
gridUF.union(position - n, position);
gridUF_backwash.union(position - n, position);
}

if (row < n && grid[row][col - 1]) { // 判断节点下方是否开放
gridUF.union(position + n, position);
gridUF_backwash.union(position + n, position);
}

if (col > 1 && grid[row - 1][col - 2]) { // 判断节点左方是否开放
gridUF.union(position - 1, position);
gridUF_backwash.union(position - 1, position);
}

if (col < n && grid[row - 1][col] == OPEN) { // 判断节点右方是否开放
gridUF.union(position + 1, position);
gridUF_backwash.union(position + 1, position);
}

if (row == n) // 如果是最后一行的节点,与下方的虚节点(n×n + 1)相连
gridUF.union(position, n * n + 1);
}
}

// 某个节点是否打开
public boolean isOpen(int row, int col) {

validate(row, col);

return grid[row - 1][col - 1];
}

// 某个节点是否渗透
public boolean isFull(int row, int col) {

validate(row, col);
int position = map2Dto1D(row, col);

return gridUF_backwash.connected(0, position);
}

// 开放节点值
public int numberOfOpenSites() {
return openedNum;
}

// 是否渗透
public boolean percolates() {
return gridUF.connected(0, n * n + 1);
}

// 坐标转换
private int map2Dto1D(int row, int col) {
return (row - 1) * n + col;
}
}

PercolationStats.java

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Programming Assignment 1:Percolation

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;

public class PercolationStats {

private final int trials; //实验次数
final double[] fractions; //分值记录

private double mean; //平均值
private double stddev; //标准差

//初始化
public PercolationStats(int n, int trials) {

if (n <= 0 || trials <= 0)
throw new IllegalArgumentException("参数值非法!");

this.trials = trials;
fractions = new double[trials];

for (int i = 0; i < trials; i++) {
Percolation p = new Percolation(n);

while (true) {
int row, col;
row = StdRandom.uniform(n) + 1; //随机列
col = StdRandom.uniform(n) + 1; //随机行
p.open(row, col);

if (p.numberOfOpenSites() >= n && p.percolates()) {
fractions[i] = (double) p.numberOfOpenSites() / (n * n);
break;
}
}
}

}

//平均值
public double mean() {
mean = StdStats.mean(fractions);
return mean;
}

//标准差
public double stddev() {
stddev = StdStats.stddev(fractions);
return stddev;
}

//上区间值
public double confidenceLo() {
return mean - 1.96 * stddev / Math.sqrt(trials);
}

//下区间值
public double confidenceHi() {
return mean + 1.96 * stddev / Math.sqrt(trials);
}

public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int trials = Integer.parseInt(args[1]);

PercolationStats ps = new PercolationStats(n, trials);
StdOut.print("mean =" + ps.mean() + "\n");
StdOut.print("stddev =" + ps.stddev() + "\n");
StdOut.print("95% confidence interval =[" + ps.confidenceLo() + ps.confidenceHi() + "]\n");
}

}

参考资料

  1. Algorithms-Coursera
  2. 程序及资料-GitHub

注:本文涉及的图片及资料均整理翻译自Robert Sedgewick的Algorithms课程以及配套教材《算法(第四版)》,版权归其所有。翻译整理水平有限,如有不妥的地方欢迎指出。


更新历史:

  • 2017.11.15 完成初稿
  • 2018.02.16 内容更新
文章作者: Hugsy
文章链接: http://binweber.top/2018/02/15/algs_1/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Weber
支付宝打赏~
微信打赏~