编程理论:解迷宫 [英] Programming theory: Solve a maze

问题描述

解迷宫的可能方法有哪些?
我有两个想法，但我认为它们不是很优雅.

基本情况:我们有一个矩阵，该矩阵中的元素以表示迷宫的方式排序，一进一出.

我的第一个想法是让一个机器人穿过迷宫，跟随一侧，直到它走出迷宫.我认为这是一个非常缓慢的解决方案.

第二个通过标记为 1 的每个连续项目，检查它可以去的地方(上、右、下、左)选择一种方式并在那里继续其路径.这比第一个还要慢.

当然，如果我让这两个机器人在每个路口多线程处理会快一点，但这也不是最好的方法.

需要更好的解决方案来让机器人穿越迷宫.

编辑
第一:谢谢你的好回答！

我的问题的第二部分是:如果我们有一个多维图怎么办?对此是否有特殊做法，或者 Justin L. 的答案是否也适用于此?
我认为这不是本案的最佳方式.

第三个问题:
这些迷宫求解器算法中的哪一个是最快的?(纯属假设)

解决方案

你可以把你的迷宫想象成一棵树.

<前>一种//乙丙//德福格/ 海杰/LM/** 哦(这可能代表)开始+ +---+---+|A C G |+---+ + + +|D B |F |J |+---+---+ +---+---+|L H E I |+---+ +---+---+|莫|+ +---+结束(忽略树上的左右排序)

其中每个节点都是路径的交汇点.D、I、J、L、O是死胡同，**是目标.当然，在您的实际树中，每个节点都有可能拥有多达三个的子节点.

您现在的目标只是找到要遍历的节点以找到终点.任何 ol' 树搜索算法都可以.

查看树，只需从树最深处的 ** 处跟踪"即可很容易地看到正确的解决方案:

A B E H M **

请注意，当您的迷宫中有循环"时，这种方法会变得稍微更复杂(即，如果可能，无需回溯，您重新输入您已经遍历过的段落通过).查看评论以获得一个不错的解决方案.

现在，让我们看看您提到的第一个应用到这棵树的解决方案.

您的第一个解决方案基本上是深度优先搜索，这真的没那么糟糕.这实际上是一个非常好的递归搜索.基本上，它说，总是先走最右边的路.如果那里什么都没有，就回溯到你可以直行或向左走的第一个地方，然后重复.

深度优先搜索将按以下顺序搜索上述树:

A B D (回溯) E H L (回溯) M ** (回溯) O (回溯三次) I(回溯三次) C F (回溯) G J

请注意，您可以在找到**后立即停止.

但是，当您实际编写深度优先搜索时，使用递归编程会使一切变得更加容易.甚至迭代方法也可以工作，而且您永远不必明确编程如何回溯.查看链接文章了解实现.

搜索树的另一种方法是广度优先 解决方案，按深度搜索树.它会按以下顺序搜索上面的树:

A (下一级) B C (下一级) D E F G (下一级)H I J(下一级) L M(下一级)** O

请注意，由于迷宫的性质，广度优先检查的平均节点数量要高得多.广度优先很容易实现，有一个要搜索的路径队列，每次迭代都会从队列中弹出一条路径，通过获取一步后可以变成的所有路径并放置这些新路径来分解"它在队列的末尾.没有明确的下一级"命令来编写代码，这些命令只是为了帮助理解.

事实上，有一个完整的广泛的搜索树的方法列表.我刚刚提到了两个最简单、最直接的方式.

如果你的迷宫非常非常长和深，有循环和疯狂，并且很复杂，我建议使用 A* 算法，这是行业标准的寻路算法，它将广度优先搜索与启发式算法相结合……有点像智能广度优先搜索".

它基本上是这样工作的:

1. 在队列中放置一条路径(您只走一步就可以直接进入迷宫的路径).路径的权重"由其当前长度 + 到终点的直线距离(可以通过数学计算)给出
2. 从队列中弹出权重最低的路径.
3. 将路径分解"为一步后可能到达的每条路径.(即，如果您的路径是右左左右，那么您的爆炸路径是 R L L R R 和 R L L R L，不包括穿过墙壁的非法路径)
4. 如果这些路径之一有目标，那么胜利！否则:
5. 计算爆炸路径的权重，并将它们全部放回队列(不包括原始路径)
6. 按权重排序队列，最低的在前.然后从第 2 步开始重复

这就是 A*，我特别强调了它，因为它或多或少是所有寻路应用的行业标准寻路算法，包括从边缘移动在避开越野路径或山脉等的同时，将地图切换到另一个地图.它运行良好，因为它使用了最短距离启发式，这赋予了它智能".A* 用途广泛，因为在遇到任何问题时，如果您有可用的最短距离启发式方法(我们的方法很简单——直线)，您就可以应用它.

但是值得注意的是，A* 不是您唯一的选择.

事实上，维基百科类别的树遍历算法仅列出了 97 个！(最好的仍将在 此页面 之前链接)

对不起，长度=P(我倾向于漫无目的)

What are the possible ways to solve a maze?
Ive got two ideas, but I think they are not very elegant.

Base situation: We have a matrix, and the elements in this matrix are ordered in a way that it represents a maze, with one way in, and one out.

My first idea was to send a robot through the maze, following one side, until it's out of the maze. I think this is a very slow solution.

The second one passes through every successive item marked with 1, checks where it can go (up, right, down, left) chooses one way and it continues its path there. This is even slower than the first one.

Of course it's a bit faster if I make the two bots multi-threaded at every junction, but thats also not the best way.

There needs to be better solutions to send a bot through a maze.

EDIT
First: Thanks for the nice answers!

The second part of my question is: What to do in the case if we have a multi-dimensional graph? Are there special practices for that, or is the answer of Justin L. usable for that too?
I think it's not the best way for this case.

The third question:
Which of these maze solver algorithms is/are the fastest? (Purely hypothetically)

解决方案

You can think of your maze as a tree.

     A
    / 
   /   
  B     C
 /    / 
D   E F   G
   /      
  H   I     J
 / 
L   M
   / 
  **  O

(which could possibly represent)

        START
        +   +---+---+
        | A   C   G |
    +---+   +   +   +
    | D   B | F | J |
+---+---+   +---+---+
| L   H   E   I |
+---+   +---+---+
    | M   O |
    +   +---+
    FINISH

(ignoring left-right ordering on the tree)

Where each node is a junction of paths. D, I, J, L and O are dead ends, and ** is the goal. Of course, in your actual tree, each node has a possibility of having as many as three children.

Your goal is now simply finding what nodes to traverse to to find the finish. Any ol' tree search algorithm will do.

Looking at the tree, it's pretty easy to see your correct solution by simply "tracing up" from the ** at the deepest part of the tree:

A B E H M **

Note that this approach becomes only slightly more complicated when you have "loops" in your maze (i.e., when it is possible, without backtracing, you re-enter a passage you've already traversed through). Check the comments for one nice solution.

Now, let's look at your first solution you mentioned, applied to this tree.

Your first solution is basically a Depth-First Search, which really isn't that bad. It's actually a pretty good recursive search. Basically, it says, "Always take the rightmost approach first. If nothing is there, backtrack until the first place you can go straight or left, and then repeat.

A depth-first search will search the above tree in this order:

A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J

Note that you can stop as soon as you find the **.

However, when you actually code a depth-first search, using recursive programming makes makes everything much easier. Even iterative methods work too, and you never have to explicitly program how to backtrack. Check out the linked article for implementations.

Another way of searching a tree is the Breadth-First solution, which searches through trees by depth. It'd search through the above tree in this order:

A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O

Note that, due to the nature of a maze, breadth-first has a much higher average amount of nodes it checks. Breadth-first is easily implementing by having a queue of paths to search, and each iteration popping a path out of a queue, "exploding it" by getting all of the paths that it can turn into after one step, and putting those new paths at the end of the queue. There are no explicit "next level" commands to code, and those were just there to aid in understanding.

In fact, there is a whole expansive list of ways to search a tree. I've just mentioned the two simplest, most straightforward way.

If your maze is very, very long and deep, and has loops and crazies, and is complicated, I suggest the A* algorithm, which is the industry standard pathfinding algorithm which combines a Breadth-First search with heuristics...sort of like an "intelligent breadth-first search".

It basically works like this:

1. Put one path in a queue (the path where you only walk one step straight into the maze). A path has a "weight" given by its current length + its straight-line distance from the end (which can be calculated mathematically)
2. Pop the path with the lowest weight from the queue.
3. "Explode" the path into every path that it could be after one step. (i.e., if your path is Right Left Left Right, then your exploded paths are R L L R R and R L L R L, not including illegal ones that go through walls)
4. If one of these paths has the goal, then Victory! Otherwise:
5. Calculate the weights of the exploded paths, and put all of them back into the queue (not including the original path)
6. Sort the queue by weight, lowest first. Then repeat from Step #2

And that's A*, which I present specially highlighted because it is more or less the industry standard pathfinding algorithm for all applications of pathfinding, including moving from one edge of the map to another while avoiding off-road paths or mountains, etc. It works so well because it uses a shortest possible distance heuristic, which gives it its "intelligence". A* is so versatile because, given any problem, if you have a shortest possible distance heuristic available (ours is easy -- the straight line), you can apply it.

BUT it is of great value to note that A* is not your only option.

In fact, the wikipedia category of tree traversal algorithms lists 97 alone! (the best will still be on this page linked earlier)

Sorry for the length =P (I tend to ramble)

这篇关于编程理论:解迷宫的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！