迷宫求解算法.复杂的迷宫

我发现了几种解决迷宫的算法.那些足够简单的东西只适用于出口在外边界的情况下(墙跟随者,承诺……).

当边界的形状是随机的,区域的成本不等并且退出可能在迷宫内的某个地方时,是否有一些更复杂的算法? (顺便说一下,所有元素都是二次的)

更新:此外,我们不知道apriori迷宫是什么样的,只能看到某个区域.

如果你的意思是“正常的”二维迷宫,就像人们可以在纸上找到的那样,你可以解决它们 using image analysis.但是,如果你以某种方式位于(2D / 3D)迷宫本身并且应该找到出路,你可能应该部署一些 Machine learning技术.如果你不知道你的迷宫究竟是什么样的,那么这是有效的,a.k.a.你只能“看到”它的一部分.

更新:除了最短路径查找器算法系列之外,我还可以涉及所谓的Trémaux算法,该算法旨在能够被迷宫内的人类使用.它类似于一个简单的递归回溯器,可以找到所有迷宫的解决方案.

描述:

As you walk down a passage, draw a line behind you to mark your path. When you hit a dead end turn around and go back the way you came. When you encounter a junction you haven’t visited before, pick a new passage at random. If you’re walking down a new passage and encounter a junction you have visited before, treat it like a dead end and go back the way you came so that you won’t go around in circles or missing passages. If walking down a passage you have visited before (i.e. marked once) and you encounter a junction, take any new passage if one is available, otherwise take an “old” one. Every passage will be either empty (if not visited yet), marked once, or marked twice (if you were forced to backtrack). When you reach the solution, the paths which were marked exactly once will indicate the direct way back to the start. If the maze has no solution, you’ll find yourself back at the start with all passages marked twice.

相关文章
相关标签/搜索