过必经节点集的动态剪枝搜索算法

来源：计算机工程与应用杂志2017年第15期北京时间：

作者：姚 博1，冯宏伟1，高 原2，马佳丽1，冯 筠1

单位：1.西北大学 信息科学与技术学院，西安 710127 ；2.西北大学 经济管理学院，西安 710127

摘要：针对过必经节点集的最短路径问题，提出一种基于动态减枝策略的深度优先搜索算法（Depth First Search based on Dynamic Pruning，DP-DFS），该算法构建一个二维矩阵，每搜索一个节点，比较当前路径的权值和与矩阵中已保存的权值，如果当前路径的权值小于矩阵中保存的权值，则更新矩阵中权值为当前较小的路径权值，否则进行剪枝。该算法比较适合较大规模的图搜索，实验表明，必经节点个数在50以内时，利用该算法可以在30?s内找到一条近似最优的最短路径。

关键词：动态剪枝,深度优先搜索,最短路径