algorithm - 迷宫解决 - 圆形路径问题

Question

通过记录“被访问”的位置（相对于路径前进的方向），在迷宫中的特定区域出现问题，其中被跟踪的路径是圆形的。我使用的算法是一种在迷宫中找到最短路径的递归算法。除了具有圆形路径的区域外，它工作正常。一个解释问题的例子——请看附图。黑线是访问的第一条路径，绿线是第二条路径。黄色标记路径中已被黑线记录为“已访问”的区域。由于这个黄色区域已经被访问过，那么实际上，黄色区域中的绿线是不存在的。因此，找不到示例中迷宫中的最短路径:-(

任何帮助将不胜感激。

在此处输入图像描述

标签： algorithmrecursionmaze

Answer 1

当您到达一个已经访问过的位置时，您必须测试您在第二次（或后续）时间到达它的路径上的距离是否比该位置记录的距离短。如果是，则必须更新其距离并继续。

只要没有“负”距离，这就会起作用。如果有负距离，您将永远停留在循环中，每次距离都会越来越小！

最短路径问题的Wikipedia 页面列出了几种算法、它们的约束和复杂性。对于具有循环但没有负距离的图，这些包括 Bellman-Ford 算法、具有各种数据结构的 Dijkstra 算法。