Floyd解决传递闭包

admin • 2015年3月10日下午7:02 • 学术报告 • 阅读 1469

传递闭包：在数学上的定义——在集合X上的二元关系R的传递闭包是包含R的X上的最小传递关系。其中定义域是数据集X，而运算关系是必须具有传递性，这里的最小传递关系指的是包含所有可达路径。我们用一个简单的例子来说明一下这个问题

如上图是一张地图，上面有六个地点，我们已知的路线连接如图中箭头所示，传递闭包就是在原图上的连接关系的基础上，通过传递可以扩展出来的连线，与原图连线共同构成的地点之间可以到达的连接，最终图为：

其中，红色标注的就是新传递出来的路径，由这些路径（箭头）构成的集合就是这个图的传递闭包。下面我们依据传递闭包来解决一个实际问题：学院举办一个辩论会，请你设计一个成绩记录器，要求：先输入参赛队伍数，然后依次输入比赛场次及每场比赛结果，最后可以输入一组队伍，系统可以输出两者的胜负关系。（胜利的关系是传递，且双方只战一场。例：A胜了B，B胜了C，则可以A胜了C。如果无法传递胜负关系则输出不能判断。双方胜利关系由直接对战结果决定）。
不难发现这就是一个闭包问题。我们来做一下对应。X就是所有参赛队的集合；二元关系就是胜利，从题目叙述它正好符合传递性；通过这个问题的对应，我们就可以构建这个传递闭包了。接下来我们将用图算法来解决这个问题，在解决之前，我们先对图进行一个初步的了解。
对于图G=(V，E),最重要的两个元素就是V(顶点或结点）和E（边）。很明显对于以上问题，每个参赛队就是一个结点，每两队之间的胜负关系则构成一条边，这个图就很容的建立了。
图有两种表示方法：1）邻接链表；2）邻接矩阵。邻接链表就是把每一个结点邻接直达的关系连接构成一个链表，这样就会构成length（V）个链表。邻接矩阵的实现则相对简单，它就是把每个结点生成一个二维矩阵的一行或者一列，矩阵的每一个元素则代表了对应两个结点的胜负关系。对于上图进行两种表示方法的展示：
邻接链表

邻接矩阵：

对比以上两种方法，很明显的，邻接链表方法构建、复杂（结点操作）。而邻接矩阵只是对二维数组对应点的赋值以及检索处理。我们以矩阵方式进行扩展，用floyd算法解决传递闭包来解决这个问题：

至此，问题核心部分就已解决，输入任意队伍组，即可输出二者之间的胜负关系了。但是问题出现了，上述解决似乎忽略了一个闭环的问题；例如，如果三场结果是a战胜b，b战胜c，c战胜a，这就构成了一个闭环。我们分析上述代码，生成上不会有问题，但是在算法执行中检测到 str[a-1][b-1]==1&&str[b-1][c-1]==1 则会把str[a-1][c-1]置1。此时显示1战胜了3，而实际3战胜了1.为解决此问题，我们可修改代码如下：

修改后的代码中，在生成时，只有两两交战的结果，所以一旦一方获胜自然另一方为负（仅赛一场）。所以可以再设置a胜b的同时，设置b负于a的标志（设置0）; 修改floyd算法的判断语句，在检测传递的同时，判断是否两者胜负关系直接已定。由此防止闭环现象的出现，同时设置双方胜负关系。至此算法问题已经解决。
如果矩阵稀疏度很大，即V*V远远大于E，这样矩阵的有效数据则会很少，在矩阵数很大的情况下，这会使运行效率大大降低。对于解决稀疏矩阵，有专门的Jhonson算法，在此，我们仅从改进floyd算法的做出处理。

以上算法改进在矩阵稀疏度很大的时候，运算效率远高于基本floyd算法，对于以上问题，在1000对参赛，只有5场结果时，在同运行环境和条件下，改进算法的运行时间是16ms，而初始算法则需要5636ms。随着稀疏度降低，对于以上问题就是比赛场次提升时，算法效率也就趋于基本算法。因此，以上改进仅适合矩阵系数度大的情况。