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

Dynamic pruning search algorithm that must go through certain node set

作　　者：姚博[1] 冯宏伟[1] 高原[2] 马佳丽[1] 冯筠[1] YAO Bo;FENG Hongwei;GAO Yuan;MA Jiali;FENG Jun(School of Information Science and Technology, Northwest University, Xi’an 710127, China;School of Economics and Management, Northwest University, Xi’an 710127, China)

机构地区：[1]西北大学信息科学与技术学院,西安710127 [2]西北大学经济管理学院,西安710127

出　　处：《计算机工程与应用》2017年第15期57-62,共6页Computer Engineering and Applications

基　　金：陕西省自然科学基金(No.2014JQ8367)

摘　　要：针对过必经节点集的最短路径问题,提出一种基于动态减枝策略的深度优先搜索算法(Depth First Search based on Dynamic Pruning,DP-DFS),该算法构建一个二维矩阵,每搜索一个节点,比较当前路径的权值和与矩阵中已保存的权值,如果当前路径的权值小于矩阵中保存的权值,则更新矩阵中权值为当前较小的路径权值,否则进行剪枝。该算法比较适合较大规模的图搜索,实验表明,必经节点个数在50以内时,利用该算法可以在30 s内找到一条近似最优的最短路径。A depth first search algorithm based on dynamic pruning strategy is presented to solve the problem of shortestpath must go through some certain nodes.This algorithm constructs a two-dimensional matrix,it is need to compare theweight of current node and the saved matrix when visits a node.If the weight of current node is less than that in matrix,update the weight in matrix as the mix weight,or prune.The algorithm is suitable for large scale graph,experiment showsthat when the number of must go through nodes is less than50,the algorithm can find an approximateshortest path in30s.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]