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

doi:10.3778/j.issn.1002-8331.1610-0296

计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (15): 57-62.DOI: 10.3778/j.issn.1002-8331.1610-0296

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

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

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

出版日期:2017-08-01 发布日期:2017-08-14

Dynamic pruning search algorithm that must go through certain node set

YAO Bo1, FENG Hongwei1, GAO Yuan2, MA Jiali1, FENG Jun1

1.School of Information Science and Technology, Northwest University, Xi’an 710127, China
2.School of Economics and Management, Northwest University, Xi’an 710127, China

Online:2017-08-01 Published:2017-08-14

摘要/Abstract

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

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

Abstract: A depth first search algorithm based on dynamic pruning strategy is presented to solve the problem of shortest path must go through some certain nodes. This algorithm constructs a two-dimensional matrix, it is need to compare the weight 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 shows that when the number of must go through nodes is less than 50, the algorithm can find an approximateshortest path in 30 s.

Key words: dynamic pruning, depth first search, shortest path

姚博1，冯宏伟1，高原2，马佳丽1，冯筠1. 过必经节点集的动态剪枝搜索算法[J]. 计算机工程与应用, 2017, 53(15): 57-62.

YAO Bo1, FENG Hongwei1, GAO Yuan2, MA Jiali1, FENG Jun1. Dynamic pruning search algorithm that must go through certain node set[J]. Computer Engineering and Applications, 2017, 53(15): 57-62.

[1]	李俊. 结合最短路径改进的社会力人群疏散仿真模型[J]. 计算机工程与应用, 2021, 57(8): 264-270.
[2]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[3]	李艳，王阳阳，张红岩，武优西. 不可达顶点剪枝算法及其在最短路径中的应用[J]. 计算机工程与应用, 2020, 56(15): 51-57.
[4]	张昕，严沛，郭阳，王慧慧. 基于k-shell的复杂网络最短路径近似算法[J]. 计算机工程与应用, 2019, 55(14): 54-60.
[5]	张林霞，何利文，黄俊. 基于SDN网络的安全设备路由研究[J]. 计算机工程与应用, 2018, 54(4): 103-109.
[6]	高遵海，高颖，程果. 图的赋权路径矩阵与所有点对最短路径问题[J]. 计算机工程与应用, 2017, 53(9): 47-50.
[7]	钟德云，王李管，毕林，王晋淼. 复杂风网井下循环风快速搜索算法[J]. 计算机工程与应用, 2017, 53(8): 235-239.
[8]	应文杰，徐开，徐少平. 羽毛球机器人机械臂运动轨迹多目标规划[J]. 计算机工程与应用, 2017, 53(3): 258-265.
[9]	张辰，李红军，罗柳红，何英豪. 等价关系矩阵的置换合同性质与标准形计算[J]. 计算机工程与应用, 2017, 53(13): 42-48.
[10]	袁亚博，刘羿，吴斌. 改进蚁群算法求解最短路径问题[J]. 计算机工程与应用, 2016, 52(6): 8-12.
[11]	韩建妙，刘业政. 基于遗传算法的超市最短导购路径推荐[J]. 计算机工程与应用, 2016, 52(4): 238-242.
[12]	孟颖翔1，高东怀2，许浩2，许卫中2. 基于最短路径的多子网链路层拓扑发现算法[J]. 计算机工程与应用, 2016, 52(2): 131-134.
[13]	侯晓琴1，胡志华1，高超峰1，罗勋杰2. 自动化仓库巷道网络AGV货区遍历优化——设计基于优先权遗传算法实现[J]. 计算机工程与应用, 2016, 52(12): 31-36.
[14]	吴幸良，涂风华. 采用图模型的个性化标签推荐方法[J]. 计算机工程与应用, 2015, 51(9): 142-146.
[15]	黄书力，胡大裟，蒋玉明. 经过指定的中间节点集的最短路径算法[J]. 计算机工程与应用, 2015, 51(11): 41-46.

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

Dynamic pruning search algorithm that must go through certain node set

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics