在有过境节点的道路网络中快速路由
Holger Bast1, Stefan Funke, Peter Sanders
1Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany.
Science (New York, N.Y.)
|April 28, 2007
概括
过境节点路由大大加快了道路网络中最快路径查询的速度. 这种算法方法将复杂的计算减少到简单的表查询,以数量级提高性能.
科学领域:
- 计算机科学 计算机科学
- 算法学的算法学
- 网络分析 网络分析
背景情况:
- 在道路网络分析中,最快路径查询是基本的.
- 对于大型道路网络而言,现有的算法可能是计算密集的.
研究的目的:
- 为高效的最快路径查询开发一种新的算法方法.
- 在道路网络中显著降低路由的计算复杂性.
主要方法:
- 引入了运输节点路由算法.
- 将最快路径查询减少到一组最小的表查询.
- 在西欧和美国的道路地图上测试了算法.
主要成果:
- 实现了查询倍数的两个数量级的速度比以前的最佳在路线图.
- 演示性能比一般网络算法快一百万倍以上.
- 验证了运输节点路由方法的效率和可扩展性.
结论:
- 过境节点路由为道路网络中最快路径问题提供了高效的解决方案.
- 该方法为现实世界的路由应用程序提供了实质性的性能改进.
- 这种算法进步对导航和物流系统有重大影响.
相关概念视频
02:12Short-distance Transport of Resources
Short-distance transport refers to transport that occurs over a distance of just 2-3 cells, crossing the plasma membrane in the process. Small uncharged molecules, such as oxygen, carbon dioxide, and water, can diffuse across the plasma membrane on their own. In contrast, ions and larger molecules require the assistance of transport proteins due to their charge or size. Transport across membranes also occurs within individual cells, playing a variety of essential roles for the plant as a whole.
01:11IP3/DAG Signaling Pathway
Membrane lipids such as phosphatidylinositol (PI) are precursors for several membrane-bound and soluble second messengers. Specific kinases phosphorylate PI and produce phosphorylated inositol phospholipids. One such inositol phospholipids are the phosphatidylinositol-4,5 bisphosphate [PI(4,5)P2], present in the inner half of the lipid bilayer. Upon ligand binding, GPCR stimulates Gq proteins to turn on phospholipase Cꞵ. Activated phospholipase Cꞵ cleaves PI(4,5)P2 and produces two-second...
01:11Direct Motor Pathways
The direct motor pathways, also known as the pyramidal tracts, are a group of neural pathways that originate in the brain and descend through the spinal cord. They control the voluntary movement of the body. There are two major direct motor pathways: the corticospinal and the corticobulbar tracts.
The corticospinal tract is responsible for the voluntary movement of the limbs and trunk. It originates in the cerebral cortex of the brain and descends through the cerebrum's internal capsule and the...
The corticospinal tract is responsible for the voluntary movement of the limbs and trunk. It originates in the cerebral cortex of the brain and descends through the cerebrum's internal capsule and the...
01:22Indirect Motor Pathways
The indirect motor or extrapyramidal pathways originate in the brainstem, the lower portion of the brain that connects it to the spinal cord. They consist of several distinct tracts, each with specialized functions. The four main tracts of the indirect motor pathways are the vestibulospinal tract, the reticulospinal tract, the tectospinal tract, and the rubrospinal tract.
The vestibulospinal tract originates in the vestibular nuclei of the brainstem. The vestibular system detects changes in...
The vestibulospinal tract originates in the vestibular nuclei of the brainstem. The vestibular system detects changes in...
01:24Fast Decoupled and DC Powerflow
The fast decoupled power flow method addresses contingencies in power system operations, such as generator outages or transmission line failures. This method provides quick power flow solutions, essential for real-time system adjustments. Fast decoupled power flow algorithms simplify the Jacobian matrix by neglecting certain elements, leading to two sets of decoupled equations:
01:17Design Example: Alignment of a Road Line Using GIS
The alignment of a road line using Geographic Information Systems (GIS) is a critical process in civil engineering, combining advanced technology with practical decision-making. This methodology begins with the collection of geospatial data, including information on land cover, geomorphology, drainage patterns, slope, and contour details. Such data is typically acquired through satellite imagery and GIS tools, offering a comprehensive understanding of the terrain.Once the data is gathered, it...