基于深度优先搜索的分层网络最短路径算法.pdf

684 Radio Communications TechnologyVol.49 No.4 2023doi:10.3969/j.issn.1003-3114.2023.04.012引用格式:侯艳丽,马震.基于深度优先搜索的分层网络最短路径算法J.无线电通信技术,2023,49(4):684-688.HOU Yanli,MA Zhen.Hierarchical Network Shortest Path Search Algorithm Based on Depth-first SearchJ.Radio Communications Technology,2023,49(4):684-688.基于深度优先搜索的分层网络最短路径算法侯艳丽,马 震(河北科技大学 信息科学与工程学院,河北 石家庄 050018)摘 要:大规模网络分层后进行数据预处理是其搜索最短路径的加速方法,现有的分层网络数据预处理存在以下问题:随着网络规模越来越大,数据预处理计算量也越来越大;预处理完的数据需要大量储存空间。针对上述问题提出一种基于深度优先搜索的分层网络最短路径搜索算法,该算法将每簇网络抽象成“一个高级节点”组成高级网络,在高级网络上利用深度优先搜索去掉冗余的簇完成数据预处理后,再利用 Dijkstra 算法搜索最短路径。采用该算法在大规模树形分层通信网络上进行最短路径搜索实验,结果表明该算法比基于关键点数据预处理的最短路径算法平均搜索时间稍长,但在数据预处理时间和存储空间上大大降低。关键词:分层网络;最短路径;数据预处理;深度优先搜索;Dijkstra中图分类号:TN915.01 文献标志码:A 开放科学(资源服务)标识码(OSID):文章编号:1003-3114(2023)04-0684-05Hierarchical Network Shortest Path Search Algorithm Based on Depth-first SearchHOU Yanli,MA Zhen(School of Information Science and Engineering,Hebei University Science and Technology,Shijiazhuang 050018,China)Abstract:Large scale network layering followed by data preprocessing is an accelerated method for searching for the shortest path,and existing hierarchical network data preprocessing has following problems:as the network scale becomes larger,the amount of data preprocessing calculation becomes larger,and preprocessed data requires a lot of storage space.This paper proposes a layered network shortest path algorithm based on depth-first search,which abstracts each cluster network into“one high-level node”to form a high-level network,uses deep-first search to remove redundant clusters networks on the high-level network to complete data preprocessing,and then uses Dijkstra algorithm to search for the shortest path.Shortest path search experiment on large-scale tree hierarchical communication network is carried out using the proposed algorithm,and results show that the proposed algorithm has a slightly longer average search time than the shortest path algorithm based on data preprocessing of key nodes,but the data preprocessing time and storage space are greatly reduced.Keywords:hierarchical network;shortest path;data preprocessing;depth-first search;Dijkstra收稿日期:2023-03-17基金项目:河北省重点研发计划(21355901D)Foundation Item:Hebei Provincial Key Research and Development Pro-garm of China(21355901D)0 引言最短路径问题一直是图论中经典的算法问题,在通信工程、运筹学、计算机科学、交通运输等学科领域都有着举足轻重的地位。针对单源最短路径问题最经典的算法是 Dijkstra 算法1-3,该算法复杂度较低,能够得到最优解。由于 Dijkstra 算法不适用负权图,对于单源负权图最短路径问题美国应用数学家理查德-贝尔曼提出了解决办法4-6,对图进行最多 V-1 次松弛操作得到所有可能的路径,但该算法复杂度极高,文献7-8优化了此算法,提出了最短路径快速算法(Shortest Path Faster Algorithm,SP-FA)。上述最短路径算法在搜索过程中搜索方向并2023年第49卷第4期无线电通信技术685 无指向性,文献9-11提出了 Astar 算法,该算法在搜索过程利用欧几里得距离或是切比雪夫距离引导路径搜索方向;受到 Astar 算法的启发,文献12提出了基于三角不等式的 ALT(Algorithmic Learning Theory)算法,但该算法由于受到地标节点的限制,求出的路径不一定是最短。近年来,随着科学技术的快速发展,交通运输网、通信网、社交网等网络结构变得越来越复杂,将复杂的网络分层是搜索最优路径的加速方法。Gei-sberger 等人13提出了一种仅基于节点收缩概念的路线规划技术,节点按“重要性”排序,然后通过迭代收缩最不重要的节点来生成层次结构。Song 等人14开发了一种基于社区的分层图模型,检测道路网络中的分层社区结构,该模型能够有效分层后适用于大型道路网的最优路径规划。分层后的网络层与层之间通信的节点为“关键点”,这些关键点可被作为先验信息进行数据预处理。Bast 等人15提出了 Transit-Node Routing 算法,将复杂网络分成不同区域后,在不同区域都有最短路径可能出入的节点即关键点,搜索这些关键点间的最短路径并储存起来,预处理的新网络有效去除了最短路径以外的一部分冗余边,大大提高搜索效率。由于层内网络数据预处理后的关键点间的最短路径可能有一定误差,文献16引入局部修正算法,在路径寻优的时候如果当前搜索到的关键点间的最短路径和数据预处理储存的不一样则进行局部修正;为了进一步在分层网络上提取能够减小搜索范围的有效信息,给出了基于子图终止技术的分层最短路径算法,该算法首先进行基于关键点的数据预处理,然后通过将搜索限定在最短路径经由的各超级节点所对应的子图区域来获取其最优路径,但是此算法数据预处理相对复杂,计算的时间成本也进一步增加。由以上分析可知,对大规模分层网络进行数据预处理,将耗费较多的预处理时间,同时也需要较大的储存空间。本文提出了一种基于深度优先搜索的最短路径算法。1 算法框架分层网络路径寻优时,从起点出发进行搜索,在搜索时很可能在不能到达终点的簇里进行无效搜索。过滤掉起点和终点间路径可能不会经过的簇能够有效减小搜索空间,提升搜索效率。首先把分层网络抽象成高级网络,再利用深度优先搜索在高级网络上进行数据预处理,然后在预处理后的网络上利用 Dijkstra 算法进行最短路径搜索。1.1 高级网络的抽象假设 k 簇无向网络 G=V,E,V 是全局顶点集合,E 是初始的边集合,第 i 簇 Gi=Vi,Ei(i=1,2,k),将第 i 簇抽象成一个高级节点 vi。每两个簇之间连接边数大于零时,这两簇之间只抽象成一条边连接且不考虑权重参数(权重默认为 1)。将所有高级节点 V=v1,v2,vk和抽象后的边 E=e1,e2,ek组成高级网络 N=V,E。1.2 高级网络数据预处理深度优先搜索(Depth-First Search,DFS)算法是一种用于遍历和搜索树或图的算法,该算法从图中某一个顶点出发走向与其连接的未曾被访问过的节点。如果与当前出发节点相邻的节点有多个没有被访问过,则随机选择其中一个节点,然后从该节点继续出发;如果深度搜索时,当前没有节点符合要求,退回之前访问的节点,找到该节点的邻接节点,如果有没被访问过的邻接节点就继续搜索,反之算法结束。针对图 1 所示网络进行深度优先搜索的搜索过程为:假设从节点 1 出发,节点 1 的邻接节点有 2 和3,这两个节点均未被访过,选择节点 2 继续出发;节点 2 的邻接节点有 1 和 4,但 1 被访问过则不被考虑,访问节点 4;节点 4 没有可继续搜索的点则回溯到节点 3,节点 3 的邻接节点 5 和 6 没有访问过,选择访问节点 5;节点 5 没有可继续访问的节点,退回节点 3,再访问节点 6。到此整个深度优先搜索算法结束,整个搜索过程为:1-2-4-3-5-6。图 1 网络结构Fig.1 Network structure在高级网络 N 上基于深度优先搜索的数据预处理具体步骤如下:将 V中的元素每两个组成一组得到所有可能的无顺序排列组合 C=(v1,v2),(v1,v3),(v1,v4),(vk-1,vk)。C 的每一个元素的两个高级节点分别作为686 Radio Communications TechnologyVol.49 No.4 2023起点 Start 和终点 End,如 C 中元素(v1,v2),v1作为起点,v2作为终点。在高级网络 N 中利用深度优先搜索找出起点和终点间可能经过的高级节点(簇),算法伪代码如算法 1 所示。将 C 中元素逐个输入算法,然后将每个输出数据储存起来。算算法法 1 1 寻寻找找起起点点和和终终点点间间所所有有路路径径经经过过的的高高级级节节点点输输入入:高级网络 N 的邻接矩阵 Graph;起点 Start;终点 End输输出出:起点和终点间所有路径经过的高级节点集合 Table1.初始化一个队列 queue 并将起点 Start 放入队列;2.初始化一个数组 path 为空;3.while(queue 不为空):4.访问队头顶点;5.标记队头顶点为已遍历;6.随机选取队头顶点未被遍历过的邻接点入队;7.If 队头顶点为 End:8.队列 queue 中的元素返回到数组 path;9.队列 queue 删除队头顶点;10.If队头顶点所有邻接点均被遍历过:11.队列 queue 删除队头顶点;12.删除数组 path 中重复出现的元素,并作为 Table 输出1.3 Dijkstra 算法搜索最短路径确定起点和终点分别属于哪一簇(高级节点),在前文的储存数据中找到起点和终点对应的高级节点之间路径所需要的高级节点,将这些高级节点对应的簇组成新的网络 H,在网络 H 上搜索起点和终点间最短路径。选择 Dijkstra 算法在网络 H 上搜索起点和终点间最短路径17-18,对于求解单源最短路径问题,该算法能够在得到最优解的情况下,通过在搜索到终点时停止来降低算法复杂度。设 Q 为网络中所有节点的集合;设一个集合 S,初始状态下仅有起点StartS;P 为 S 中节点的邻接点集合,P 满足 PS=;Lk为当前情况下,起点经过 S 中若干点到点k 的最短距离(kQ),初始 LStart=0,其他均为+。Dijkstra 算法具体描述如下:在Ln1,Ln2,Lnk(n1,n2,nk)P)找到最小值 Lni;将节点 ni添加到集合 S;更新集合 P。重复,直到终点 EndS 时,算法结束,LEnd即为从起点 Start 到终点 End 的最短路径长度。2 实验评估2.1 实验环境与数据规模实现本文所提算法的脚本语言是 python,编译器是 pycharm,硬件为 12th Gen Intel(R)Core(TM)i7-12700H 2.70 GHz。原始分层网络选择树形分层通信网络,树形拓扑通信网络适用于局域网环境和分层分域的战术通信网。树形分层网络数据分为骨干层、主干层、地区层、接入节点层、终端层,每一层网络有一到十几个子网络不等(本文称层内子网络为“簇”),每一层内簇与簇之间没有联系,可能会与上一层或者下一层的簇之间有连接。分层网络有 23 000 个节点,每个节点的度平均为 150,关键点每簇平均 187 个。原始分层网络抽象成高级网络 N 如图 2 所示,高级节点 0 为骨干层,高级节点 13 为主干层,高级节点410 为地区层,高级节点 1119 为接入节点层,高级节点 2029 为终端层。图 2 高级网络 NFig.2 Advanced network N2.2 实验分析在高级网络 N 上采用本文提出的基于深度优先搜索的预处理方法进行预处理,并与基于关键点的数据预处理方法比较,实验结果如表 1 所示。基于关键点的数据预处理速度极慢,是本文方法的4 267 倍,预处理后的数据所需的存储空间也是远超本文,是本文方法的 165 倍。可见本文提出的最短路径算法在数据预处理上优势明显。表 1 不同算法数据预处理成本对比Tab.1 Comparison of data preprocessing costs between different algorithms数据预处理方法预处理时间/s数据存储空间/kB基于关键点的数据预处理22 275.53608.7本文提出的数据预处理5.223.72023年第49卷第4期无线电通信技术687 数据预处理完成后进行最短路径搜索,首先随机生成 14 组起点和终点,如表 2 所示。然后分别采用 Dijistra 算法直接搜索(Dijkstra Searches directly,DS)、基于关键点数据预处理的最短路径算法(Shor-test Path Algorithm for Data Preprocessing Based Criti-cal Nodes,SPADPBCN)和本文提出的算法(Depth-First Search Shortest Path Algorithm,DFSSPA)搜索起点与终点间的最短路径。表 2 起点和终点组合Tab.2 Start and end point combinations组号1234567起点5 89016 7974 2782105 2291 21514 666终点19 10919 26013 7532 0696 9964 6064 327组号891011121314起点4 25618 39317 0783 1821 59619 18216 929终点12 79216 74213 58919 3081 29758810 602 图 3 是表 2 在存储数据中直接查找得到的所需簇的数量,3 种算法最短路径搜索时间如图 4 所示。图 3 需要的簇数量Fig.3 Number of clusters图 4 寻优速度对比Fig.4 Comparison of optimization speeds综合图 3 的 clu 曲线和图 4 的 DFSSPA 曲线,可以看出数据预处理后需要簇的数量越多,DFSSPA算法搜索时间越长,表明本文算法的效率受到高级网络 N 的复杂度影响。DFSSPA 算法平均搜索时间明显比 DS 算法短,仅为后者的 0.4 倍,可见 DFSSPA 算法对于大规模树形分层网络在路径寻优时能够减小搜索范围。对于不同的起点和终点,对比 DFSSPA 和 SPADPBCN算法搜索时间有不同结果,总的来说 DFSSPA 算法平均搜索时间比 SPADPBCN 算法长,是后者的1.24 倍,DFSSPA 算法最短路径搜索范围略大于SPADPBCN 算法。DS 算法和 DFSSPA 算法搜索第 1 组起点和终点间最短路径的结果如图 5 所示,两种算法搜索的最短路径经过的节点一致。(a)DS 算法搜索结果(b)DFSSPA 算法搜索结果图 5 最优路径Fig.5 Optimal path688 Radio Communications TechnologyVol.49 No.4 20233 结论本文提出一种分层网络最短路径算法,将分层网络抽象成高级网络 N,通过利用深度优先搜索在网络 N 上求得起点和终点间最短路径可能所需要的簇,将这些簇组成新的网络 H,然后 Dijkstra 算法在网络 H 上进行起点和终点间的最短路径搜索。实验结果表明,本文算法(DFSSPA 算法)在数据预处理阶段对比 SPADPBCN 算法有巨大优势,DFSS-PA 算法的最短路径搜索时间平均多了 0.24 倍,可见两个算法在最短路径搜索时间上处于同一水平,从综合性能上来看 DFSSPA 算法优于 SPADPBCN算法。DFSSPA 算法在数据预处理成本很低的情况下,在最短路径搜索时间上对比分层网络不做任何处理利用 DS 算法有着非常明显的优势,可见深度优先搜索能够过滤掉不需要的簇,进而缩小了 Dijk-stra 算法搜索范围,有效缩短了运行时间。参 考 文 献1 黄翼虎,孙久象.基于自动化码头的改进 Dijkstra 算法路径规划研究 J.电子设计工程,2023,31(8):37-41.2 郑弈,谢亚琴.基于 Dijkstra 算法改进的飞行器航迹快速规划算法J.电子测量技术,2022,45(12):73-79.3 宋江一,李丹,陈文博.融合 Dijkstra 和 PID 算法的室内移动机器人局部路径规划J.安徽工业大学学报(自然科学版),2023,40(1):59-64.4 周鑫,张晶.实例解析 Bellman-ford 和 Spfa 算法J.电脑知识与技术,2021,17(30):79-81.5 臧洋,师艳,景港澳,等.基于 Bellman-Ford 算法的穿越沙漠策略研究J.科学技术创新,2020(34):16-17.6 吴华芹.基于 Bellman-Ford 算法的最优交通路径选取建模J.电脑知识与技术,2018,14(9):192-193.7 丁建勋,樊哲延,颜江楠,等.一种基于 SPFA 算法的城市 K 则最短路径获取方法:CN114093188BP.2022-08-19.8 蔡明杰,朱希安,刘德民,等.基于优化 SPFA 算法的矿井突水救援模型J.煤田地质与勘探,2019,47(6):78-83.9 IBRAHIM M,IQBAL M A,ALEEM M,et al.MAHA:Mi-gration-based Adaptive Heuristic Algorithm for Large-scale Network SimulationsJ.Cluster Computing,2019:1-16.10 姚俊峰,洪湘.一种基于 Astar 算法的路径搜索方法:CN113532458AP.2021-10-22.11 张永涛.基于改进 Astar 算法的 AGV 路径规划J.信息与电脑(理论版),2022,34(23):67-70.12 GOLDBERG A V,HARRELSON C.Computing the Shor-test Path:A Search Meets Graph TheoryCProceedings of the Sixteenth Annual ACM-SIAM Symposium on Dis-crete Algorithms.Vancouver:ACM,2005:156-165.13 GEISBERGER R,SANDERS P,SCHULTES D,et al.Con-traction Hierarchies:Faster and Simpler Hierarchical Rou-ting in Road NetworksC Proceedings of the 7th Inter-national Conference on Experimental Algorithms.Berlin:Springer,2008:319-333.14 SONG Q,WANG X.An Efficient Path Computation Ap-proach for Road Networks Based on Hierarchical Commu-nities J.IFAC Proceedings Volumes,2011,44(1):13028-13033.15 BAST H,FUNKE S,SANDERS P,et al.Fast Routing in Road Networks with Transit NodesJ.Science,2007,316(5824):566.16 宋青.大规模网络最短路径的分层优化算法研究D.上海:上海交通大学,2012.17 祝国明.基于 Dijkstra 的多源点最短路径求解算法的设计与分析J.电脑知识与技术,2021,17(16):177-178.18 胡恩祥,汪春雨,潘美芹.基于密度峰值剪枝后的最短路径聚类算法 J.应用科学学报,2020,38(5):792-802.作者简介:侯艳丽博士,河北科技大学副教授。主要研究方向:无线通信技术、无线电测向、电子对抗技术、运动目标检测与跟踪等。(通信作者)马 震河北科技大学硕士研究生。主要研究方向:大规模通信网路径规划算法。