HTEDI算法的实现和改进

发布时间：2017-12-11 02:18

  本文关键词：HTEDI算法的实现和改进

  更多相关文章： 最短路径 最小度的树分解 最小填充的树分解

【摘要】：点到点的最短路径问题是复杂网络和GIS等学科中的经典问题,在实践中得到广泛应用,如物流运输、车载导航、社交网络、计算机网络等。虽然针对该问题提出过许多经典算法,但是随着网络规模迅速扩大,网络拓扑结构越来越复杂,对现有的最短路径算法提出新的挑战。多核计算机的出现,为最短路径搜索算法的改进提供新途径。本文主要内容如下:首先,对最短路径的研究背景和意义、国内外研究进展进行总结,介绍了本文的研究内容、组织结构及技术路线。其次,对当前点到点的最短路径算法进行分类总结,包括精确最短路径算法、近似最短路径算法。精确最短路径算法,如Dijkstra、BFS、SPFA、Bellman-Ford等,该类算法常应用于精度要求较高的情形,如计算机网络协议、数据库查询等;近似最短路径算法,如A*、双向算法、分层算法、ALT等,该类算法应用在对精度要求不太高的情形,如机器人导航、地图导航等。其次,对树分解算法进行分类总结,主要包括两类:基于消除序列的树分解算法和基于割集的树分解算法。基于消除序列的树分解算法主要有弦图识别算法,如:最大基搜索泛(Maximum Cardinality Search algorithm)、字典广度优先搜索算法(Lexicographic Breadth First Search algorithm)等,基于贪心的三角化算法,如:基于最小度的树分解算法(MinDegree)、基于最小填充的树分解算法(MinFill)等,基于剪枝约束的算法等,该类算法主要特点是时间复杂度较低。基于割集的树分解算法主要有基于组件分割策略的算法(The splitting into components strategy)、基于最小顶点割集的启发式算法(The Minimum Separating Vertex Sets heuristic)等,该类算法的优点是可以根据树分解的上界作为启发,但是时间复杂度较高。然后,通过对HTEDI算法(由Fang Wei-Kleiner于2016年提出)的分析。据此对最短路径查询过程进行改进,主要包括,将算法的查询过程从双向计算过程改为单向,使算法在有向图中也是可靠解;将根节点的计算过程进行特殊处理(见第五章),保留原算法时间和空间平衡的优点;根据树分解父节点和子节点的特点,加快最短路径算法的查询过程。在真实的道路网中进行实证分析,证明改进后的算法在有向有权图上是可靠解,并且查询速度得到有效改善。接着,考虑到树分解方法的选择可能会影响HTEDI算法的效率。第五章详细对比MinFill的树分解方法和MinDegree的树分解方法,将MinFill的树分解方法应用于HTEDI算法,与采用MinDegree的HTEDI算法进行对比,通过实验分析,证明采用MinFill比采用MinDegree方法在预处理部分的时间和空间上的结果都要好,同时最短路径查询计算速度得到提高。最后,本文给出了相关的结论,并对未来的工作进行展望。
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】

中国期刊全文数据库 前10条

1 肖金声;;关于最短路径算法[J];中山大学学报(自然科学版);1987年03期

2 马东岭;;城市公交网络的最短路径算法研究[J];科技信息;2008年26期

3 胡于杰;李响;;利用最短路径算法确定地理网络中心服务范围[J];地理与地理信息科学;2010年03期

4 郑年波;陆锋;李清泉;段滢滢;;顾及转向延误的时间依赖A~*最短路径算法[J];测绘学报;2010年05期

5 涂海丽;;最短路径算法及其应用探讨[J];科技广场;2011年09期

6 毛少武;张焕国;黄崇超;吴万青;;改进的K最短路径算法在通信网络中的应用[J];武汉大学学报(理学版);2013年06期

7 张效贤;最短路径算法的应用[J];甘肃高师学报;1999年02期

8 冯晓辉;;交通网络中的最短路径算法探索[J];计算机光盘软件与应用;2013年21期

9 窦桂琴;杨青;黄祖锋;王雪萍;;一种基于城市应急系统的最短路径算法[J];广西师范大学学报(自然科学版);2007年04期

10 欧福军;刘萍;涂亚平;吴海兵;;大规模网络最短路径算法的优化及实现[J];海南大学学报(自然科学版);2008年02期

中国重要会议论文全文数据库 前9条

1 王闯;董志江;;最短路径算法[A];吉林省测绘学会2008年学术年会论文集（下）[C];2008年

2 唐小勇;程琳;徐上;;考虑转向延误最短路径算法及实现[A];2007第三届中国智能交通年会论文集[C];2007年

3 陈再春;张云青;潘伯鸣;;最短路径算法在公交查询中的实现[A];首届长三角科技论坛数字区域建设与地理空间技术论坛优秀论文集[C];2004年

4 罗飞;魏开平;万润泽;;复杂网络中最短路径算法的研究及应用[A];2006全国复杂网络学术会议论文集[C];2006年

5 王明福;彭群生;;基于编码图的求解最短路径算法[A];中国计算机图形学进展2008--第七届中国计算机图形学大会论文集[C];2008年

6 孙绍河;朱瑞艳;;GIS中最短路径算法的研究[A];第二届“测绘科学前沿技术论坛”论文精选[C];2010年

7 张惠谦;;电信规划最短路径算法的Excel宏实现[A];中国通信学会信息通信网络技术委员会2005年年会论文集[C];2005年

8 王冬;张丽果;杜慧敏;韩俊刚;;基于R-Torus结构和最短路径算法的NoC建模[A];全国第19届计算机技术与应用（CACIS）学术会议论文集（上册）[C];2008年

9 冯盼盼;蔺宏伟;于金辉;;投影法生成网格上的路径[A];第六届全国几何设计与计算学术会议论文集[C];2013年

中国博士学位论文全文数据库 前1条

1 廖远;一对一最短路径算法研究及车载导航系统设计[D];南昌大学;2012年

中国硕士学位论文全文数据库 前10条

1 吕志超;面向资源优化配置的集群航天器网络拓扑管理研究[D];哈尔滨工业大学;2015年

2 汤博蔚;基于云计算的智能交通系统[D];南京邮电大学;2015年

3 尹伊伊;基于A*算法的多目标和约束条件下的k优换乘方案研究[D];中国铁道科学研究院;2015年

4 罗丽虹;考虑转向限制的路网中最短路径算法研究[D];清华大学;2015年

5 郭东;基于Virtools的煤矿井下逃生系统的研究[D];太原理工大学;2016年

6 吴友宝;Hadoop平台下基于路网加权分层和关联规则的最短路径算法研究[D];华南理工大学;2016年

7 陈志芳;基于最短路径算法的高速路网建模与实证研究[D];合肥工业大学;2016年

8 何亚琦;基于GPS轨迹的移动端最短网络距离推荐系统[D];湖南科技大学;2016年

9 冀陆兵;HTEDI算法的实现和改进[D];西南交通大学;2017年

10 邓礼礼;求图中受限制的所有最短路径算法的分析与研究[D];华东师范大学;2009年

，

本文编号：1276792