车载导航系统中带方向矩形限制的最优路径算法

摘要

计算机科学中的最优路径算法由于在计算过程中主要考虑的是网络的拓扑结构，忽略了网络可能具有的空间分布特征，从而在路径搜索的过程中使用的是全方向的搜索，因此在计算的过程中会存在大量的冗余节点。在有关地理信息系统的应用中，空间分布是空间数据隐含的重要特征。在道路网络中，给定了起点和终点，实际上就给出了两点之间所包含的空间关系，比如起点和终点问的方向关系、距离关系、势力范围等等。在计算最优路径的过程中应当充分考虑这些空间分布特征属性以缩小搜索的范围，降低的数据冗余度，提高计算效率。在本文中我们以交通网络为例，给出了带方向矩形限制的最优路径算法，并验证了给出算法的有效性。