存在未知隐藏障碍物时的最短路径求解方法咨询

你提的“先DFS遍历探明所有红色障碍再BFS算路”的方案不是最优解，核心问题是这个方案会产生大量无意义的探路成本——你根本不需要掌握全图所有障碍物的位置，只要找到一条从起点到终点的可通行最短路径即可，遍历全图探障的移动开销在绝大多数场景下都是完全浪费的。

针对这种存在未知障碍物的栅格最短路径问题，直接根据你的机器人感知能力选成熟的现成方案即可，不需要自己组合DFS+BFS的野路子：

• 如果机器人在移动过程中，可以实时探测到自身周围固定半径内的障碍物（这是移动机器人最常见的感知配置），直接用D* Lite算法，这是未知栅格环境下最短路径规划的入门首选，实现难度低、算路效率高，还能保证路径最优：
  1. 初始阶段只把已知的蓝色障碍物标记到地图上，从终点向起点反向计算初始最短路径，沿着路径向终点移动
  2. 每移动一格，就把当前位置探测到的红色障碍物更新到地图中，如果当前行进的路径没有被新发现的障碍物阻断，就继续沿原路径前进
  3. 如果探测到障碍物阻断了当前路径，不需要从头重算全图路径，只需要复用之前已经计算好的节点代价信息，局部更新受障碍物影响的节点权重，重新规划当前位置到终点的最短路径即可
     这个算法的总移动成本和重规划计算量，都远低于“全探路再算路”的方案，因为它只会在路径被挡的时候做局部调整，从来不会走和终点方向无关的探路路程。如果你的场景是起点固定、障碍物会动态变化，也可以换用LPA*（终身规划A*），二者核心逻辑同源，适配场景略有区别。
• 如果机器人没有实时周围感知，必须移动到对应位置才能观测到障碍物，也不要用DFS做全图遍历，换成边界探索+A*的组合方案即可：
  1. 初始状态只标记起点周围的已探知区域，把已知区域和未知区域的交界点标记为探索边界
  2. 每次选「离当前位置最近、同时离终点直线距离最短」的边界点，用A*在当前已知地图上算到该点的路径，移动过去探索新区域
  3. 每探索完一块新区域就更新地图，检查当前已知地图下是否存在起点到终点的可通行路径，一旦路径连通就直接沿路径走到终点，不需要继续探索剩余区域
     这个方案的探路效率远高于DFS，DFS的遍历顺序没有指向性，很容易绕到远离终点的区域做无用探索，而边界探索是优先往终点方向探路，只要路通了立刻停止探路，总开销低很多。

新手注意：不要在这个场景下硬套RRT之类的采样类规划算法。你面对的是规则栅格上的最短路径问题，基于图搜索的增量式算法可以保证得到严格的最短路径，而RRT是概率完备非最优的，实现更复杂、路径质量还差，完全不匹配你的需求。

本质上你最开始的思路大方向没错，错在把“探路”和“规划”拆成了两个完全独立的先后阶段。未知环境下的路径规划从来不需要等全图信息收集全了再开始算，边走边探、遇到阻断再局部调整，才是这类场景的核心解决思路。

内容的提问来源于stack exchange，提问作者V Adarsh