最短路径问题是图论分析与算法设计等理论研究中的经典问题,也是物流规划、行车导航等实际应用领域中的基本问题。由于Q学习算法具有环境无关性和离线学习的优点,无需建立具体的环境模型便可对最短路径进行求解,同时其离线学习的特性易于与其他优化算法相结合,因此在求解最短路径问题方面取得较好的效果。本文针对Q学习算法前期搜索空间大、中期搜索慢、后期收敛不稳定等缺点,研究基于改进Q学习算法的最短路径问题。针对Q学习算法前期搜索空间大和后期难以稳定收敛的问题,本文提出基于多头绒泡菌的自适应选择Q学习算法(Adaptive Choosing Q-learning based on Physarum Polycephalum Algorithm,ACQPPA)。ACQPPA通过多头绒泡菌算法对网络模型进行预处理,筛选出次优路径作为Q学习算法的初始Q值矩阵,减少Q学习算法前期的搜索空间;同时利用改进的模拟退火算法对探索策略进行动态处理,令探索策略随算法推进逐步降低,保证算法前期解的多样性算法及后期的稳定收敛。仿真结果表明,在网络节点数量为128的情况下,ACQPPA算法收敛到最优路径成功率为100%,高于ACO算法和Q(λ)算法的80%,其迭代次数分别低于Q学习算法57.2%、ACO算法32.9%和Q(λ)算法35.1%。针对Q学习算法中期搜索慢的问题,并为进一步提升多头绒泡菌算法预处理网络的效率,本文提出基于网络压缩的双向ACQPPA算法(Bidirectional ACQPPA based on Network Compression,B-ACQPPANC)。B-ACQPPANC利用CH算法(Contraction Hierarchies)缩小网络规模,减少多头绒泡菌算法预处理网络时的耗时;同时将双向探索的思想与Q学习算法相结合,将反向探索结果作为正向探索的先验知识进行储备,加快算法探索速度。对比仿真结果表明,B-ACQPPANC算法的平均成功收敛次数降低43.26%,同时Q学习算法和Q(λ)算法平均成功收敛次数分别降低39.40%和29.76%,同时改进后的B-ACQPPANC收敛到最优路径成功率为100%,高于B-QNC算法的80%和B-Q(λ)NC算法的20%。