面向大图的传递归约问题研究
本文关键词：面向大图的传递归约问题研究 出处：《燕山大学》2016年硕士论文 论文类型：学位论文
【摘要】：给定有向无环图G,G的传递归约是和G有相同传递闭包的最小唯一子图。传递归约是图论中的经典问题之一,并广泛应用于实际中简化问题的求解,包括传递闭包、背包问题、可达性问题等。然而,现有传递归约方法的计算代价高昂。随着网络技术的飞速发展和新型应用的不断涌现,实际应用中的图规模越来越大,在机器内存容量受限的情况下,已有的传递归约算法因其较高的空间复杂度面临无法使用的尴尬境地。本文从以下几个方面对有向无环图的传递归约方法进行研究,具体内容如下。首先,提出自底向上的BUTR算法。该算法首先将G分解为k条路径,以自底向上的方式处理每条路径p。其特点体现在处理每条路径p时,可以利用p中顶点间的父子关系来避免对部分顶点和边的重复访问,并保证在处理完p的所有顶点后,所有涉及到的边仅被访问一次。当处理完所有的k条路径之后,即可得到传递归约。BUTR时间与空间复杂度分别为O(km)和O(n),其中n、m分别为图G中结点和边的个数。其次,针对BUTR算法在实际应用中路径分解规模过大的问题,提出无需路径分解的算法TDTR来避免BUTR算法存在的冗余计算问题。TDTR通过栈来缓存已处理结点并标记其逆向传递闭包,从而尽可能早的利用结点间的父子关系来避免BUTR算法存在的冗余计算问题。算法TDTR时间与空间复杂度分别为O(wavgm)和O(n),wavg为为处理单个结点时平均访问结点数目。最后,在26个不同规模的真实数据集上,通过实验从不同角度对算法的性能进行深入比较和分析。实验结果验证了本文算法的高效性和扩展性。
[Abstract]:In this paper , the paper presents the algorithm TDTR , which can be used to solve the problem of redundancy calculation of the BUTR algorithm . In this paper , the algorithm TDTR is used to solve the problem of redundancy calculation of the BUTR algorithm .
【学位授予单位】：燕山大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【相似文献】
相关期刊论文 前8条
1 陆正福,何英,杨邓奇,王国栋;模归约算法的数学基础研究[J];云南大学学报(自然科学版);2005年04期
2 叶恒舟;罗晓娟;牛秦洲;;基于归约图的Web服务自动组合[J];桂林工学院学报;2009年03期
3 谢宜晖;苏运霖;;关于Petri网归约问题[J];暨南大学学报(自然科学与医学版);1990年01期
4 王洁;p-t-归约及sn-t-归约的一些性质[J];中山大学学报(自然科学版);1986年03期
5 杨东屏;结构多项式复杂性研究中使用的一些方法[J];数学进展;1995年04期
6 李传湘;字集的识别模型[J];数学物理学报;1998年02期
7 韦元军;;实函数的归约性[J];贵州大学学报(自然科学版);1987年03期
8 ;[J];;年期
相关会议论文 前1条
1 林珠;邢延;;适用于时间序列分类的数据归约方法[A];2009年中国智能自动化会议论文集（第二分册）[C];2009年
相关博士学位论文 前1条
1 刘云霞;数据归约的统计方法研究及应用[D];厦门大学;2007年
相关硕士学位论文 前3条
1 周世杰;面向大图的传递归约问题研究[D];燕山大学;2016年
2 孙寅龙;X-DSP 64位定点ALU和归约单元的设计优化与验证[D];国防科学技术大学;2014年
3 张闯;X-DSP64位定点运算单元与向量归约网络的设计与实现[D];国防科学技术大学;2013年
，本文编号：1379894
本文链接：https://www.wllwen.com/kejilunwen/yysx/1379894.html
