- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
一种基于路网跃迁的高效路径有哪些信誉好的足球投注网站算法.doc
一种基于路网跃迁的高效路径有哪些信誉好的足球投注网站算法
摘要:针对移动导航设备内存小、运算能力相对弱的特点,以分级分幅路网模型为基础,设计了一种新的以“路网跃迁”为核心思想的高效最优路径有哪些信誉好的足球投注网站算法,并应用到实际产品中。实践表明,该有哪些信誉好的足球投注网站算法具有计算速度快、消耗内存低、路线质量总体接近最优等优点。
关键词:分级;分幅;路网跃迁;路径有哪些信誉好的足球投注网站算法
中图分类号:TP311 文献标识码:A 文章编号:1009-3044(2015)30-0073-02
An Efficient Route Search Algorithm Based on Road Transition
WU Juan, GAO Zheng-dong
(SCTV, Shucheng 231300, China)
Abstract: Corresponding to the shortage of having less memory and weaker compute capability within mobile navigation device, a new efficient best route search algorithm based on road classification and map sheet, which takes “road transition” as key point, is implemented and has being applied to the real products. Practice has shown that it has advantage of faster speed, less memory occupation, and perfect route quality, etc.
Key words: road classification; map sheet; road transition; route search algorithm
1 概述
为了适应车载设备内存低、运算能力相对较弱的特点,我们对路网进行了分级和分幅处理。分级指的是将路网根据道路属性分成多个等级,如将地区内路网分成三级(0级,1级,2级),将全国路网分成两个等级(3级、4级);分幅指的是将整个路网网格化,每个网格覆盖路网一定的区域,如10公里*10公里区域范围。分级的好处是允许有哪些信誉好的足球投注网站过程从低级路网跃迁到高级路网,加快有哪些信誉好的足球投注网站速度;分幅的好处是降低有哪些信誉好的足球投注网站的节点空间,降低内存占用率。关于分级分幅路网数据组织格式的详细介绍可参阅文献[1]。
在分级分幅路网数据做支撑的基础上,我们改进了经典的Dijkstra算法,引入路网跃迁机制,设计了高效的双向启发式最优路径有哪些信誉好的足球投注网站算法。经典的Dijkstra算法已产生许多变体[2-3],总的来说,现有最优路径有哪些信誉好的足球投注网站算法基于的均不是分级和分幅的地图数据,因此本算法首先在基础数据层次上对时空效率的提高提供了有力保证。
2 算法描述
为了保证快速的有哪些信誉好的足球投注网站过程和良好的路线质量,我们对算法做了多方面的改进,主要有:利用四叉堆进行节点排序、双向有哪些信誉好的足球投注网站、优化的代价函数、路网跃迁以及路网图幅化。通过将地区内路网和全国路网进行分级分幅化处理,在所有类型路网上都支持路网跃迁操作。以下详细描述算法的有哪些信誉好的足球投注网站过程,算法原理示意图如图1所示:
有哪些信誉好的足球投注网站算法用到三个地图数据:发源地区路网、目的地区路网、全国路网。根据出发点和目的点所在地区位置,将有哪些信誉好的足球投注网站算法分为以下三类:
1)地区内有哪些信誉好的足球投注网站:出发点和目的点都在同一地区内,则有哪些信誉好的足球投注网站仅在本地区范围内进行,不需要有哪些信誉好的足球投注网站全国路网,有哪些信誉好的足球投注网站过程相对最简单。
2) 相邻地区有哪些信誉好的足球投注网站:出发点和目的点不在同一地区,但地区内有哪些信誉好的足球投注网站到达的边界点存在重合,即一个地区的地区边界点同时也是另一个地区的地区边界点,此时也不需要有哪些信誉好的足球投注网站全国路网。
3) 跨地区有哪些信誉好的足球投注网站:当出发点和目的点既不在同一地区,也不发生两个地区边界点重合时,就必须借助全国路网有哪些信誉好的足球投注网站两个地区之外的路线。
以下给出跨地区算法描述,地区内有哪些信誉好的足球投注网站和相邻地区有哪些信誉好的足球投注网站是跨地区有哪些信誉好的足球投注网站的特例情况,不再详述。
1) 由发源点经纬度找到发源最近路段;
2) 由发源最近路段选择某个端点作为出发点;
3) 由目的点经纬度找到目的最近路段;
4) 由目的最近路段选择某个端点作为到达点;
5) 以到达点为目的点,从发源地区正向有哪些信誉好的足球投注网站到一条到达节点是地区边界点S’的路线L1;
6) 以出发点为出发点,从目的地区逆向有哪些信誉好的足球投注网站到一条前驱节点是地区边界点D’的路段L2;
7) 将源地区边界点S’向全国路网投影,找到其在全国路网上的投影节点 Sp;
8) 将目的地区边界点D’向全国路网投影,找
文档评论(0)