| 过必经点集且具有额外硬约束的最短路径算法 |
| |
| 引用本文： | 郭展羽,张志明,贺兰山,郑家齐,赵师兵,康琦. 过必经点集且具有额外硬约束的最短路径算法[J]. 计算机工程与应用, 2022, 58(18): 297-303. DOI: 10.3778/j.issn.1002-8331.2102-0338 |
| |
| 作者姓名： | 郭展羽 张志明 贺兰山 郑家齐 赵师兵 康琦 |
| |
| 作者单位： | 同济大学 电子与信息工程学院，上海 200092 |
| |
| 基金项目： | 国家自然科学基金（51775385）；;上海市教育委员会科研创新计划（202101070007E00098）；;教育部高等教育司2019年度第二批产学合作协同育人项目（201902016059）； |
| |
| 摘 要： | 求解过必经点集的最短路径问题已有多种算法，但其应用到在具有额外硬约束限定条件的场景时存在不足。针对此类问题，提出一种基于深度优先搜索发展的随机搜索算法，由使用者依据现场情况给出数学描述，建模抽象为无向带权图表示；依据路径规划要求定义相关变量，包括路径规划的起点、终点、必经点集以及额外硬约束条件，图信息和节点信息以邻接矩阵的形式保存；搜索过程中对路径的可行性加入额外硬约束条件进行实时判定，最终获得最短路径解。实验仿真和实测结果表明，该算法能有效规避额外硬约束条件下的中间路径，生成合理的最短路径，改善相关问题的可求解性。
|
| 关 键 词： | 深度优先搜索 随机搜索 最短路径 必经点集 额外硬约束 |
Shortest Path Algorithm Through Necessary Nodes with Extra Hard Constraints |
| |
| GUO Zhanyu,ZHANG Zhiming,HE Lanshan,ZHENG Jiaqi,ZHAO Shibing,KANG Qi. Shortest Path Algorithm Through Necessary Nodes with Extra Hard Constraints[J]. Computer Engineering and Applications, 2022, 58(18): 297-303. DOI: 10.3778/j.issn.1002-8331.2102-0338 |
| |
| Authors: | GUO Zhanyu ZHANG Zhiming HE Lanshan ZHENG Jiaqi ZHAO Shibing KANG Qi |
| |
| Affiliation: | College of Electronics and Information Engineering, Tongji University, Shanghai 200092, China |
| |
| 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. |
| |
| Keywords: | depth-first search random search shortest path passing necessary nodes extra hard constraints |
|
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
