论文研究过必经节点集的动态剪枝搜索算法.pdf

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