Modelling a Hierarchy of Space Applied to Large Road Networks
Modelling a Hierarchy of Space Applied to Large Road Networks
复制标题
DOI：
10.1007/3-540-58795-0_30
复制
发表时间：
1994-02
期刊：
影响因子：
--
通讯作者：
A. Car;A. Frank
中科院分区：
文献类型：
--
作者：
A. Car;A. Frank
人类广泛使用层次结构来简化他们对现实的概念模型，并更有效地进行推理。层级结构在概念上强加于空间，并允许在非常大的上下文中更好地执行复杂任务。理解空间层次是如何形成和使用的，是空间推理研究中最重要的问题之一。在本项目中，大型路网中的寻路作为一个特例进行了研究。应用分层策略，即使在非常大的街道网络中，人类也可以快速找到最快的路径。标准的非分层算法的性能会随着网络规模的增加而迅速下降。可以从街道类别(高速公路、高速公路、地方道路)的层次结构中抽象出层次结构。这减少了搜索过程中涉及的节点数量，并允许在子网络中更有效地执行搜索过程。我们提出了一个在最高可能级别的子图中搜索最优路径的算法。这导致了有效的寻路算法，即使在最短路径的标准简单图搜索算法变得不够用的情况下也是如此。
Human beings use hierarchies extensively to simplify their conceptual models of reality and to perform reasoning more efficiently. Hierarchical structures are conceptually imposed on space and allow better performance of complex tasks in very large contexts. To understand how spatial hierarchies are formed and used is one of the most important questions in spatial reasoning research. In this project, wayfinding in large road networks is studied as a particular case. Humans can find fastest paths even in very large street networks quickly, applying a hierarchical strategy. Standard, non-hierarchical algorithms show performance that degrades rapidly with increasing network size. A hierarchical structure can be found as an abstraction from the hierarchy of street classes (expressway, highway, local road). This reduces the number of nodes involved in a search process, and allows to perform the search process in subnetworks more efficiently. We propose an algorithm which searches for an optimal path in the subgraph of the highest possible level. This leads to an efficient wayfinding algorithm, even where standard simple graph search algorithms for the shortest path become inadequate.