学位论文 > 优秀研究生学位论文题录展示

星图互联网络上的最短路径及并行路径算法的研究

作　者: 王静
导　师: 郭大昌
学　校: 广东工业大学
专　业: 组合数学与最优化
关键词: 星图互联网络最短路径并行路径长度
分类号: O157.5
类　型: 硕士论文
年　份: 2011年
下　载: 25次
引　用: 0次
阅　读: 论文下载

内容摘要

星图由于具有正则性、对称性、可扩展性、直径短、结点的存储空间小等良好的拓扑结构特性,使得它比较适宜作为多处理机系统拓扑结构的原型,为此星图逐渐成为实践研究者的新的目标。而且由于路由路径的选择直接反映了星图互联网络的性能,因此对星图互联网络中的路由研究一直都是人们所关注的热点问题,鉴于此,本文在探索星图拓扑结构特性的基础上研究了星图中的路由路径,具体包含以下两个方面的工作：1.在星图互联网络中,要将消息从源结点传送给目的结点,那么它们之间的路径的选择将会影响到传送消息所耗费的时间,因此,为了提高传送效率,它们之间的路径一定要选择的越短越好,找任意两点之间的最短路径算法也就显得尤为重要,为了解决这一问题,本文给出了找任意两点之间的最短路径算法,并在实例中和文献中已有的方法进行了比较,结果显示本文给出的方法比较直接、方便。2.伴随着多处理器系统规模的增大,系统中出现结点与链路故障的概论也随之增大,而且当互联网络中任意两个结点之间有大量数据消息需要传送时,为了在短时间内将消息传送出去,提高传送的效率,以及当星图网络中出现结点故障或链路故障的情况下保证消息的正常传输,针对这一问题,本文从群论的角度出发,重点采用循环置换的相关性质,给出了一种新的寻找星图互联网络中任意两点之间的所有并行路径的方法。由于在寻找的过程中,该方法将条件细化成不同的情况讨论,从而保证了在每种情况下给出的所有并行路径的长度构成的集合的上界都是最短的,同时也保证了该算法的有效性和最优性。

星图互联网络上的最短路径及并行路径算法的研究

内容摘要

全文目录

相似论文