有哪些解决迷宫问题的可能方法？
我有两个想法，但我认为它们不太优雅。
基本情况：我们有一个矩阵，这个矩阵中的元素按一定方式排序，代表着一个迷宫，有一个入口和一个出口。
我的第一个想法是让机器人穿过迷宫，沿着一个方向走，直到迷宫外。我认为这是一个非常缓慢的解决方法。
第二种方式是经过每一个标有1的连续项，检查它可以往哪里走（上、右、下、左），选择一个方向并继续前进。这比第一种方式还要更慢。
当然，在每个交叉口上将两个机器人多线程化会快一些，但那也不是最好的方式。
需要有更好的方法来让机器人通过迷宫。
编辑
首先：感谢大家的好回答！
我的问题的第二部分是：如果我们有一个多维图形怎么办？有特殊的做法吗？或者Justin L.的答案是否适用于这种情况？
我认为这不是这种情况下的最佳方式。
第三个问题：
这些迷宫解决算法中哪个/哪些是最快的？（纯属假设）
你可以将迷宫看作一棵树。
A
/ \
/ \
B C
/ \ / \
D E F G
/ \ \
H I J
/ \
L M
/ \
** O
（可能代表）
START
+ +---+---+
| A C G |
+---+ + + +
| D B | F | J |
+---+---+ +---+---+
| L H E I |
+---+ +---+---+
| M O |
+ +---+
FINISH
（忽略树上的左右顺序）
每个节点都是路径的交汇处。D、I、J、L和O是死路，**是目标。 当然，在你实际的树中，每个节点都有可能有多达三个孩子。
现在你的目标只是找到要遍历的节点以找到终点。任何一种树搜索算法都可以。
从树的最深处的**开始，“向上跟踪”很容易看出正确的解决方案：
A B E H M **
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*并不是您唯一的选择。
事实上，树遍历算法的维基百科类别单独就列出了97种！（最好的仍然在之前链接的此页面上）抱歉长度有点长=P（我喜欢唠叨）存在许多迷宫解决算法：
http://en.wikipedia.org/wiki/Maze_solving_algorithm
http://www.astrolog.org/labyrnth/algrithm.htm#solve
对于机器人而言，特莫算法看起来很有前途。
一个有趣的方法，至少我觉得很有趣，是使用元胞自动机。简单来说，被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
在我的大学计算机科学课程中，我遇到了类似的问题。我们想出的解决方案是按照左手边的墙壁走（右手边也同样有效）。以下是一些伪代码：
While Not At End
If Square To Left is open,
Rotate Left
Go Forward
Else
Rotate Right
End If
Wend
基本上就是这样。复杂的部分是要跟踪你面朝的方向，并根据此方向确定左侧的网格位置。对于我放在它面前的任何测试用例都有效。有趣的是，教授的解决方案大致如下：
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
对于大多数简单的迷宫而言，这种方法都能很好地运作，但是对于下面这个迷宫就会失败：
SXXXXXXXXXXXXX
X X
X X
X X
XXX X
X X X
X XXXXXXXXXXX XXXE
X X
XXXXXXXXXXXXXXXXXXX
以S和E为起点和终点。
对于任何不沿着墙壁前进的情况，你最终需要记录你走过的地方，以便在你走入死胡同时可以回溯，同时也避免陷入循环。如果你沿着墙壁前进，就不需要跟踪你走过的地方。虽然你可能不会找到迷宫中最优路径，但你总能通过它。
#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
这只是一个想法。为什么不像蒙特卡罗方法一样，投入一些机器人？
我们将第一代机器人称为gen0。
我们只保留在以下情况下具有一些连续道路的gen0机器人：
我们在新的随机点上运行新的gen1机器人，然后尝试连接gen1机器人的道路与gen0机器人的道路，看是否能够获得从起点到终点的连续道路。
因此，对于genn，我们尝试与gen0、gen1、…、genn-1的机器人进行连接。
当然，一代机器人只持续有限的时间。
我不知道算法的复杂性是否对小数据集实用。
一些好的网站供参考：
http://citeseerx.ist.psu.edu/
http://arxiv.org/
这就是所有 stack-overflow 上的问题的通用答案 ;)
使用 vi 吧！
http://www.texteditors.org/cgi-bin/wiki.pl?Vi-Maze
看到文本编辑器解决ASCII迷宫真是太有趣了，我相信Emacs的人也有类似的东西。