Abstract: There have been many algorithms for solving the shortest path problems through necessary nodes set, but most of them are insufficient when applied to the circumstances with extra hard constraints. To solve this problem, this paper puts forward a random search algorithm based on depth first search mechanism. The mathematical models are provided by users according to actual situation, and they are abstracted as undirected weighted graphs. Some related variables such as the beginning node, the end node, necessary nodes and extra hard constraints are defined by path planning requirements, and they are saved as adjacency matrix. In the searching process, the feasibility of the path is determined in real time to meet the requirements of extra hard constraints. Finally, the optimal shortest path solution is obtained. Simulation and actual results show that the algorithm effectively avoids the influence of intermediate path under extra hard constraints and generate a shortest path, which means that this algorithm can greatly improve problem solvability.

Key words: depth-first search, random search, shortest path, passing necessary nodes, extra hard constraints

摘要： 求解过必经点集的最短路径问题已有多种算法，但其应用到在具有额外硬约束限定条件的场景时存在不足。针对此类问题，提出一种基于深度优先搜索发展的随机搜索算法，由使用者依据现场情况给出数学描述，建模抽象为无向带权图表示；依据路径规划要求定义相关变量，包括路径规划的起点、终点、必经点集以及额外硬约束条件，图信息和节点信息以邻接矩阵的形式保存；搜索过程中对路径的可行性加入额外硬约束条件进行实时判定，最终获得最短路径解。实验仿真和实测结果表明，该算法能有效规避额外硬约束条件下的中间路径，生成合理的最短路径，改善相关问题的可求解性。

关键词: 深度优先搜索, 随机搜索, 最短路径, 必经点集, 额外硬约束