随着经济的发展,城市的地理信息数据呈爆炸式增长且城市路网的结构也变得日益复杂。能否从复杂的城市路网中几乎实时地找出从出发地到目的地的最短路线越发受到老百姓的关注。A星算法作为一种经典的启发式寻路算法,广泛用于城市交通寻路。随着时代的前进,多种改进A星算法已被人们提出。其中以二叉堆存储’结构代替传统OPEN表的线性存储结构的改进令人瞩目,虽效率提升明显但逐渐难以满足用户需求。本文在此背景下对上述算法展开了研究。本文首先对图和图搜索算法相关知识进行了叙述,着重介绍本文研究对象——A星算法,对其进行分析并指出其瓶颈。接着简单介绍了已被人提出的A星算法改进方案。基于对上述改进方案的研究并结合较为成熟多核多线程技术,本文提出了两种算法改进方案。第一种方案是节点并行扩展及OPEN表分治并行查找最小代价值节点。该方案让节点扩展时可以在邻接节点代价值计算、节点是否在OPEN表和CLOSE表中等耗时读操作上由多个子线程并行进行,而OPEN表添加节点或更改节点代价值、CLOSE表添加节点等写操作由主线程串行进行。同时,为了减少查找OPEN表中最小代价值节点的时间,基于“分治”思想,提出将OPEN表分成多个节点更少的表,由多线程并行实现二叉堆存储,每个线程找出单个表的最小代价值节点后交由主线程得出全局的最小代价值节点。另一种方案是双向并行运行寻径。该方案提出开启两个线程同时分别从起始节点和目标节点分别朝对方寻径,两个线程各独自拥有OPEN表但共用一个CLOSE表且对此表进行同步处理,当其中一个线程从其独自拥有的OPEN表中找到的最小值节点放入CLOSE表中时,若发现该节点已存在于CLOSE表中并被另一个线程标记,表明路径已经找到。经分析,此算法只适用于两节点间的最短路径只存在一条或多条但多条路径间有重合节点。最后,实验表明在路网较为复杂、起始节点和目标节点距离较远时,两种改进方案有着良好的性能。