.png){kind=icon}
返回
Efficient fastest-path computations for road maps
.png){kind=icon}
OA
AI
DOI：10.1007/s41095-021-0211-2.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In the age of real-time online traffic information and GPS-enabled devices, fastest-path computations between two points in a road network modeled as a directed graph, where each directed edge is weighted by a travel time value, are becoming a standard feature of many navigation-related applications. To support this, very efficient computation of these paths in very large road networks is critical. Fastest paths may be computed as minimal-cost paths in a weighted directed graph, but traditional minimal-cost path algorithms based on variants of the classical Dijkstra algorithm do not scale well, as in the worst case they may traverse the entire graph. A common improvement, which can dramatically reduce the number of graph vertices traversed, is the A* algorithm, which requires a good heuristic lower bound on the minimal cost. We introduce a simple, but very effective, heuristic function based on a small number of values assigned to each graph vertex. The values are based on graph separators and are computed efficiently in a preprocessing stage. We present experimental results demonstrating that our heuristic provides estimates of the minimal cost superior to those of other heuristics. Our experiments show that when used in the A* algorithm, this heuristic can reduce the number of vertices traversed by an order of magnitude compared to other heuristics.
Keyword:
shortest-path
road map
heuristic
GPS navigation
A* search
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
18.3
论文数:
319
被引数:
2.6K
机构
引用论文
Does it take older adults longer than younger adults to perceptually segregate a speech target from a background masker?在感知上将语音目标与背景掩蔽器隔离开来是否需要老年人比年轻人更长的时间？
PREAI
分享收藏
分享收藏PVDF layer as a separator on the solution-side of air-cathodes: the electricity generation, fouling and regeneration.png)
RSC Advances
RSC AdvancesIF0
PREAI
分享收藏分享收藏
查看更多内容