我有几个关于迷宫求解器算法的问题:C
- 递归(回溯)迷宫求解器的时间复杂度是多少?(作为矩阵中路径的数量? - 我无法计算这个数字..)
- 基于 BFS 的迷宫求解器的时间复杂度是多少?(O(n^2)?)n 是方形迷宫矩阵的维度?
- 计算迷宫中从源到目的地的所有可能路径数量的最佳算法是什么?
- 您能否提出是否以及如何使用并行计算(opecl/cuda)实现它的想法
这是我的迷宫解算器的类,它有暴力(递归)和基于 bfs 的版本。我实现了它,问题基于这个迷宫解算器实现
<p></p>
//MazeSolver.h
//#define N 5
typedef enum {BLACK,WHITE,GRAY,VISITED} color;
class MazeSolver
{
public:
MazeSolver(){}
struct Cell
{
unsigned int _x;
unsigned int _y;
Cell* _p;
Cell(unsigned int x = 0,unsigned int y = 0, Cell* p = NULL) : _x(x),_y(y),_p(p) {}
bool operator == (const Cell& c)
{
return _x == c._x && _y == c._y;
}
};
bool solveMazeBrute(color maze[][N],unsigned int n,int xS,int yS,int xD,int yD,std::list<Cell>& path);
bool solveMazeBFS(color maze[][N],unsigned int n,int xS,int yS,int xD,int yD,std::list<Cell>& path);
private:
std::queue<Cell* > _bfs;
std::vector<Cell* > _cells;
Cell* addCellBFS(color maze[][N],unsigned int n,int x,int y,Cell* p = NULL);
};
//MazeSolver.cpp
MazeSolver::Cell* MazeSolver::addCellBFS(color maze[][N],unsigned int n,int x,int y,Cell* p)
{
if (x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == WHITE)
{
Cell* c = new Cell(x,y,p);
maze [x][y] = VISITED;
_bfs.push(c);
_cells.push_back(c);
return c;
}
return NULL;
}
bool MazeSolver::solveMazeBrute(color maze[][N],unsigned int n,int xS,int yS,int xD,int yD,std::list<MazeSolver::Cell>& path)
{
bool solved = false;
if (xS < 0 || xS >= n || yS < 0 || yS >= n || maze[xS][yS] == VISITED || maze[xS][yS] == BLACK)
{
return false;
}
Cell s(xS,yS);
Cell d(xD,yD);
if (s == d)
{
path.push_front(s);
return true;
}
maze[xS][yS] = VISITED;
if (solveMazeBrute(maze,n,xS + 1,yS,xD,yD,path) ||
solveMazeBrute(maze,n,xS - 1,yS,xD,yD,path) ||
solveMazeBrute(maze,n,xS,yS + 1,xD,yD,path) ||
solveMazeBrute(maze,n,xS,yS - 1,xD,yD,path))
{
path.push_front(s);
solved = true;
}
maze[xS][yS] = WHITE;
return solved;
}
bool MazeSolver::solveMazeBFS(color maze[][N],unsigned int n,int xS,int yS,int xD,int yD,std::list<Cell>& path)
{
Cell d(xD,yD);
addCellBFS(maze,n,xS,yS);
while(!_bfs.empty())
{
Cell* cur = _bfs.front();
if (*cur == d)
{
while (cur != NULL)
{
path.push_front(*cur);
cur = cur->_p;
}
return true;
}
_bfs.pop();
addCellBFS(maze,n,cur->_x - 1,cur->_y,cur);
addCellBFS(maze,n,cur->_x + 1,cur->_y,cur);
addCellBFS(maze,n,cur->_x,cur->_y - 1,cur);
addCellBFS(maze,n,cur->_x,cur->_y + 1,cur);
}
for(std::vector<Cell*>::iterator itC= _cells.begin();itC != _cells.end();++itC)
{
maze[(*itC)->_x][(*itC)->_y] = WHITE;
delete *itC;
}
return false;
}
最佳答案
也许我们可以在 O(n) 时间内找到目标。
让我们想象一下 5X5 矩阵。 在每次迭代中,我们将向前迈出一步,我们将检查单元格是否有效并且不是迷宫的终点,并将其标记为“已访问”。
因此,我们将从第一个单元格 (0,0) 开始。在下一次迭代中,我们将检查下一层,均值 (0,1),(1,0),在下一次迭代中,我们将继续检查下一层 (0,2),(1,1),(2, 0)。等等。
所以,我们只会检查每个单元格一次!我们会在 n 复杂度中找到终点(目标)。
我错了吗?
关于c++ - 迷宫求解器的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20192406/