https://stackoverflow.com/questions/3097556
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
解决迷宫的可能方法是什么？
我有两个想法，但我认为它们不是很优雅。
基本情况： 我们有一个矩阵，并且该矩阵中的元素以代表迷宫的方式排序，并以一种方式出现。
我的第一个想法是沿着迷宫派遣一个机器人，直到迷宫脱落。我认为这是一个非常缓慢的解决方案。
第二个通过标记为1的连续物品，检查它可以（向上，右，向下，左）选择一种方式，然后继续其路径。这甚至比第一个慢。
当然，如果我在每个路口进行多线程进行了两个机器人，但这也不是最好的方法。
需要有更好的解决方案来通过迷宫发送机器人。
编辑
首先：感谢您的好答案！
我问题的第二部分是： 如果我们有多维图，该怎么办？是否有特殊的做法，或者贾斯汀·L的答案也可以使用？
我认为这不是这种情况的最佳方法。
第三个问题：
这些迷宫求解器算法中的哪一种是/最快的？ （纯粹是假设的）
解决方案
您可以将您的迷宫视为树。
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)
每个节点是路径的连接。 d，i，j，l和o是死胡同，**是目标。当然，在您的实际树中，每个节点都有尽可能多的 三 孩子们。
您的目标现在只是找到要遍历的节点以找到饰面。任何OL'Tree搜索算法都可以做到。
看着树，只需在树的最深处就“跟踪”，很容易看到正确的解决方案：
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
请注意，由于迷宫的性质，广度优先的节点的平均值要高得多。广度优先可以通过搜索路径的队列来轻松实现，并且每次迭代都会从队列中弹出一条路径，“爆炸”，通过获取一步后可以变成一步的所有路径，并将这些新路径置于在队列结束时。没有明确的“下一级”命令来代码，而这些命令只是为了帮助理解。
实际上，有一个整体 搜索树的范围列表. 。我刚才提到了两个最简单，最简单的方式。
如果您的迷宫非常非常长，很深，并且有循环和疯狂，并且很复杂，我建议您 一种* 算法是行业标准的探索算法，将广度优先的搜索与启发式方法结合在一起……有点像“智能的广度优先搜索”。
它基本上是这样的：
- 将一条路径放在队列中（只有直接进入迷宫的路径）。一条路径具有由其当前长度 +距末端的直线距离给出的“权重”（可以通过数学计算）
- 从队列中以最低的重量弹出路径。
- 将路径“爆炸”到一步之后可能是每条路径。 （即，如果您的路径向右左右，则您的爆炸路径为rllrr和rllrl，不包括穿过墙壁的非法途径）
- 如果这些道路之一有目标，那就胜利！除此以外：
- 计算爆炸路径的权重，并将所有这些路径放回队列（不包括原始路径）
- 按重量对队列进行排序，最低。然后从步骤＃2重复
就是这样 一种*, ，我特别强调的是，它或多或少是行业标准的探索算法 全部 探路的应用，包括从地图的一个边缘移动到另一个边缘，同时避免越野路径或山脉等。 最短的距离启发式, ，这给了它“智力”。 A*是如此的通用性，因为考虑到任何问题，如果您有最短的距离启发式距离（我们很容易 - 直线），则可以应用它。
但 值得注意的是，一个*是 不是 您唯一的选择。
实际上， 树木遍历算法的Wikipedia类别 单独列出97！ （最好的仍然会在 这一页 之前链接）
对不起，长度= P（我倾向于漫步）
其他提示
存在许多迷宫传播算法：
http://en.wikipedia.org/wiki/maze_solving_algorithm
http://www.astrolog.org/labyrnth/algrithm.htm#solve
对于机器人， Tremaux的算法 看起来很有希望。
至少我发现有趣的一种有趣的方法是使用蜂窝自动机。简而言之，一个被3“壁”细胞包围的“空间”细胞变成了“壁”细胞。在最后，剩下的唯一的空间是通往出口的途径。
如果您看一下贾斯汀（Justin）的答案，那么您会看到叶子节点有3个墙壁。修剪树木直到有一条路。
如何从矩阵中构建图形并使用广度首次搜索，深度搜索或Dijkstras算法？
这是我有史以来最喜欢的算法之一。
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的机器人：
- 从起点到一定程度
或 - 从一点点到末端
我们在新的随机点中运行了一个新的机器人Gen1，然后我们尝试将Gen1的机器人的道路与Gen0的道路联系起来，看看我们是否从头到尾都能获得连续的道路。
因此，对于Genn，我们尝试与形成gen0，gen1，...，genn-1的机器人连接。
当然，一代人只能持续一定的时间。
我不知道该算法的肤色是否对小型数据集有效。
同样，该算法假设我们知道起点和终点。
我的大学中有一个类似的问题。科学。培训班。我们提出的解决方案是沿着左侧墙壁（右侧墙壁也可以工作）。这是一些伪代码
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是开始和结尾。
有了任何不遵循墙壁的东西，您最终都必须保留自己去过的地方的列表，以便在必要时可以回溯循环。如果您沿着墙壁行驶，则无需跟踪您去过的地方。尽管您不会找到迷宫中最佳的道路，但您将始终通过它。
如果机器人可以跟踪其位置，因此它知道它是否以前去过一个位置，那么深度优先搜索是显而易见的算法。您可以通过对抗性论点表明，不可能比深度优先搜索获得更好的最差性能。
如果您对机器人无法实现的技术可用，那么广度优先的搜索对于许多迷宫来说可能会更好，就像Dijkstra的算法可以找到图形中最短路径。
有很多算法，很多 不同的设置 该指定哪种算法是最好的。这只是一个有趣的环境的一个想法：
假设您有以下属性...
- 你移动机器人，你想 最小化其运动, ，不是其CPU使用情况。
- 该机器人可以仅检查其相邻的单元格或查看 走廊 要么看到或看不到横路。
- 它有 全球定位系统.
- 它知道其目的地的坐标。
然后，您可以设计一个AI ...
- 绘制地图 - 每次收到有关迷宫的新信息时。
- 计算最低已知的 小路 长度 之间 全部 未观察到的位置 （以及本身和目的地）。
- 可以优先考虑未观察的位置以进行检查 周围结构. 。 （如果无论如何都无法从那里到达目的地...）
- 可以优先考虑未观察的位置以进行检查 方向和距离 到达目的地。
- 可以优先考虑未观察的位置以进行检查 关于收集信息的经验. 。 （平均能看到多远，必须走多远？）
- 可以优先考虑未观察到的位置 找到可能的快捷方式. 。 （经验：有很多 循环?)
与堆栈跨流有关的所有问题相同；）
使用vi！
http://www.texteditors.org/cgi-bin/wiki.pl?vi-maze
看到文本编辑解决了ASCIIMAZE真是令人着迷，我敢肯定，Emacs的家伙有同等的。
解决迷宫的最佳方法是使用连通性算法，例如Union-Find，它是一种准线性时间算法，假设已完成路径压缩。
Union-Find是一个数据结构，它告诉您集合中的两个元素是否是传输的。
要使用联合获取数据结构来解决迷宫，首先使用邻居连接数据来构建联合获取数据结构。然后联盟发现被压缩。为了确定迷宫是否可以解决，比较了入口和退出值。如果它们具有相同的值，则可以连接并可以解决迷宫。最后，要找到一个解决方案，您从入口开始并检查与每个邻居相关的根。一旦找到一个与当前单元格相同的词根的先前未访问的邻居，就可以访问该单元格并重复该过程。
这种方法的主要缺点是，如果有多个路径，它不会告诉您迷宫的最短路线。
