有哪些可能的方法来解决迷宫？
我有两个想法，但我认为它们不是很优雅。
基本情况：我们有一个矩阵，这个矩阵中的元素按照它代表一个迷宫的方式排序，一个进一个出。
我的第一个想法是让机器人沿着迷宫的一侧穿过迷宫，直到它走出迷宫。我认为这是一个非常缓慢的解决方案。
第二个通过标记为 1 的每个连续项目，检查它可以去的地方（上、右、下、左）选择一种方式，并在那里继续它的路径。这甚至比第一个慢。
当然，如果我让两个机器人在每个连接处都进行多线程处理会快一点，但这也不是最好的方法。
需要有更好的解决方案来让机器人通过迷宫。
编辑
第一：谢谢你的好答案！
我的问题的第二部分是：如果我们有一个多维图，该怎么办？是否有特殊的做法，或者贾斯汀 L. 的答案是否也适用于此？
我认为这不是这个案子的最佳方式。
第三个问题：
这些迷宫求解算法中哪个/是最快的？（纯属假设）
你可以把你的迷宫想象成一棵树。
一个
/ \
/ \
公元前
/ \ / \
DEFG
/ \ \
HIJ
/ \
LM
/ \
** 哦
（可能代表）
开始
+ +---+---+
| ACG |
+---+ + + +
| 数据库 | F | Ĵ |
+---+---+ +---+---+
| LHEI |
+---+ +---+---+
| 莫|
+ +---+
结束
（忽略树上的左右排序）
其中每个节点都是路径的交汇点。D、I、J、L、O是死胡同，**是目标。当然，在您的实际树中，每个节点都有可能拥有多达三个子节点。
您现在的目标只是找到要遍历的节点以找到终点。任何老树搜索算法都可以。
查看树，只需从树最深处的 **“向上跟踪”，就很容易看到正确的解决方案：
A B E H M **
请注意，当您的迷宫中有“循环”时，这种方法只会稍微复杂一些（即，如果有可能，无需回溯，您就可以重新进入已经穿过的通道）。检查评论以获得一个不错的解决方案。
现在，让我们看看您提到的第一个解决方案，应用于这棵树。
您的第一个解决方案基本上是Depth-First Search，这确实还不错。这实际上是一个非常好的递归搜索。基本上，它说，“总是先走最右边的路。如果什么都没有，回溯到第一个可以直走或左走的地方，然后重复。
深度优先搜索将按以下顺序搜索上述树：
A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J
请注意，您可以在找到 ** 后立即停止。
但是，当您实际编写深度优先搜索代码时，使用递归编程会使一切变得更容易。甚至迭代方法也可以工作，您不必显式地编程如何回溯。查看链接的文章以了解实现。
另一种搜索树的方法是广度优先解决方案，它通过深度搜索树。它会按以下顺序搜索上面的树：
A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O
请注意，由于迷宫的性质，广度优先检查的平均节点数量要高得多。广度优先很容易实现，方法是有一个要搜索的路径队列，每次迭代都会从队列中弹出一条路径，通过获取一步后可以变成的所有路径来“爆炸”它，然后放置这些新路径在队列的末尾。代码没有明确的“下一级”命令，这些命令只是为了帮助理解。
事实上，搜索树的方法有很多种。我刚刚提到了两种最简单、最直接的方法。
如果你的迷宫非常非常长而且很深，并且有循环和疯狂，而且很复杂，我建议使用A*算法，这是行业标准的寻路算法，它结合了广度优先搜索和启发式算法......有点像“智能广度优先搜索”。
它基本上是这样工作的：
这就是A*，我特别强调了它，因为它或多或少是适用于所有寻路应用的行业标准寻路算法，包括从地图的一个边缘移动到另一个边缘，同时避开越野路径或山脉等。它有效很好，因为它使用了最短距离启发式算法，这赋予了它“智能”。A* 是如此多才多艺，因为如果有任何问题，如果你有一个可用的最短距离启发式（我们的很简单——直线），你可以应用它。
但值得注意的是，A*不是您唯一的选择。
事实上，树遍历算法的维基百科分类仅列出了 97 个！（最好的仍将在之前链接的此页面上）
抱歉长度=P（我倾向于漫无目的）
存在许多解决迷宫的算法：
http://en.wikipedia.org/wiki/Maze_solving_algorithm
http://www.astrolog.org/labyrnth/algrithm.htm#solve
对于机器人来说，Tremaux 的算法看起来很有前途。
一个有趣的方法，至少我觉得它很有趣，是使用元胞自动机。简而言之，一个由 3 个“壁”单元包围的“空间”单元变成了一个“壁”单元。最后，唯一剩下的空间单元是通往出口的路线。
如果您查看 Justin 在他的答案中输入的树，那么您可以看到叶节点有 3 个墙。修剪树直到你有路径。
这是我最喜欢的算法之一......
1) Move forward
2) Are you at a wall?
2a) If yes, turn left
3) Are you at the finish?
3a) If no, go to 1
3b) If yes, solved
使用广度优先搜索、深度优先搜索或 Dijkstras 算法从矩阵中构建图形怎么样？
I had a similar problem in one of my University Comp. Sci. courses. The solution we came up with was to follow the left hand wall (right hand wall will work just as well). Here is some pseudocode
While Not At End
If Square To Left is open,
Rotate Left
Go Forward
Else
Rotate Right
End If
Wend
That's basically it. The complex part is keeping track of which direction your facing, and figuring out which grid position is on your left based on this direction. It worked for any test case I put up against it. Interesting enough the Professors solution was something along the lines of:
While Not At End
If Can Go North
Go North
ElseIf Can Go East
Go East
ElseIf Can Go South
Go South
ElseIf Can Go West
Go West
EndIf
Wend
Which will work well for most simple mazes, but fails on the a maze that looks like the following:
SXXXXXXXXXXXXX
X X
X X
X X
XXX X
X X X
X XXXXXXXXXXX XXXE
X X
XXXXXXXXXXXXXXXXXXX
With S and E being the start and end.
With anything that doesn't follow the wall, you end up having to keep a list of the places you have been, so that you can backtrack if necessary, when you fall into a dead end, and so that you don't get caught in a loop. If you follow the wall, there's no need to keep track of where you've been. Although you won't find the most optimal path through the maze, you will always get through it.
这是在 C++ 中模拟迷宫的一个非常简单的表示形式 :)
#ifndef vAlgorithms_Interview_graph_maze_better_h
#define vAlgorithms_Interview_graph_maze_better_h
static const int kMaxRows = 100;
static const int kMaxColumns = 100;
class MazeSolver
{
private:
char m_matrix[kMaxRows][kMaxColumns]; //matrix representation of graph
int rows, cols; //actual rows and columns
bool m_exit_found;
int m_exit_row, m_exit_col;
int m_entrance_row, m_entrance_col;
struct square //abstraction for data stored in every verex
{
pair<int, int> m_coord; //x and y co-ordinates of the matrix
square* m_parent; //to trace the path backwards
square() : m_parent(0) {}
};
queue<square*> Q;
public:
MazeSolver(const char* filename)
: m_exit_found(false)
, m_exit_row(0)
, m_exit_col(0)
, m_entrance_row(0)
, m_entrance_col(0)
{
ifstream file;
file.open(filename);
if(!file)
{
cout << "could not open the file" << endl << flush;
// in real world, put this in second phase constructor
}
init_matrix(file);
}
~MazeSolver()
{
}
void solve_maze()
{
//we will basically use BFS: keep pushing squares on q, visit all 4 neighbors and see
//which way can we proceed depending on obstacle(wall)
square* s = new square();
s->m_coord = make_pair(m_entrance_row, m_entrance_col);
Q.push(s);
while(!m_exit_found && !Q.empty())
{
s = Q.front();
Q.pop();
int x = s->m_coord.first;
int y = s->m_coord.second;
//check if this square is an exit cell
if(x == m_exit_row && y == m_exit_col)
{
m_matrix[x][y] = '>'; // end of the path
m_exit_found = true;
//todo: try breaking? no= queue wont empty
}
else
{
//try walking all 4 neighbors and select best path
//NOTE: Since we check all 4 neighbors simultaneously,
// the path will be the shortest path
walk_path(x-1, y, s);
walk_path(x+1, y, s);
walk_path(x, y-1, s);
walk_path(x, y+1, s);
}
} /* end while */
clear_maze(); //unset all previously marked visited shit
//put the traversed path in maze for printing
while(s->m_parent)
{
m_matrix[s->m_coord.first][s->m_coord.second] = '-';
s = s->m_parent;
} /* end while */
}
void print()
{
for(int i=0; i<rows; i++)
{
for(int j=0; j<cols; j++)
cout << m_matrix[i][j];
cout << endl << flush;
}
}
private:
void init_matrix(ifstream& file)
{
//read the contents line-wise
string line;
int row=0;
while(!file.eof())
{
std::getline(file, line);
for(int i=0; i<line.size(); i++)
{
m_matrix[row][i] = line[i];
}
row++;
if(line.size() > 0)
{
cols = line.size();
}
} /* end while */
rows = row - 1;
find_exit_and_entry();
m_exit_found = false;
}
//find and mark ramp and exit points
void find_exit_and_entry()
{
for(int i=0; i<rows; i++)
{
if(m_matrix[i][cols-1] == ' ')
{
m_exit_row = i;
m_exit_col = cols - 1;
}
if(m_matrix[i][0] == ' ')
{
m_entrance_row = i;
m_entrance_col = 0;
}
} /* end for */
//mark entry and exit for testing
m_matrix[m_entrance_row][m_entrance_col] = 's';
m_matrix[m_exit_row][m_exit_col] = 'e';
}
void clear_maze()
{
for(int x=0; x<rows; x++)
for(int y=0; y<cols; y++)
if(m_matrix[x][y] == '-')
m_matrix[x][y] = ' ';
}
// Take a square, see if it's the exit. If not,
// push it onto the queue so its (possible) pathways
// are checked.
void walk_path(int x, int y, square* parent)
{
if(m_exit_found) return;
if(x==m_exit_row && y==m_exit_col)
{
m_matrix[x][y] = '>';
m_exit_found = true;
}
else
{
if(can_walk_at(x, y))
{
//tag this cell as visited
m_matrix[x][y] = '-';
cout << "can walk = " << x << ", " << y << endl << flush;
//add to queue
square* s = new square();
s->m_parent = parent;
s->m_coord = make_pair(x, y);
Q.push(s);
}
}
}
bool can_walk_at(int x, int y)
{
bool oob = is_out_of_bounds(x, y);
bool visited = m_matrix[x][y] == '-';
bool walled = m_matrix[x][y] == '#';
return ( !oob && !visited && !walled);
}
bool is_out_of_bounds(int x, int y)
{
if(x<0 || x > rows || y<0 || y>cols)
return true;
return false;
}
};
void run_test_graph_maze_better()
{
MazeSolver m("/Users/vshakya/Dropbox/private/graph/maze.txt");
m.print();
m.solve_maze();
m.print();
}
#endif
如果机器人可以跟踪它的位置，那么它就知道它以前是否去过某个位置，那么深度优先搜索就是显而易见的算法。您可以通过对抗性论证表明，不可能获得比深度优先搜索更好的最坏情况性能。
如果您有机器人无法实现的技术，那么广度优先搜索对于许多迷宫的性能可能会更好，Dijkstra 的算法在图中寻找最短路径也是如此。
只是一个想法。为什么不以蒙特卡洛的方式将一些机器人扔在那里。我们将第一代机器人称为 gen0。我们只保留来自 gen0 的机器人以这种方式有一些连续的道路：
-从开始到某个点
或 -从某个点到结束
我们在新的随机点上运行新的 gen1 机器人，然后我们尝试将 gen1 机器人的道路与 gen0 机器人的道路连接起来，看看我们是否得到一条从头到尾的连续道路。
因此，对于 genn，我们尝试连接 gen0、gen1、...、genn-1 的机器人。
当然，一代人只能持续有限的时间。
我不知道算法的复杂性是否会被证明对小数据集是实用的。
该算法还假设我们知道起点和终点。
一些很好的创意网站：
http ://citeseerx.ist.psu.edu/
http://arxiv.org/
有许多算法和许多不同的设置来指定哪种算法是最好的。这只是关于一个有趣设置的一个想法：
假设您具有以下属性...
然后你可以设计一个人工智能...
与有关堆栈溢出的所有问题的答案相同；）
使用 vi！
http://www.texteditors.org/cgi-bin/wiki.pl?Vi-Maze
看到一个文本编辑器解决一个 ascii 迷宫真的很有趣，我相信 emacs 的人也有一个等价的..
这个 azkaban 算法也可能对您有所帮助， http://journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html
解决迷宫的最佳方法是使用连接算法，例如 union-find，它是假设路径压缩完成的准线性时间算法。
Union-Find 是一种数据结构，它告诉您集合中的两个元素是否是可传递连接的。
为了使用并集数据结构来解决迷宫，首先使用邻居连接数据来构建并集数据结构。然后联合查找被压缩。为了确定迷宫是否可解，比较入口值和出口值。如果它们具有相同的值，则它们是连接的并且迷宫是可解的。最后，为了找到解决方案，您从入口开始并检查与其每个邻居关联的根。一旦您找到与当前单元具有相同根的先前未访问的邻居，您就访问该单元并重复该过程。
这种方法的主要缺点是，如果有多个路径，它不会告诉您穿过迷宫的最短路径。