检索规则说明:AND代表“并且”;OR代表“或者”;NOT代表“不包含”;(注意必须大写,运算符两边需空一格)
检 索 范 例 :范例一: (K=图书馆学 OR K=情报学) AND A=范并思 范例二:J=计算机应用与软件 AND (U=C++ OR U=Basic) NOT M=Visual
机构地区:[1]上海海事大学信息工程学院,上海201306 [2]同济大学电子与信息工程学院,上海201804
出 处:《计算机科学》2016年第6期188-193,247,共7页Computer Science
基 金:国家自然科学基金项目(61202370);上海市教委科研创新项目(14YZ110);中国博士后科学基金资助项目(2014M561512)资助
摘 要:针对大规模城市路网寻找最短路径的问题,提出了一种基于边的聚类树(ECT)和最小封闭格(MCL)的算法来达到路网中快速查询的目的。首先对给定的城市路网进行预处理,即利用封闭格的定义对路网进行划分;其次利用ECT树对划分出的MCL格进行存储;最后利用虚拟路径的思想(两点之间直线距离最短)并结合MCL格的性质和路网的平面性的特点,利用ECT树存储的优势,在查询中大大减少了无用节点的访问数量,降低了时间复杂度,从而达到了快速寻找最短路径的目的。理论分析和仿真实验表明,在大规模的城市路网中ECT树的存储空间相比PCPD算法减少了约45.56%,相比TNR算法减少了24.35%,其在存储方面略优于较为完备的SILC算法。MCL算法在查找过程中的搜索效率比SPB算法快15.6%。实验结果表明基于ECT存储的MCL算法在实际查询过程中能提高查询的效率。Concerning the problem of finding the shortest path in the large scale city road network, this paper proposed an algorithm based on the Edge Clustering Tree and Minimal Closed Lattice to achieve the goal of quick searching. Firstly, the city road network is proproeessed,i, e. using the definition of the MCL to classify the road network. Then ErIC is used to storage the MCL. Eventually, depending on the idea of the virtual path(the shortest distance between two points is the straight line distance), combining the attribute of MCL planarity of the road network and taking ad- vantage of the ECT will dramatically reduce the visits to dud nodes. So this kind of algorithm really reduces the time complexity and achieves the purpose of quick searching. The theoretical analysis and the simulation experiment demon- strate that the storage space of ECT is 45.56% less than the PCI)C algorithm and 24. 35% less than TNR. In the aspect of storage, ECT is slightly better than SILC. Besides, the query efficiency of the MCL is 15.60/0 faster than that of the SPB. The results of the experiment suggest that the MCL algorithm based on ETC storage can improve the query efficiency.
分 类 号:TP311.13[自动化与计算机技术—计算机软件与理论]
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在载入数据...
正在链接到云南高校图书馆文献保障联盟下载...
云南高校图书馆联盟文献共享服务平台 版权所有©
您的IP:216.73.216.171