迷宮求解複雜

Question

我對迷宮幾夭的問題 - 求解算法：C

1. 什麼是遞歸（回溯）迷宮求解的時間複雜度（如在矩陣路徑的量 - 我能？ ）這個數字就是數字..）
2. 什麼是基於BFS的迷宮解算器的時間複雜度？（O（n^2）？）n是平方迷宮矩陣的維數？
3. 計算迷宮中從源到目的地的所有可能路徑數的最佳算法是什麼？
4. 你能提出這個想法是否以及如何在它使用並行計算（opecl/CUDA）

這裏是我的迷宮解算器，它具有強力（遞歸）類基於version.I BFS實現和實現它和問題是基於這個迷宮求解器的實現

 

//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; 
    } 

Answer 1

也許我們可以在O（n）中找到目標。

讓我們來想象5X5矩陣。 在每一次迭代中，我們將前進一步，我們將檢查單元是否有效，而不是迷宮的終點，並將其標記爲「已訪問」。

所以，我們將從第一個單元格（0,0）開始。在下一次迭代中，我們將檢查下一層，平均值（0,1），（1,0），在下一次迭代中我們將繼續檢查下一層（0,2），（1,1），（2， 0）。等等。

所以，我們只檢查一次每個單元格！我們會在n個複雜度中找到最終目標。

我錯了嗎？