遞歸迷宮求解方法

Question

我正在研究遞歸求解由單元組成的方法。

該方法只是不工作。任何建議，將不勝感激。

參數：srow =起始x值。 scol =凝視y值erow =結束 x值。 ecol =結束y值。 L =解決路徑的鏈接列表指向

代碼：

private InputGraphicMaze2 maze; 
private int R, C; 

//code added by me 
private String[] [] cell; //an array to keep track of cells that are proven dead ends. 


public YourMazeWithPath2() 
{  
    // an R rows x C columns maze 
    maze = new InputGraphicMaze2(); 

    R=maze.Rows(); C=maze.Cols(); 

    //code added by me 
    cell = new String[R+2][C+2]; 
    for (int i=0; i<R+2; i++) { 
     for (int k=0; k<C+2; k++) { 
      cell[i][k] = "no"; 
     } 
    } 

    // Path holds the cells of the path 
    LinkedList<Point> Path = new LinkedList<Point>(); 
    // Create the path 
    CreatePath(maze, 1, 1, R, C, Path); 
    // show the path in the maze 
    maze.showPath(Path); 
} 

private void setDead(int x, int y) { 
    cell[x][y] = "dead"; 
} 

private void setVisited(int x, int y) { 
    cell[x][y] = "visited"; 
} 

public boolean CreatePath(InputGraphicMaze2 maze,  
    int srow, int scol, int erow, int ecol, LinkedList<Point> L) 
{ 

    int x = srow; 
    int y = scol; 
    Point p = new Point(x, y); 

    if ((x<1) || (y<1) || (x>R) || (y>C)) { 
     return false; //cell is out of bounds 
    } 

    else if ((x==R) && (y==C)) { 
     return true; // cell is the exit cell 
    } 

    else { 
     if ((maze.can_go(x, y, 'U')) && (x!=1) && (!cell[x-1][y].equals("dead")) && (!cell[x-1][y].equals("visited"))) { 
      L.addLast(p); 
      setVisited(x,y); 
      CreatePath(maze, x-1, y, R, C, L); 
      return false; 
     } 
     else if ((maze.can_go(x, y, 'R')) && (y!=C) && (!cell[x][y+1].equals("dead")) && (!cell[x][y+1].equals("visited"))) { 
      L.addLast(p); 
      setVisited(x, y); 
      CreatePath(maze, x, y+1, R, C, L); 
      return false; 
     } 
     else if ((maze.can_go(x, y, 'D')) && (x!=R) && (!cell[x+1][y].equals("dead")) && (!cell[x+1][y].equals("visited"))) { 
      L.addLast(p); 
      setVisited(x, y); 
      CreatePath(maze, x+1, y, R, C, L); 
      return false; 
     } 
     else if ((maze.can_go(x, y, 'L')) && (y!=1) && (!cell[x][y-1].equals("dead")) && (!cell[x][y-1].equals("visited"))) { 
      L.addLast(p); 
      setVisited(x, y); 
      CreatePath(maze, x, y-1, R, C, L); 
      return false; 
     } 
     else { 
      if ((maze.can_go(x, y, 'U')) && (x!=1) && (cell[x][y-1].equals("visited"))) { 
       setDead(x, y); 
       if (L.contains(p)) 
        L.remove(p); 
       CreatePath(maze, x-1, y, R, C, L); 
       return false; 
      } 
      else if ((maze.can_go(x, y, 'R')) && (y!=C) && (cell[x][y+1].equals("visited"))) { 
       setDead(x, y); 
       if (L.contains(p)) 
        L.remove(p); 
       CreatePath(maze, x, y+1, R, C, L); 
       return false; 
      } 
      else if ((maze.can_go(x, y, 'D')) && (x!=R) && (cell[x+1][y].equals("visited"))) { 
       setDead(x, y); 
       if (L.contains(p)) 
        L.remove(p); 
       CreatePath(maze, x+1, y, R, C, L); 
       return false; 
      } 
      else if ((maze.can_go(x, y, 'D')) && (y!=1) && (cell[x][y-1].equals("visited"))) { 
       setDead(x, y); 
       if (L.contains(p)) 
        L.remove(p); 
       CreatePath(maze, x, y-1, R, C, L); 
       return false; 
      } 
      else { 
       return false; 
      } 
     } 
    } 



} 

Answer 1

這是一個基本圖形的穿越問題。我建議你使用dfs而不是bfs。幾乎任何關於算法和數據結構的教科書都會有實現。

您只需調整遞歸部分即可在您達到目標後停止搜索。另一方面，如果你正在尋找所有的目標路徑，那就去做所有的路徑，然後從那裏開始。對於提示，您可以查看Bellman-Ford或Dijkstra的算法（http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm）。再次，任何好的教科書上都有關於圖表的章節。

Answer 2

從Another similar thread，只是在一個不太冗長的語言看到的問題，看看 用戶@Sergey魯堅科

var map = [ 
    [1,1,0,0,0,0,0,0], 
    [0,1,1,0,0,0,0,0], 
    [1,1,1,0,0,0,0,0], 
    [1,0,0,1,1,1,1,1], 
    [1,1,0,0,1,0,0,1], 
    [0,1,1,0,1,0,0,1], 
    [1,1,1,0,1,0,0,1], 
    [1,0,0,0,1,1,1,1] 
] 

var goalx = 7; 
var goaly = 7; 

function findpath(x,y){ 

    // illegal move check 
    if (x < 0 || x > (map[0].length -1) || y < 0 || y > (map.length - 1)) return false; //if it is outside of map 
    if (map[y][x]==0) return false; //it is not open 

    // end move check 
    if (x== goalx && y== goaly){ 
     console.log('Reached goal at: ' + x + ':' + y); 
     return true; // if it is the goal (exit point) 
    } 

    if(map[y][x] == 9 || map[y][x] == 8) 
     return false; 

    console.log('Im here at: ' + x + ':' + y); 

    map[y][x]=9; //here marking x,y position as part of solution path outlined by "9" 

    if(findpath(x+1,y)) 
     return true;  
    if(findpath(x,y+1)) 
     return true;  
    if(findpath(x,y-1)) 
     return true; 
    if(findpath(x-1,y)) 
     return true;      

    return false; 
}; 

findpath(0, 0); 

JSfiddle

沒錯使這個小小的JS遞歸迷宮求解。它的小巧，簡單，天真，缺乏，但它，遞歸和它的作品！另外，你可以清楚地看到許多迷宮遍歷算法的通用部分。

對於更嚴重的閱讀，this page有優秀深入但不科學論文有關許多遊戲相關算法的教程。

有一些相關的問題的一種算法購物時回答：

需要什麼解決辦法嗎？

需要每個解決方案嗎？

需要最快的？

什麼是迷宮的地形？網格？一張圖？

想要在未來實現運動成本？

想要實施啓發式選擇最佳路線？

最後，如果您還沒有遇到它，請檢查*算法。很受歡迎。

玩得開心！