算法第一章   动态连通性

    首先，我们讲到第一个问题，也就是第三张PPT，动态连通性问题，就是给出N个对象，并从0到N-1将它们命名，在做过若干次合并操作（连接两个对象）过后，然后来看两个对象之间（与合并时的两个对象不一定相同）是否有连通的路径，这就是动态连通性问题。如图中的这个例子，在事先已经合并了4和3，3和8，6和，9和4，2和1这5对对象之后，我们来看几对对象之间是否相互连通，0和7，不连通，8和9不连通，我们再合并5和0，7和2，6和1，1和0，然后查询0和7，此时它们就变成连通的了。

    我们再来看第四张PPT，图中的P和Q有连通的路径吗？答案是，有，因为在P和Q之间存在着若干个相互连通的位点。

    从中我们可以总结出来动态连通性问题的几个特点，就是逆反性，也就是说每个对象都能连接到自己，还有就是对称性，也就是说如果P能连接到Q，那么Q也能连接到P，最后一个则是传递性，如果P连接到Q，而且Q连接到R，那么P就能连接到R。

    动态连通性问题在实际生活中我们也会遇到很多，如数码照片的像素，网络中的计算机，两台计算机之间是否联络或访问，则表明它们是否有连通性，社会网络之中的两个人之间是否认识或是否有联系，则表明它们之间是否有连通性，又如计算机芯片中的电路元件，程序中的变量名，数学集合中的元素，复合体系中的金属，这里就不一一解释了。

  对象之间相互连接会构成一个集合，我们可以将这些集合为连通分量，连通分量就是相互连接的对象的最大集合，如第七张PPT所示，0单独构成一个连通分量，1，4，5共同构成一个连通分量，2，3，6，7共同构成一个连通分量。

  那么我们有了模型之后即可以对它们实施运算，当我们进行查找请求时，我们可以查找两个对象是否在同一个连通分量中，当我们进行合并命令时，我们可以将两个对象的分量替换成它们的并集。         

    如第八张PPT所示，当我们合并2和5时，它们所在的连通分量也会合并，结果就只剩下两个连通分量。

    接下来我们来看第九张PPT，也就是解决动态连通性问题的第一种算法，快速查找算法，也是贪心算法，它的数据结构是在一个长度为N的索引整数数组中，当且仅当两个对象P与Q在数组中的项是一样时，两个对象是相互连通的。如图中所示，0，5，6的项是一样的，都是0，所以它们是相互连通的，并构成一个连通分量，1，2，7的项都是1，所以它们构成一个连通分量，3，4，8，9的id值都是8，所以它们也构成一个连通分量。

    然后我们再来看下这个算法的具体操作，给出一个既定的数组，进行查询操作，检查P和Q是否有相同的id值，例如图中的6和1，1的id值是1，6的id值是0，那么6和1则是不连通的，返回“F”，再进行合并操作，将6并与6连通的对象的id值改为1的id值。但是这样会出现一个问题，也就是会出现大量对象的id值发生改变的情况。

    我们来看看这个算法的效率，效率的模型是访问数组的次数，初始化与合并的次数与N成正比。而查找操作的次数是常数项，合并的代价太大了，如果你想要在N个对象上进行N次合并操作，那么你所需要花费的时间将是正比与N2这个级别上的。

    那么为什么我们不愿意使用平方级的算法呢？原因就在于平方级的算法无法应用于巨大规模的动态连通性问题，对于现在的计算机而言，我们能够每秒进行几十亿次操作，而这些计算机的驻内存中有几十亿项，也就是说，我们可以早大约一秒的时间内访问主内存所有的项，那么当我们使用快速查询算法这种平方级的算法处理巨大规模的问题的时候，例如在几十亿个对象上进行几十亿个合并操作，那么我们需要进行10的18次方个操作，即使我们有每秒能够进行几十亿次操作的计算机，那么我们也需要几十亿秒才能解决这个问题，换算一下大概需要30多年的时间，这显然无法满足我们对时间的要求。二次方时间的算法也不能成比例适用于新技术，试想一下，即使你拥有一台比现在的快10倍的新计算机, 但你可能遇到一个10倍大的问题 ,那么使用平方时间算法处理这个问题花的时间还要多10倍。

    在快速查找算法不能处理大规模动态连通性问题的情况下，我们又提出了一种新的用来替代快速查找算法的懒人算法，叫做快速合并算法。它的数据结构是在长度为N的索引整数数组中，把数组看作一组树即一片森林的表示，数组中的每一项包含在它在树中的父节点；根结点则表示该节点的父节点是它本身，如果根结点相同，则两个对象是相互连通的。如图中所示，0的父节点是0本身，所以0的根节点是0，1的根结点是1，2的根结点是9，3的父节点是4，3和4的根结点是9，5和6的根结点是6，7，8，9的根结点均是它们本身，所以2，4，3，9构成一个连通分量，5和6构成一个连通分量，其他对象均单独构成一给连通分量。

    我们再来看看这个算法的具体操作，在一个已经经过若干次合并操作的整数数组中，先进行查找操作，检查P和Q是否具有相同的根结点，例如图中的3和5，3的根结点是9，5的根结点是6，所以3和5是不连通的返回“F”，再进行合并操作，将3的根结点9设为5的根节点6的子节点。结果只有9的发生了改变。

    我们再来看快速合并算法的效率，我们发现快速合并的效率在解决大规模问题时同样也很慢，我们同样以访问数组的次数作为效率的模型，初始化的次数均正比于N，快速合并的实际操作次数应该为常数，但是如果加上找根结点的这个操作，那么合并操作的次数将正比与N，查找操作显然正比于N，快速合并的缺点在于树可能会很高，那么对子节点执行一次查找操作,可能需要回溯整棵树，只进行查找操作就需要花费N次数组访问，因此快速合并算法也不支持巨大的动态连通性问题。

    在已知上述的两种算法都无法解决大规模动态连通性问题的情况下，我们需要做出一些改进，也就是我们的第16张PPT，加权，就是在快速合并的基础上进行一些修改来避免得到很高的树，通过跟踪每棵树的对象的个数，将小树的根结点作为大树的根结点的子节点以维持平衡。

    我们避免图中将大的树放在下面的情况，在加权算法中，我们总是将小的树放在下面，也就是说查找操作与快速合并算法中是一样的，只是合并操作进行了一点修改而已。

    我们再来对加权的运算时间进行分析，我们发现查找操作花费的时间与节点P和Q在树中的深度成正比，因为你在树中的深度跟你查找操作时访问数组的次数有关，而是合并操作只需要花费常数倍时间，因为它只需要将节点P的根结点设置成节点Q的根结点的子节点就可以了。在这里我们要提出一个命题，即树中任意节点的深度上线是以2为的N的对数。

    我们可以对这个命题进行证明，当任意节点x所在的树T1，与T2合并时，如果T2>=T1,x深度加1，所以x深度增加时，树的大小至少翻倍。假设x的深度一直增加，那么x所在的树，则一直翻倍直到得到N，即使树从1开始，最多也只能翻lgN倍（这里的lgN指以2为地N的对数），所以树中任意节点得深度上限是lgN。

    现在，除了初始化总是需要正比于N的时间，合并和 “是否连接”或查询操作需要的时间都是正比于N以2为底的对数 这个算法能成比例适应大规模问题。当N从1百万变为10亿 花费的时间仅仅从20变为30，说明这个算法已经可以适应大规模动态连通性问题了。

    那么这个算法我们还能够进行进一步改进吗？答案是可以的，那就是路径压缩，当我们找到P的根结点之后，可以回过头来将路径上的每个节点都指向根结点，从图中可以看出当我们找到对象9的根结点是0时，我们回过头来将9直接指向根节点0，再将9的根结点6指向0，再将祖父节点3指向0。

    要分析这个算法已经超出了我的能力范围，但是Hopcroft Ulman和Tarjan证明了如果有N个对象，M个合并与查找操作的任意序列，需要访问数组最多c(N + M lg* N)次。lg* N是个挺有意思的函数 它是使N变为1需要取对数的次数,它叫做迭代对数函数,从右表中可以看出，当N为1时lg* N为0，当N为2时，lg* N等于1，当N增长到65536时，lg* N仅仅等于4，N等于265536时，lg* N等于5，由此我们可以看出迭代函数关于N的增长非常缓慢，然而还有迭代函数函数更慢的函数，阿克曼函数，或者说是反阿克曼函数，阿克曼函数是一个增长特别快的函数，

                       Ackermann(0,n)=n+1

                       若m>0且n=0，返回Ackermann(m-1,1)。

                       若m>0且n>0，返回Ackermann(m-1,Ackermann(m,n-1))。Ackermann(0,n)=n+1

 当n大于时，数字基本上大的难以计算了，所以它的反函数相应的也会特别慢，甚至比迭代函数还要慢。这个函数已经非常接近与N成正比的线性了，那么是否存在一个算法就是线性的呢？Friedman与Sachs最终证明，并查集问题不存在线性算法。

    最后做一个总结，带压缩路径的加权快速合并算法能够解决其他算法不能解决的问题，也就是大闺蜜动态连通性问题。使用加权快速合并算法或带压缩路径的快速合并所需要消耗的时间最多与（N+MlgN）成正比，而使用带压缩路径的加权快速合并算法所需要耗的时间最多与（N+Mlg*N)成正比。之前我们在讲快速合并算法时，提到使用平方级算法在十亿个对象进行十亿次操作需要花费30年，而现在使用WQUPC值需要6秒，这为我们节省了大量的时间，即使使用了超级计算机也不能达到这种效果，它最多可能将30年减少到几年或几个月，但是使用快速的算法我们只需要几秒就足够了。

    我们现在已经找到了解决大规模们问题的高效算法，现在来看下它的应用，渗滤，很多物理系统的一个模型，给出一个 n×n的方形网格，小方格叫做位，每个位是开放的概率为p ，位是闭合的概率为1-p，如果顶端和底端被开放的位连通，我们则认为这个系统是渗滤的。如图中所示，为一个8×8的方形网格，黑色方格代表闭合，白色方格表示开放，从左图中可以找到一条通过白色方格从上到下的路径，所以左边的系统是渗滤的，而右边的系统不是渗滤的，不存在通过白色方格 从上到下的路径。

    渗滤模型在实际生活中有很多例子，如第29张PPT所示， 在电力系统中，可以认为开放的位是导体，闭合的位是绝缘体，所以如果存在 从上到下的导体那么系统就是导电的。或者可以认为水流过某种多孔的物质，开放位就是空的 闭合位有一些材料，是否渗滤就是水能否从上端流到下端。或者可以认为这个系统是社交网络，，人们互相有联系，两个人之间可能有 也可能没有联系，系统是否是渗滤的就是是否存在一条路径一群人可以通过社交网络联系另一群人。

    假如这个方形网格是一个每个位开放概率位P的随机模型，我们可以清楚地看到，当概率P比较低例如等于4的时候，系统时不渗滤的，因为开放的位根本不够形成从上到下的连接，当P很大时，有很多开放位，从上到下会有很多条通路，系统就一定是渗滤的。那么当概率P中等的时候，就不是很好判断系统是否渗滤了。

    系统渗滤这个问题存在相变，相变就是当一个系统里的元素发生改变的时候，这个系统会从一种状态转变到另外一种状态。实际上 ，系统是否渗滤的概率p阈值非常陡峭，而且存在一个值，当N非常大，p小于该值时 ，系统基本肯定不是渗滤的，如果大于该值，基本 一定会渗滤。所以我们需要求出这个概率的值。通过在计算机上成千上万次的实验，我们可以得到一个粗略的阈值，大约是0.593。

    但是我们需要得出一个精准的答案，所以我们需要用到蒙特卡罗仿真来得出这个概率，并通过并查集算法来运行。首先将整个网格初始化为闭合的，即全是黑色的，然后随机加上开放的位，每次加上一个开放位后，检查是否使系统变得渗滤的。持续这个过程直到系统变得是渗滤的。我们可以得出系统变得渗滤时开放位的比例是要求的阈值的估计。

    那么当系统以一定的开放位比例渗滤时，我们要如何得知呢？首先我们对应每一个位，构建一个矩阵状的点集，然后从0到N2-1分别将它们命名，如果开放位位和开放位 连在一起，我们就把它们连接在一起，检查最下面一行中是否有位与最上面一行任何一个位连通，如果有则表明系统渗滤。但是这么做需要花费很多查找操作的时间来检验它们是够连通了，需要N2次，这就变成一个平方级的算法了，所以我们可以做一点小改进，就是在顶端和底端各加一个虚拟位，那么想知道系统是否渗滤时，只需要检查虚拟顶端位和虚拟底端位是否连通这样我们就只需要一次连接操作就可以了。

    那么我们要怎么对开放新位建模呢？我们值需要将它和周围开放的位连通就可以了，所以需要调用几次合并操作。现在我们就可以对这个问题进行仿真，我们在足够大的N上运行足够多次的仿真获得结果，得出渗滤阈值大约是0.592746，这就比我们之前的出的1结果要精确多了，事实证明，使用快速的算法，使我们关于这个科学问题获得了一个精确的答案。

    通过这一章节的学习，我得到一些体会就是，如果我们想要针对一个问题开发一个有效算法，那么我们首先要根据这个问题建立模型，据此找出算法解决该问题，然后检验该算法是否足够快速，内存是否足够，如果不是，计算出为什么，然后找到方法来解决这个问题，最后需要反复验证是否满意直到得到一个合格的算法。