-
题名过必经点集且具有额外硬约束的最短路径算法
被引量:2
- 1
-
-
作者
郭展羽
张志明
贺兰山
郑家齐
赵师兵
康琦
-
机构
同济大学电子与信息工程学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2022年第18期297-303,共7页
-
基金
国家自然科学基金(51775385)
上海市教育委员会科研创新计划(202101070007E00098)
+1 种基金
教育部高等教育司2019年度第二批产学合作协同育人项目(201902016059)
同济大学2020年双一流引导专项本科生学科竞赛专项立项项目(4250145303)。
-
文摘
求解过必经点集的最短路径问题已有多种算法,但其应用到在具有额外硬约束限定条件的场景时存在不足。针对此类问题,提出一种基于深度优先搜索发展的随机搜索算法,由使用者依据现场情况给出数学描述,建模抽象为无向带权图表示;依据路径规划要求定义相关变量,包括路径规划的起点、终点、必经点集以及额外硬约束条件,图信息和节点信息以邻接矩阵的形式保存;搜索过程中对路径的可行性加入额外硬约束条件进行实时判定,最终获得最短路径解。实验仿真和实测结果表明,该算法能有效规避额外硬约束条件下的中间路径,生成合理的最短路径,改善相关问题的可求解性。
-
关键词
深度优先搜索
随机搜索
最短路径
必经点集
额外硬约束
-
Keywords
depth-first search
random search
shortest path
passing necessary nodes
extra hard constraints
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
TP312
[自动化与计算机技术—计算机软件与理论]
-