基于设置复合位置的传递闭包算法-论文.pdf

《基于设置复合位置的传递闭包算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第3期苏州科技学院学报(自然科学版)Vo1．31No．3Q生旦jouma1。fSuzh0uUniversity0fScie。dTeeho10gy(Natua1Science)Sep．2014基于设置复合位置的传递闭包算法汪小燕(安徽业大学计算机科学与技术学院，安徽马鞍山243032)摘要：二元关系的传递闭包根据定义有时不好计算，文中提出一种通过设置二元关系中序偶的复合位置．对被删减的二元关系按照序偶的复合位置，进行增量式复合来计算传递闭包的新算法，利用该算法可以较快地实现传递闭包的求解。关键词：二元关系；传递闭包；恒等关系；复

2、合位置中图分类号：O158文献标识码：A文章编号：1672—0687(2014)03—0043—03关系的传递闭包运算是近年来学者们研究的热点，传递闭包在图论、数据库、编译原理、计算机形式语言中都有重要的应用。关系的传递闭包一般根据定义来计算，需要进行多次的集合复合运算。运算量大，特别是当尺中的序偶较多时，计算起来不仅麻烦，而且容易出现错误。1962年Warshall提出了计算传递闭包的有效算法【l_，Warshall算法比较简单，而且也容易在计算机中实现，但该算法执行所用时间较多。近年来，也有不少学者提出传递闭包的改进算法，文献『2

3、—51减少了关系复合的次数，从而简化了原有传递闭包的计算。文献[6—7】提出利用关系矩阵求解传递闭包，也简化了传递闭包的计算。文献『8]提出如果关系中包含，>这一类的序偶，在计算传递闭包时，可以先不考虑，>这一类的序偶，在二元关系中删除这些序偶后，对被删减二元关系进行增量式复合计算，一次复合完毕，将复合计算的结果、原有的，>类序偶和新产生的，>类序偶合并在一起就可以计算出传递闭包。这种传递闭包的计算方法减少了，>这一类序偶的复合运算，并且只需要集合的一次复合运算。为了更进一步降低被删减二元关系和其自身增量式复合计算量，采取设置二元关系

4、中序偶的复合位置，使得被删减二元关系中的每个序偶都从自己的复合位置开始复合，不需要每个序偶都从被删减二元关系的第一个序偶开始寻找它们的复合元素，使用新的传递闭包算法可以节省复合计算时间，并且保留了文献中传递闭包算法的优越性。1相关理论定义1t1R为集合A上的二元关系，对于任意a，b，c∈A，当<口，6>∈尺且<6，c>∈R时，有<0，c>∈R，称R为A上的传递关系，或者说R在A上具有传递性。定义2t]设尺是集合上的二元关系，在R中添加最少的序偶集合尺，使得Ru具有传递性，则t(R)=尺UR是尺的传递闭包。如果关系本身具有传递性质，则t

5、(R)。定义3t】设R是集合A上的二元关系，对于任意∈A，，>∈R，且对于任意，Y∈A，如果≠y，则，y>簪R，则尺称为集合A中的恒等关系，记作，4。定义4阎设R是集合A上的二元关系，若={，x>lx∈A且，>∈R}，则称为尺中的恒等关系的集合【收稿日期】2013—09—11[基金项目】计算机软件新技术国家重点实验室开放课题基金资助项目(KFKT2010B02)；安徽省高校自然科学基金资助项目(KJ2012ZO24)[作者简介]汪小燕(1974一)，女，安徽桐城人，副教授，硕士，研究方向：数据挖掘，粗糙集理论，概念格，本体。苏州科技学

6、院学报(自然科学版)20l4年定义5t。】设R是集合4上的二元关系，，y，是A中的任意三个元素，若Vs，t∈R，且5=，>，扛，若以Y为中间元素，则和t可以形成新的序偶，>，将这一运算称为序偶的复合，记作s。拄，>。定理1阎设R是集合4上的二元关系，≠，判断尺是否具有传递性，可以不考虑中的所有序偶。2改进的传递闭包算法文献『81提出的传递闭包算法思想如下：设A是一非空集合，尺是集合A中的二元关系，计算R：尺一，将和其自身进行增量式复合运算，即计算尺。R，若产生序偶<，y>且=y，如果，y>譬，则将，y>并入；若产生序偶，y>

7、且=，，，如果，，，>∈，则将，y>舍弃；若产生序偶<，y>且≠，如果，>R，则将，>并人尺的末尾；若产生序偶，y>且≠y，如果，y>∈R，则将，y>舍弃，直到。R复合结束，则t(R)=尺U。当计算尺。时，若产生新的序偶，>R且≠，，y>要并人的末尾，如果产生这种类型的序偶较少，文献『8]所提出的传递闭包算法优越性是很明显的，但是，如果产生这种类型的序偶较多，每个新产生的序偶都要从的第一个序偶按照定义5进行复合，计算量会增大。为了改进文献『81提出的传递闭包算法，降低复合计算量．采取记录集合中每个元素在R中作为序偶的第一元素第一次出现

8、的位置，现提出如下的3个定义。定义6设是集合4上的二元关系，尺=一，若任意，y>∈R，，y>在尺中的排序，就是序偶，>在尺中的位置。序偶，y>在R中的位置，一般从1开始编号。定义7设R是集合A上的二元关系，，Y是4中的任