摘要
针对过必经节点集的最短路径问题,提出一种基于动态减枝策略的深度优先搜索算法(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.
作者
姚博
冯宏伟
高原
马佳丽
冯筠
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)
出处
《计算机工程与应用》
CSCD
北大核心
2017年第15期57-62,共6页
Computer Engineering and Applications
基金
陕西省自然科学基金(No.2014JQ8367)