计算机工程与应用Issue(15)：57-62,6.DOI:10.3778/j.issn.1002-8331.1610-0296
过必经节点集的动态剪枝搜索算法
Dynamic pruning search algorithm that must go through certain node set
摘要
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分类
信息技术与安全科学引用本文复制引用
姚博,冯宏伟,高原,马佳丽,冯筠..过必经节点集的动态剪枝搜索算法[J].计算机工程与应用,2017,(15):57-62,6.基金项目
陕西省自然科学基金(No.2014JQ8367). （No.2014JQ8367）
