基于节点压缩的寻径优化算法  

SEARCH PATH OPTIMIZATION ALGORITHM BASED ON NODE COMPRESSION

作　　者：廖志芳[1] 陈亮名 彭志文[1] 李严冰 

机构地区：[1]中南大学软件学院,湖南长沙410075

出　　处：《计算机应用与软件》2017年第11期241-246,共6页Computer Applications and Software

基　　金：国家自然科学基金青年项目(61301136)

摘　　要：最短路径问题是一个经典问题,而目前的研究大多是针对给定起点和终点,选择从起点到终点的最短路径,且取得了不少成果。而对于限定时间的最短路径问题的研究成果相对较少,这类问题在现实生活中却随处可见。针对这一问题提出几种限定时间的寻径优化算法,从对回溯法的改进到不同的节点压缩的方法,给出改进的回溯法以及三种基于节点压缩的寻径算法。算法实现在限定的时间内从起点出发经过给定的节点集合再到达终点的路径选择,并针对不同复杂度的网络图有相应合适的算法可以选择,从而有效地解决这类问题。The shortest path problem is a classic problem,while the current study is mostly for a given starting point and end point, choose the shortest path from the starting point to the end, and has achieved a lot of results. For the limit time of the research achievements of the shortest path problem is relatively less, this kind of problem is ubiquitous in real life. In this paper, we propose several optimization algorithms for time-dependent optimization of this problem, from the improvement of backtracking method to the method of different node compression, an improved backtracking method and three algorithms based on node compression are proposed. Implemented in a limited amount of time, starting from the starting point after a given node set to reach the destination path selection, and according to different complexity of network diagram, can choose the appropriate algorithm to deal with, which can effectively solve the problem.

关 键 词：最短路径 限定时间 节点压缩 寻径 

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