1. 首頁
  2. 問答
  3. Java中的迷宮求解器問題

Java中的迷宮求解器問題

2014-03-06 108 views
0

現在我已經知道它停止無限重複，但它只是一遍又一遍地嘗試相同的錯誤路徑。有誰知道有辦法讓它嘗試不同的路徑嗎？Java中的迷宮求解器問題

關鍵的數字： 0是開放 1是一堵牆 2是路徑的一部分 3是迷宮結束

public class Maze{ 
    public static void main(String[] args){ 
    int[][] maze = {{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, 
     {0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1}, 
     {1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1}, 
     {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1}, 
     {1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1}, 
     {1,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1}, 
     {1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1}, 
     {1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,1}, 
     {1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1}, 
     {1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1}, 
     {1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1}, 
     {1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1}, 
     {1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1}, 
     {1,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1}, 
     {1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1}, 
     {1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1}, 
     {1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1}, 
     {1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1}, 
     {1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1}, 
     {1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1}, 
     {1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1}, 
     {1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,1}, 
     {1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1}, 
     {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1}, 
     {1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1}, 
     {1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1}, 
     {1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1}, 
     {1,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,1}, 
     {1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,1,1,1,0,1}, 
     {1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1}, 
     {1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1,0,1}, 
     {1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,1}, 
     {1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1}, 
     {1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1}, 
     {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1}}; 
    boolean[][] posCheck = new boolean[maze.length][maze[0].length]; 
    int r = 0; 
    int c = 0; 
    for(int row = 0; row < maze.length; row++){ 
     for(int col = 0; col < maze[row].length; col++){ 
     if(maze[row][col]==0){ 
      r = row; 
      c = col; 
     } 
     } 
    } 
    maze[r][c] = 3; 
    mazeSolver(1, 0, maze, posCheck); 
    } 

    public static boolean mazeSolver(int r, int c, int[][]maze, boolean[][] posCheck){ 
    posCheck[r][c] = true; 
    maze[r][c] = 2; 

    if(maze[r][c] == 3){ 
     print(maze); 
     return true; 
    } 

    if((c+1 < maze.length) && maze[r][c+1]==0 && !posCheck[r][c+1] && (mazeSolver(r, c + 1, maze, posCheck))){ 
     maze[r][c] = 2; 
     return true; 
    } 

    if((r-1 >= 0) && maze[r-1][c]==0 && !posCheck[r-1][c] && (mazeSolver(r - 1, c, maze, posCheck))){ 
     maze[r][c] = 2; 
     return true; 
    } 

    if((c-1 >= 0) && maze[r][c-1]==0 && !posCheck[r][c-1] && (mazeSolver(r, c - 1, maze, posCheck))){ 
     maze[r][c] = 2; 
     return true; 
    } 

    if((r+1 < maze.length) && maze[r+1][c]==0 && !posCheck[r+1][c] && (mazeSolver(r + 1, c, maze, posCheck))){ 
     maze[r][c] = 2; 
     return true; 
    } 

    print(maze); 
    return false; 
    } 

    public static void print(int[][] maze){ 
    for(int row = 0; row<maze.length; row++){ 
     for(int col = 0; col<maze[row].length; col++) 
     System.out.print(maze[row][col]); 
     System.out.println(); 
    } 
    } 
}

來源

2014-03-06 user3390133

+1

數字0,1,2和3是什麼意思 – stakSmashr

+4

也許你應該從一個較小的迷宮開始，讓自己工作？這樣你可以更容易地發現錯誤。 – Keppil

+0

即使有一天你得到這個有限的遞歸，我預見你會在棧上傳遞一個數組，每次遞歸調用時都會有一個數組。 –

回答

1

您需要跟蹤它的定位你有已經訪問過。一個簡單的方法是創建一個與你的迷宮大小相同的2d布爾數組，並且當你的遞歸方法首次擊中它時標記一個位置爲真。除了您的牆檢查外，您還需要添加wasVisited檢查。

來源

2014-03-06 21:41:24

3

我已將調試輸出添加到您的mazeSolver函數的每個分支。正如你所看到的，任何分支都不會被調用，因爲第三個if塊中的遞歸調用從未完成評估。因此它是一個無限遞歸，這是StackOverflowError的原因。它也表明它只是在兩種不同的價值之間來回反彈，這可能是一個問題。

您需要確定您的mazeSolver實際上在做什麼 - 爲什麼無限遞歸永遠不會展開，並對其進行更改以滿足其他條件之一。

換句話說，您需要修復您的「遞歸終止符」，並找出爲什麼除了[1,1]和[0,1]之外沒有其他值被傳遞。

public static boolean mazeSolver(int r, int c, int[][] maze){ 
System.out.println("mazeSolver(" + r + ", " + c + ", maze)"); 

    if(maze[r][c] == 3) { 
System.out.println(" Equals 3 -- return true"); 
     return true; 
    } else if((c+1 < maze.length) && maze[r][c+1]==0 && (mazeSolver(r, c + 1, maze))) { 
     maze[r][c] = 2; 
System.out.println(" Set to 2 (a) -- return true"); 
     return true; 
    } else if((r-1 >= 0) && maze[r-1][c]==0 && (mazeSolver(r - 1, c, maze))) { 
     maze[r][c] = 2; 
System.out.println(" Set to 2 (b) -- return true"); 
     return true; 
    } 

System.out.println(" Between first and second if-block"); 


    if((c-1 >= 0 && maze[r][c-1]==0) && (mazeSolver(r, c - 1, maze))) { 
     maze[r][c] = 2; 
System.out.println(" Set to 2 (c) -- return true"); 
     return true; 
    } 

System.out.println(" Between second and third if-block"); 

    if((r+1 < maze.length) && maze[r+1][c]==0 && (mazeSolver(r + 1, c, maze))){ 
     maze[r][c] = 2; 
System.out.println(" Set to 2 (d) -- return true"); 
     return true; 
    } 

System.out.println(" return false"); 
    return false; 
}

}

輸出：

[R:\jeffy\programming\sandbox\xbnjava]java Maze 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block

...等等等等...

mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
mazeSolver(1, 0, maze) 
mazeSolver(1, 1, maze) 
Between first and second if-block 
Exception in thread "main" java.lang.StackOverflowError 
     at sun.nio.cs.SingleByte.withResult(Unknown Source) 
     at sun.nio.cs.SingleByte.access$000(Unknown Source) 
     at sun.nio.cs.SingleByte$Encoder.encodeArrayLoop(Unknown Source) 
     at sun.nio.cs.SingleByte$Encoder.encodeLoop(Unknown Source) 
     at java.nio.charset.CharsetEncoder.encode(Unknown Source) 
     at sun.nio.cs.StreamEncoder.implWrite(Unknown Source) 
     at sun.nio.cs.StreamEncoder.write(Unknown Source) 
     at java.io.OutputStreamWriter.write(Unknown Source) 
     at java.io.BufferedWriter.flushBuffer(Unknown Source) 
     at java.io.PrintStream.write(Unknown Source) 
     at java.io.PrintStream.print(Unknown Source) 
     at java.io.PrintStream.println(Unknown Source) 
     at Maze.mazeSolver(Maze.java:64) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
     at Maze.mazeSolver(Maze.java:82) 
     at Maze.mazeSolver(Maze.java:69) 
    at Maze.mazeSolver(Maze.java:82)

...等等等等...

來源

2014-03-06 21:55:14 aliteralmind

+0

我已經修復了無限遞歸，但現在它只是一直經歷同樣的錯誤路徑 – user3390133

+0

所以做一些事情不同。添加一些更相關的調試來幫助你。添加一些*條件*調試，例如'if（someConditionIsTrue）{System.out.println（「some related information」）; }'所以你不會被輸出壓倒。你也可以說'java maze> temp.txt'，這樣你就可以在文本編輯器中分析輸出。試一試！ – aliteralmind

1

http://www.astrolog.org/labyrnth/algrithm.htm http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap

我最近一直在編寫一個迷宮應用程序，發現上述網站在理解這些概念方面非常有用。我創建了類來代表Maze，Cell &邊緣的圖形作爲Cells（節點）&邊緣的集合。有一次，我還遇到了一個問題，沒有完成搜索路徑&需要更好地管理哪些單元已被訪問過。我反覆回到死衚衕，因爲我的算法沒有跟蹤Cell已經被訪問過。這聽起來和你的問題非常相似。

來源

2014-03-06 23:01:39 onesixtyfourth

相關問題

 相關問題