java - 迷宫路径搜索 DFS java

Question

我正在开发一个用 DFS 解决迷宫的小程序。但似乎算法在找到目标之前就停止得太早了。谁能给我提示我做错了什么？

所以墙是 1，3 是目标，我用 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

您的代码中存在一些错误。我稍微修改了您的代码，现在可以使用了。

一些关键观察结果:

1) 您的 inBounds 方法应用不正确，因为迷宫数组的维度不相等。这就是算法无法到达迷宫中的多个网格的原因。所以我删除了 inBounds 方法，修改了 Maze 构造函数以接受两个维度大小并添加了两个方法:inBoundsY 和 inBoundsX分别检查每个维度。

2) 我敢肯定，标记路径中每个访问过的网格的想法是不正确的。我添加了名为 prev 的新数组来存储路径中每个网格的前一个网格。然后我更改了您的 solve 方法并添加了 fillPath 方法以将路径中的所有网格填充 2。然后我们可以简单地打印所有迷宫并显示 relust。

新代码如下所示:

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