编程理论：解决迷宫

什么是解决迷宫的可能方法？
我有两个想法，但我认为他们不是很优雅。

基本情况：我们有一个matrix，这个matrix中的元素被sorting，它代表一个迷宫，一个方向，一个方向。

我的第一个想法是把一个机器人通过迷宫，一边，直到它走出了迷宫。我认为这是一个非常缓慢的解决scheme。

第二个通过每一个标有1的项目，检查它可以去的地方（向上，向右，向下，向左）select一种方式，并在那里继续它的path。这比第一个还要慢。

当然，如果我在每个交叉点上使两个机器人都是multithreading的，那么速度会更快一些，但那也不是最好的方法。

需要有更好的解决scheme来发送一个bot在迷宫中。

编辑
首先：感谢您的好答案！

我的问题的第二部分是：如果我们有一个多维图，该怎么办？有没有特别的做法呢，还是Justin L.的答案呢？
我认为这不是最好的办法。

第三个问题：
哪一种迷宫求解algorithm是最快的？（纯粹假设）

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

     一个
     / \
    / \
  公元前
  / \ / \
 DEFG
    / \ \
   HIJ
  / \
 LM
    / \
   ** O

 （可能代表）

        开始
         + + --- + --- +
         |  ACG |
     + --- + + + +
     |  DB |  F |  J |
 + --- + --- + + --- + --- +
 |  LHEI |
 + --- + + --- + --- +
     |  MO |
     + + --- +
    完

 （忽略树上的左右sorting）

每个节点是path的交汇点。 D，I，J，L和O是死路一条，**是目标。当然，在你的实际树中，每个节点都有可能有多达三个孩子。

现在你的目标是简单地find要遍历的节点来find结束。任何醇树searchalgorithm会做。

看着这棵树，通过简单地从树的最深处“**”追踪你的正确答案是相当容易的：

ABEHM **

请注意，当你在迷宫中有“循环”的时候，这种方法会变得稍微复杂一点（也就是说，如果有可能，没有回溯，你重新进入了已经穿过的通道）。检查一个很好的解决scheme的意见。

现在，让我们看看你提到的第一个解决scheme，应用到这棵树上。

你的第一个解决scheme基本上是一个深度优先search ，其实并没有那么糟糕。这实际上是一个很好的recursionsearch。基本上，它说：“总是先采取最右边的方法，如果没有什么东西，回溯到第一个地方，你可以直走或离开，然后重复。

深度优先search将按以下顺序search上述树：

 ABD (backtrack) EHL (backtrack) M ** (backtrack) O (backtrack thrice) I (backtrack thrice) CF (backtrack) GJ

请注意，只要find**，就可以停下来。

但是，当您实际编写深度优先search时，使用recursion编程可以使一切变得更加容易。即使是迭代方法也是如此，而且你不必明确地编程如何回溯。查看链接的文章的实现。

search树的另一种方法是广度优先解决scheme，它通过深度search树。它会按照以下顺序search上面的树：

 A (next level) BC (next level) DEFG (next level) HIJ (next level) LM (next level) ** O

请注意，由于迷宫的性质，宽度优先的节点检查的平均节点数量要高得多。宽度优先通过具有searchpath的队列来容易地实现，并且每次迭代从队列中popup一条path，通过获得它在一步之后可以转入的所有path，并将这些新path“爆炸”在队列的末尾。没有明确的“下一级”命令来编码，而这些只是帮助理解。

实际上， search树的方法有很多。我刚刚提到了两个最简单，最直接的方法。

如果你的迷宫非常，很长，很深，有循环和疯狂，并且是复杂的，我build议A *algorithm，这是行业标准的寻路algorithm，它结合了广度优先search与启发式…有点像一个“智能广度优先search”。

它基本上是这样工作的：

把一条path放在一个队列中（你只走一步直入迷宫的path）。 path有一个由当前长度给出的“权重”+从末端到直线的距离（可以通过math计算）
从队列中popup权重最低的path。
将path“爆炸”到一步之后的每条path。（也就是说，如果你的path是右左左，那么你的爆炸path是RLLRR和RLLRL，不包括穿过墙壁的非法path）
如果其中一条路有目标，那胜利！除此以外：
计算爆炸path的权重，并将其全部放回到队列中（不包括原始path）
按重量对队列进行sorting，先从最低sorting。然后从步骤＃2重复

这就是我特别强调的A * ，因为它或多或less是所有寻路应用程序的行业标准寻路algorithm，包括从地图的一边移动到另一边，同时避开越野path或山脉等。所以很好，因为它使用了最短的距离启发式 ，这使得它的“智能”。 A *是如此多才多艺，因为如果有任何问题，如果你有一个尽可能短的启发式可用（我们很容易 – 直线），你可以应用它。

但是，注意到A * 不是你唯一的select。

事实上，树遍历algorithm的维基百科类别列出了97！（最好的还是会在这个页面上链接一下）

对不起，长度= P（我倾向于漫步）

存在许多迷宫求解algorithm：

http://en.wikipedia.org/wiki/Maze_solving_algorithm

http://www.astrolog.org/labyrnth/algrithm.htm#solve

对于机器人， Tremaux的algorithm看起来很有前途。

一个有趣的方法，至less我觉得很有趣，就是使用元胞自动机。简言之，被3个“壁”单元包围的“空间”单元变成了“墙”单元。最后剩下的唯一空间单元就是通往出口的单元。

如果你看看贾斯汀树的答案，那么你可以看到叶节点有3面墙。修剪树，直到你有一个path。

如何从你的matrix构build一个graphics，并使用广度优先search，深度优先search或Dijkstrasalgorithm？

这是我最喜欢的algorithm之一….

 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

这是一个非常简单的表示来模拟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

只是一个想法。为什么不以蒙特卡罗的方式在那里扔一些机器人呢？我们称之为第一代机器人gen0。我们只保留gen0那些有连续道路的机器人：
从开始到某一点
或者 – 从某个点到最后

我们用新的随机点运行一个新的bot机器人，然后我们尝试将gen1机器人的道路与gen0机器人的道路连接起来，看看我们是否从头到尾都有连续的道路。

所以对于genn我们试图连接到机器人gen0，gen1，…，genn-1。

当然，一代人只能持续一段时间。

我不知道该algorithm的肤色是否会certificate对于小数据集是实用的。
algorithm也假设我们知道开始点和结束点。

一些好点子的想法：
http://citeseerx.ist.psu.edu/
http://arxiv.org/

在我的一个大学比较中，我遇到过类似的问题。科学。培训class。我们提出的解决scheme是跟随左手墙（右手墙也将工作）。这是一些伪代码

 While Not At End If Square To Left is open, Rotate Left Go Forward Else Rotate Right End If Wend

基本上就是这样。复杂的部分是跟踪你面对的方向，根据这个方向确定你左边的网格位置。它适用于我反对的任何testing案例。有意思的是，教授们的解决scheme是符合以下几点的：

 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 XX XX XX XXX X XXX X XXXXXXXXXXX XXXE XX XXXXXXXXXXXXXXXXXXX

S和E是开始和结束。

任何不跟随墙壁的东西，你最终不得不保留一个你已经去过的地方的清单，这样，如果有必要的话，当你陷入死胡同时，你就可以回头了，这样你就不会被抓到在一个循环中。如果你按照墙壁，没有必要跟踪你去过的地方。虽然你不会在迷宫中find最理想的path，但是你总能通过它。

如果机器人可以跟踪它的位置，那么它知道它是否曾经到过某个位置，那么深度优先search就是明显的algorithm。你可以通过一个对抗论证来表明，不可能获得比深度优先search更好的最坏情况performance。

如果你已经掌握了一些机器人无法实现的技术，那么广度优先search对于许多迷宫来说可能会更好，Dijkstra在图中find最短path的algorithm也是如此。

有很多algorithm，许多不同的设置指定哪种algorithm最好。这只是一个有趣的设置的一个想法：

让我们假设你有以下属性…

你移动一个机器人，你想尽量减less它的运动 ，而不是它的CPU使用率。
该机器人可以只检查其邻近的单元，或者沿着走廊看或看不到交叉路口。
它有GPS 。
它知道目的地的坐标。

那么你可以devise一个AI …

每次绘制地图时，都会收到有关迷宫的新信息。
计算所有未观测位置 （及其本身和目的地）之间的最小已知path长度。
可以根据周围的结构优先考虑未观察到的检查位置。（如果无法从那里到达目的地…）
可以根据方向和到目的地的距离，优先考虑未观察到的检查位置。
根据收集信息的经验，可以优先考虑未被察觉的检查职位。（它能平均看多远，走多远？）
可以优先考虑未观察到的职位来寻找可能的捷径 。（经验：有很多循环？）

与堆栈溢出的所有问题一样的答案;）

使用vi！

http://www.texteditors.org/cgi-bin/wiki.pl?Vi-Maze

看到一个文本编辑器解决了一个ascii迷宫真的很吸引人，我敢肯定，emacs的人有一个相当的..

这azkabanalgorithm也可能会帮助你， http: //journals.analysisofalgorithms.com/2011/08/efficient-maze-solving-approach-with.html

解决迷宫问题的最好方法是使用连接algorithm，如假设path压缩已完成的准线性时间algorithmunion-find。

联合查找是一个数据结构，告诉你一个集合中的两个元素是否是可传递连接的。

为了使用联合发现数据结构来解决迷宫，首先使用邻居连接性数据来build立联合发现数据结构。然后联合查找被压缩。为了确定迷宫是否可解，比较入口和出口值。如果他们有相同的价值，那么他们是连接的，迷宫是可以解决的。最后，要find一个解决scheme，首先从入口开始，检查与每个邻居相关的根。一旦find一个与当前单元格具有相同根的先前未访问的邻居，就可以访问该单元格并重复该过程。

这种方法的主要缺点是它不会告诉你通过迷宫的最短path，如果有多条path的话。

不是特别为你的情况，但我遇到了几个编程竞赛的问题，我发现李的algorithm很方便快速编码。它不是所有情况下最有效率的，但很容易出发。这是一个我砍了一个比赛。

编程理论：解决迷宫

代表和解决迷宫的形象

生成一个塔防御迷宫（最长的迷宫与有限的墙壁） – 近乎最佳的启发式？

什么是生成迷宫的好algorithm？