迷宮路徑搜索DFS java

Question

我正在開發一個小程序來解決由DFS發佈的迷宮。但似乎算法在發現它的目標之前就停止了太早。任何人都可以給我一個暗示我做錯了什麼？

SO壁均爲1，3是目標，以及i標記用2

代碼的路徑：

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Stack; 

public class Maze { 

    private final int size; 
    private final int[][] maze; 

    Maze(int[][] maze){ 
     this.size = maze.length; 
     this.maze = maze; 
    } 

    private boolean inBounds(int number){ 
     return number >= 0 && number < this.size; 
    } 

    /* 
    * This one has no information where the end point is so it uses DFS to find a path to the 
    * the end point. The end point must be marked by a 3. 
    * 
    * procedure DFS-iterative(G,v): 
    * let S be a stack 
    * S.push(v) 
    * while S is not empty 
    *  v = S.pop() 
    *  if v is not labeled as discovered: 
    *   label v as discovered 
    *   for all edges from v to w in G.adjacentEdges(v) do 
    *    S.push(w) 
    * 
    * 
    */ 
    public void solve(Node start){ 
     Stack<Node> stack = new Stack<Node>(); 
     HashSet<Node> visited = new HashSet<Node>(); 
     stack.push(start); 
     while(!stack.isEmpty()){ 
      Node tmp = stack.pop(); 
      this.maze[tmp.getY()][tmp.getX()] = 2; 
      if(!visited.contains(tmp)){ 
       visited.add(tmp); 
       for(Node n : this.getAdjacentEdges(tmp)) 
        stack.push(n); 
      } 

     } 
    } 


    private List<Node> getAdjacentEdges(Node tmp) { 
     List<Node> neighbours = new ArrayList<Node>(); 
     if(this.inBounds(tmp.getX()+1)){ 
      if(this.maze[tmp.getY()][tmp.getX()+1] != 1){ 
       neighbours.add(new Node(tmp.getX()+1, tmp.getY())); 
      } 
     } 
     if(this.inBounds(tmp.getX()-1)){ 
      if(this.maze[tmp.getY()][tmp.getX()-1] != 1){ 
       neighbours.add(new Node(tmp.getX()-1, tmp.getY())); 
      } 
     } 
     if(this.inBounds(tmp.getY()+1)){ 
      if(this.maze[tmp.getY()+1][tmp.getX()] != 1){ 
       neighbours.add(new Node(tmp.getX(), tmp.getY()+1)); 
      } 
     } 
     if(this.inBounds(tmp.getY()-1)){ 
      if(this.maze[tmp.getY()-1][tmp.getX()] != 1){ 
       neighbours.add(new Node(tmp.getX(), tmp.getY()-1)); 
      } 
     } 
     return neighbours; 
    } 


    public static void main(String args[]){ 
     int [][] maze = 
      { {1,1,1,1,1,1,1,1,1,1,1,1,1}, 
       {1,0,1,0,1,0,1,0,0,0,0,0,1}, 
       {1,0,1,0,0,0,1,0,1,1,1,0,1}, 
       {1,0,0,0,1,1,1,0,0,0,0,0,1}, 
       {1,0,1,0,0,0,0,0,1,1,1,0,1}, 
       {1,0,1,0,1,1,1,0,1,0,0,0,1}, 
       {1,0,1,0,1,0,0,0,1,1,1,0,1}, 
       {1,0,1,0,1,1,1,0,1,0,1,0,1}, 
       {1,0,0,0,0,0,0,0,0,0,1,3,1}, 
       {1,1,1,1,1,1,1,1,1,1,1,1,1} 

      }; 
     Maze m = new Maze(maze); 
     m.solve(new Node(1,1)); 
     for(int i = 0; i < maze.length; i++){ 
      for(int j = 0; j < maze[i].length; j++){ 
       System.out.print(" " + maze[i][j] + " "); 
      } 
      System.out.println(); 
     } 
    } 
} 

節點類：

public class Node { 
    private int x; 
    private int y; 


    Node(int x, int y){ 
     this.x = x; 
     this.y = y; 
    } 


    int getX(){ 
     return this.x; 
    } 

    int getY(){ 
     return this.y; 
    } 

    @Override 
    public int hashCode(){ 
     return this.getX()+this.getY()+31; 
    } 

    @Override 
    public boolean equals(Object obj){ 
     if (obj == this) return true; 
     if (obj == null || obj.getClass() != this.getClass()) return false; 
     Node tmp = (Node) obj; 
     return tmp.getX() == this.getX() && this.getY() == tmp.getY(); 
    } 

    @Override 
    public String toString(){ 
     return "x: " + this.getX() + " y: " + this.getY(); 
    } 
} 

Answer 1

有很你的代碼中有一些bug。我稍微修改了你的代碼，現在它工作。

一些關鍵的觀測：因爲迷宮陣列的尺寸是不相等的

1）你的inBounds方法不正確地應用。這就是算法在迷宮中沒有達到多個網格的原因。因此，我刪除了inBounds方法，修改了Maze構造函數以接受兩個尺寸大小並添加了兩個方法：inBoundsY和inBoundsX以單獨檢查每個維度。

2）我確定，將每個訪問過的網格標記爲位於路徑中的想法是不正確的。我添加了一個名爲prev的新數組來存儲路徑中每個網格的先前網格。然後我改變了你的solve方法並添加了fillPath方法來填充路徑中的所有網格，然後我們可以簡單地打印所有的迷宮並顯示重新渲染。

新的代碼看起來是這樣的：

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Stack; 

public class Maze { 

    private int[][] maze; 
    // previous grids array 
    private Node[][] prev; 

    private int sizeX; 
    private int sizeY; 

    private Node lastNode; 

    Maze(int[][] maze, int sizeY, int sizeX) { 
     this.maze = maze; 
     this.sizeY = sizeY; 
     this.sizeX = sizeX; 

     prev = new Node[sizeY][sizeX]; 
    } 

    private boolean inBoundsX(int number){ 
     return number >= 0 && number < sizeX; 
    } 

    private boolean inBoundsY(int number){ 
     return number >= 0 && number < sizeY; 
    } 

    public void solve(Node start){ 
     Stack<Node> stack = new Stack<>(); 
     HashSet<Node> visited = new HashSet<>(); 

     stack.push(start); 

     while(!stack.isEmpty()) { 
      Node tmp = stack.pop(); 
      visited.add(tmp); 

      if (maze[tmp.getY()][tmp.getX()] == 3) { 
       lastNode = tmp; 
       break; 
      } 

      for(Node node : this.getAdjacentEdges(tmp)) { 
       if (!visited.contains(node)) { 
        stack.push(node); 
        prev[node.getY()][node.getX()] = tmp; 
       } 
      } 
     } 
    } 

    public void fillPath() { 
     if (lastNode == null) { 
      System.out.println("No path in maze"); 
     } else { 
      // assume, that start point and end point are different 
      for (;;) { 
       lastNode = prev[lastNode.getY()][lastNode.getX()]; 

       // There's no previous node for start point, so we can break 
       if (lastNode == null) { 
        break; 
       } 

       maze[lastNode.getY()][lastNode.getX()] = 2; 

      } 
     } 
    } 

    private List<Node> getAdjacentEdges(Node tmp) { 
     List<Node> neighbours = new ArrayList<Node>(); 
     if(this.inBoundsX(tmp.getX()+1)){ 
      if(this.maze[tmp.getY()][tmp.getX()+1] != 1){ 
       neighbours.add(new Node(tmp.getX()+1, tmp.getY())); 
      } 
     } 
     if(this.inBoundsX(tmp.getX()-1)){ 
      if(this.maze[tmp.getY()][tmp.getX()-1] != 1){ 
       neighbours.add(new Node(tmp.getX()-1, tmp.getY())); 
      } 
     } 
     if(this.inBoundsY(tmp.getY()+1)){ 
      if(this.maze[tmp.getY()+1][tmp.getX()] != 1){ 
       neighbours.add(new Node(tmp.getX(), tmp.getY()+1)); 
      } 
     } 
     if(this.inBoundsY(tmp.getY()-1)){ 
      if(this.maze[tmp.getY()-1][tmp.getX()] != 1){ 
       neighbours.add(new Node(tmp.getX(), tmp.getY()-1)); 
      } 
     } 
     return neighbours; 
    } 


    public static void main(String args[]){ 
     int [][] maze = 
       { {1,1,1,1,1,1,1,1,1,1,1,1,1}, 
        {1,0,1,0,1,0,1,0,0,0,0,0,1}, 
        {1,0,1,0,0,0,1,0,1,1,1,0,1}, 
        {1,0,0,0,1,1,1,0,0,0,0,0,1}, 
        {1,0,1,0,0,0,0,0,1,1,1,0,1}, 
        {1,0,1,0,1,1,1,0,1,0,0,0,1}, 
        {1,0,1,0,1,0,0,0,1,1,1,0,1}, 
        {1,0,1,0,1,1,1,0,1,0,1,0,1}, 
        {1,0,0,0,0,0,0,0,0,0,1,3,1}, 
        {1,1,1,1,1,1,1,1,1,1,1,1,1} 

       }; 

     // Create maze with certain dimensions 
     Maze m = new Maze(maze, 10, 13); 

     m.solve(new Node(1,1)); 

     m.fillPath(); 

     for(int i = 0; i < maze.length; i++){ 
      for(int j = 0; j < maze[i].length; j++){ 
       System.out.print(" " + maze[i][j] + " "); 
      } 
      System.out.println(); 
     } 
    } 
} 

結果將是：

1 1 1 1 1 1 1 1 1 1 1 1 1 
1 2 1 0 1 0 1 2 2 2 2 2 1 
1 2 1 0 0 0 1 2 1 1 1 2 1 
1 2 0 0 1 1 1 2 0 0 0 2 1 
1 2 1 2 2 2 2 2 1 1 1 2 1 
1 2 1 2 1 1 1 0 1 0 0 2 1 
1 2 1 2 1 0 0 0 1 1 1 2 1 
1 2 1 2 1 1 1 0 1 0 1 2 1 
1 2 2 2 0 0 0 0 0 0 1 3 1 
1 1 1 1 1 1 1 1 1 1 1 1 1