基于PIN LRU算法的路网最短路径研究

摘要

在陕西省交通地理信息系统数据存储与导航的实际应用中,由于路网数据量庞大,直接利用最短路径算法计算会出现内存溢出,导致无法完成计算。针对此问题,本文提出利用R Tree与最近最少使用(Least Recently Used,LRU)算法缓存优化管理相结合的锁定最近最少使用(Pin Least Recently Used,PIN LRU)算法对实际路网进行最短路径计算。与LRU、基于四叉树的空间数据缓存策略模型(Spatial Least Recently Frequently Used,SLRFU)算法相比,该算法在10个途经点路径检索时的耗时为5000 ms,SLRFU算法耗时为30000 ms,LRU算法耗时为75000 ms。试验测试证明,该算法检索响应高效,可解决计算实际数据过程中因内存溢出而导致系统崩溃的问题。