改进的Highway Hierarchical算法：无环压缩与高效存储策略

"基于路网压缩策略的改进Highway Hierarchical算法 (2012年)"，作者：蔡文学，周兴，许靖，钟慧玲，发表于《同济大学学报(自然科学版)》2012年第40卷第11期。 这篇论文主要探讨了针对Highway Hierarchical算法的优化，该算法常用于路径规划问题。Highway Hierarchical算法是一种高效的道路网络路径查找算法，但在实际应用中存在一些挑战，包括路网压缩过程中形成环路的问题、预处理数据的存储难题以及完整最短路径计算的复杂性。 首先，论文提出了一种无环压缩策略，以解决路网压缩成环的问题。在原始算法中，路网压缩可能导致某些路段相互连接形成环路，这会增加计算复杂性和可能导致路径查找错误。通过实施无环压缩，算法避免了这种现象，减少了不必要的计算，并提高了路径查找的准确性。 其次，为了改善预处理数据的存储，论文引入了分层存储策略。传统的Highway Hierarchical算法可能需要大量存储空间来保存所有节点和边的信息。分层存储将路网数据结构化，将节点和边按照层次划分，使得数据的访问和更新更为高效，从而降低了存储需求。 再者，论文还提出了局部最短路存储策略，以应对完整最短路计算的问题。在大规模路网中，计算所有节点之间的最短路径可能会非常耗时。局部最短路存储策略则只存储和更新关键节点之间的最短路径，降低了计算复杂度，显著提升了时间效率。 根据广东省路网的测试结果，这些改进使得新算法的时间效率相对于原算法提高了约5倍，空间效率提高了约4倍。这意味着优化后的算法在处理同样规模的路网时，不仅能在更短的时间内找到最优路径，而且所需的内存资源也大大减少，这对于实时交通导航系统和其他依赖路径规划的应用具有重大意义。 这篇论文通过提出无环压缩、分层存储和局部最短路存储等策略，成功地优化了Highway Hierarchical算法，使其在时间和空间效率上得到了显著提升，对于解决大规模路网的路径规划问题提供了有效的方法。这些改进对于现代交通系统、物流管理和城市规划等领域具有重要的理论与实践价值。