并查集

零、概述:

1. 本周内容通过引入动态连通性问题,介绍了并查集的思路与实现。连通性问题是判断给定的两个点,是否存在一条通路使得它们是连通的。

2. 作者首先介绍了quick find算法,直接使用数组模拟,把能够连通的元素看成一个集合,它们对应的索引的值相等,但是这种方法存在的问题是每一次连通操作的合并过程都需要更改一个集合中的所有元素,这部分耗时过多,近乎达到N的平方阶了。

3. 针对这一个问题,作者提出了进一步的改进思路:quick union算法,还是用数组模拟,但是对于每一个集合都看成棵树,选择某一个元素作为它的代表(即作为根结点),每次合并只改变它的根部索引的值(即将它的根部合并到作为另一棵树的子结点)。这种方法把合并操作的更改减少到了1,但是合并前查找根部结点的耗时会随着树的加长而加长。

4. 故而下一步引入的方法的着力点在于尽量减少树的长度,这里主要有两个步骤去实现:一个是对树进行加权,每一个树都用一个值来保留它的大小,合并的时候把小的树合并到大的树上面。第二个是进行路径压缩,在查找根结点的过程中,尽量将一个遇到的结点都提高到作为它的根结点的孩子,这也使得最后整棵树变得扁平。查找的时间减低到常数。

5. 经过这一系列的优化,算法的速度得到了很大的提高,在实践中几乎是达到了线性的程度了。

一、dynamic connectivity

1. 设计一个可行算法的步骤:
    a. 问题建模,寻找算法。
    b. 检查算法速度是否足够快。
    c. 寻找原因,改进,直到满足要求。
    
2.  动态连通性问题:
    a. 给定若干个物体。
    b. 可以给两个物体之间建立连接。
    c. 问某两个物体之间是否存在通路。
    
    
3. 对象的建模:
    a. 问题的相关应用:
        i. 数字图片上的像素。
        ii. 网络上的计算机。
        iii. 社交网络上的关系。
        iv. 计算机芯片中的晶体管。
        v. 数学集合中的成员。
        vi. Fortran语言中的变量名。
        vii. 复合系统中的金属位置。
        
    b. 编程过程中的简化:编号
        i. 使用整数作为数组的下标,便于访问。
        ii. 减少与并查集无关的细节。
    
4. 连接的建模:
    a. 假设连接是一个等价关系:
        i. 具有自反性:
        ii. 具有对称性:
        iii. 具有传递性:
    b. 连通集合:
        i. 最小的相互连接的集合。
            1) 没有不在这个集合内的元素与集合内的元素相互连接。
        
5. 实现操作:
    a. 寻找路径:
        i. 判断两个对象是否在同一个集合中。
    b. 合并操作:
        i. 将两个不同的连通集合合并。
            
6. API
    a. 目标:
        i. 设计一个有效的并查集数据结构:
            对象和操作都是庞大的,寻找路径可能很复杂。
            创建一个叫UF的类,实现两个操作
            
    b. 动态连接的接口:
        i. 从标准输入中读入对象个数N
        ii. 重复进行:
            1) 从标准输入中读取一对整数。
            2) 如果它们没有连接,就将他们连接,并打印连接对。
            
            

二、quick find

1. 数据结构:
    a. 一个整数数组,如果两个对象是连通的,那么他们的值相等。
            
2. 操作:
    a. 查找:
        i. 检查两个对象是否具有相同的下标。
    b. 合并:
        i. 将两个连通集合合并,改变一个连通集合的所有值。
        ii. 易于实现,但当数据量比较大的时候,每次连接都需要很大的时间开销。
3. 代码实现:

            
        、
4. 性能评估:
    a.  各个部分时间开销:
        i. 明显看出合并部分每次需要n次操作,而最后算法的复杂度可以到n的平方项。
            
         
    b. 故而下一步思路自然而言的就是要改造合并操作。

三、quick union

1. 数据结构
    a. 将对应的数组当做一个森林。
    b. 数组中的值当做是对应索引的父节点。
    c. 如图中,下标2,4,9的对应的值都是9,故而9可以当成他们的根结点。
        i. 很明显可以看出,因为初始化,其中必然有一个项的下标跟他们共同的值相同。
        ii. 故而这个结点就是根结点,故而整棵树就可以当做是一个连通集合了。
        iii. 根结点的的标志:
            1) 通过不断地向上查找,知道找到某个值的索引等于它对应的值。
            2) 作用:
                a) 这种表示方法利于下面合并操作的时候,只要改掉对应的根结点的索引的值即可。
                
2. 操作:
    a. 查找:
        i. 只需要确定两个结点是否具有相同的根结点即可。
    b. 合并:
        i. 要合并两个结点,只要把其中一个结点的根结点改变成另一个结点的根结点。
            1) 从抽象意义上来说,即合并两棵树,其中一棵树作为另一棵树的子树。 
            2) 对于具体实现来说,就是把其中一个数组的根结点的的下标改变成对应的另一个结点的根的下标。
                a) 那么向上索引的时候,两个树索引到的都是合并到的那棵树的根。
            3) 如下图,要把3合并到5的位置,需要做的是分别找到他们的根6和9, 把9的值改成6的值,那么对于两个集合来说,合并后,它们共同的代表就是6了。
    

                
      


3. 代码实现:
            



4. 性能评估:
    a. 各部分时间开销:
        i. 固然相比而言减少了需要更改的值的量,但是查找根需要的时间会随着合并的次数的增加而增加。
        
    
    b. 故而下一步的优化应该是如何在不改变性质的情况下去减少树的深度。
    






四、improvements

1. 加权:
    a. 在实现quick_union的时候尽量避免深度大的树。
        i. 跟踪每一棵树的大小(只跟踪根结点的大小)。
        ii. 把小的树合并到大的树上面。
        iii. 有点类似于哈夫曼编码的感觉。
    b. 代码实现:
        i. 其余部分不变,增加一个保存树的大小的数组,并把小的树合并到大的树上,并改变大小。 
        
                
         
    c. 性能评估:
        i. 查找和合并操作都取决于树的高度,而数的高度最多只有lgN。
                
        ii. 但是其实还有方法可以得到更进一步的提高。
 

2. 路径压缩
    a. 将每一个父节点不是根结点的结点的父节点转移到根结点。(在查找根的时候进行)
        i. 所以到最后,整棵树 基本就是一条横线了。
    b. 代码实现:
        i. 只要在每次查找根的时候,查到到对应的父节点,只要不是根结点,就把父节点往上提,在改变查找位置父节点哪里。
        
                
                                    
    c. 性能评估:
        i. 合并过程中的查找过程几乎是常数倍的了。
        ii. 理论上还不算线性的,但在实际中,算法的复杂度可以低到线性。
        
                
                                                        


五、applications

1. 并查集应用实例:
            
            
2. Percolation:
    a. 问题描述
        i. 有一个N*N的方格。
        ii. 每一个方格都有p概率会打开。
        iii. 如果一个系统底部和顶部连通,那么它就被称为Percolation 
    b.  实例:
        i. 可以当成是是否存在电流/水流/关系网等等。
    c. 数学近似:
        i. 取决于概率的大小。
                
    d. Monte Carlo simulation(蒙特卡洛模拟)
        i. N*N方格。
        ii. 随机打开某些方格,不断进行。
        iii. 直到最后方格连通。
    e. 使用并查集解决问题:
        i. 创建一个N^2-1的数组。
        ii. 连通则当做一个并集。
        iii. 如果顶部的某个值和底部的某个值连通,则成功。(但是这样的检查代价太大了)
        iv. 改进:
            1) 在顶部和底部分别加一个点和顶部和底部相连,则只用检查这两个点是否相连即可。

clipboard.png

评论

暂无评论