我认为我的 BFS 将所有有效坐标添加到列表中，而不仅仅是最短路径

Question

所以我正在研究 BFS 算法以在二维二进制迷宫中找到最短路径并以坐标的形式打印路径。代码是运行ning，但肯定有哪里出错了。

基本上，迷宫坐标有真值或假值（其中墙壁为假）。迷宫中的坐标以自定义 class 的形式给出，称为 Pos。

我的目标是找到路径，添加列表中的点（以 Pos 的形式）和 return 数组列表 ArrayList<Pos> path

这是我目前得到的结果：

import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Queue;

class Node {
    int x;
    int y;
    int d;

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

public class Problem3{

    private static final int r[] = {-1, 0, 0, 1};
    private static final int c[] = {0, -1, 1, 0};

    public static ArrayList<Pos> findPath(Pos start, Pos end, boolean maze[][]){
        ArrayList<Pos> path = new ArrayList<Pos>();
        path.add(start);

        // Get the x and y values from both start and end Pos
        // currX and currY is initially start Pos
        int currX = start.x;
        int currY = start.y;
        int endX = end.x;
        int endY = end.y;

        // Set to size of maze
        boolean[][] visited = new boolean[6][6];

        Queue<Node> q = new ArrayDeque<>();

        visited[currX][currY] = true;
        q.add(new Node(currX, currY, 0));

        int min_d = Integer.MAX_VALUE;

        while (!q.isEmpty()) {
        // Pop front node and process
            Node node = q.poll();

            currX = node.x;
            currY = node.y;
            int d = node.d;

            // If end is found, stop
            if (currX == endX && currY == endY)
            {   

                path.add(end);
                min_d = d;
                break;
            }

            // check all 4 directions from curr cell
            for (int k = 0; k < 4; k++)
            {
                if (isValid(maze, visited, currX + r[k], currY + c[k]))
                {
                    // mark as visited and add to path
                    visited[currX + r[k]][currY + c[k]] = true;
                    q.add(new Node(currX + r[k], currY + c[k], d + 1));
                    path.add(new Pos(currX, currY));
                }
            }
        }

        // If path is empty, return null. Else return path
        if (path.isEmpty()) {
            return null;
        }
        else {
            return path;
        }

    }


        // Checks if cell is traversable or visited
    private static boolean isValid(boolean maze[][], boolean visited[][], int r, int c) {
        return maze[r][c] && !visited[r][c];
    }   

}

代码是运行在另一个 class 中，它从 .in 文件中读取迷宫，然后运行在所述迷宫上使用我的算法。如果 ArrayList<Pos> path 是 returned 它将打印每个元素。如果不是，它只打印 "Not solvable"。假设我有文件 test.in 和运行 java driver < test.in:

6 6
######
#A...#
#.##.#
#.##.#
#.B..#
######

我希望输出为：

[1,1]
[2,1]
[3,1]
[4,1]
[4,2]

但这就是我得到的：

[1,1]
[1,1]
[1,1]
[1,2]
[2,1]
[1,3]
[3,1]
[1,4]
[4,1]
[2,4]
[4,2]

通过查看输出，算法似乎找到了最短路径，但每个坐标打印两次。此外，x 和 y 值翻转，起始坐标打印 3 次。非常感谢任何解决此问题的帮助。

Answer 1

你的问题是 path 永远不会重置，只会添加到。您需要以某种方式跟踪 Pos 或级别的先前位置。

试试这个：

    while (!q.isEmpty()) {
    // Pop front node and process
        Node node = q.poll();

        currX = node.x;
        currY = node.y;
        int d = node.d;
        path.removeRange(d, path.size());
        path.add(new Pos(curX, curY));

        // If end is found, stop
        if (currX == endX && currY == endY)
        {   
            min_d = d;
            break;
        }

        // check all 4 directions from curr cell
        for (int k = 0; k < 4; k++)
        {
            if (isValid(maze, visited, currX + r[k], currY + c[k]))
            {
                // mark as visited and add to path
                visited[currX + r[k]][currY + c[k]] = true;
                q.add(new Node(currX + r[k], currY + c[k], d + 1));
            }
        }
    }

更新：

class Node {
    int x;
    int y;
    Node prev;

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

...

    while (!q.isEmpty()) {
    // Pop front node and process
        Node node = q.poll();

        currX = node.x;
        currY = node.y;

        // If end is found, stop
        if (currX == endX && currY == endY)
        {   
            ArrayList<Pos> path = new ArrayList<>();
            do {
                path.add(0, new Pos(node.x,node.y));
                node = node.prev;
            } while (node != null);
            return path;
        }

        // check all 4 directions from curr cell
        for (int k = 0; k < 4; k++)
        {
            if (isValid(maze, visited, currX + r[k], currY + c[k]))
            {
                // mark as visited and add to path
                visited[currX + r[k]][currY + c[k]] = true;
                q.add(new Node(currX + r[k], currY + c[k], node));
            }
        }
    }
    return null;

我认为我的 BFS 将所有有效坐标添加到列表中，而不仅仅是最短路径

I think my BFS adds all valid coordinates to list, not just shortest path

java

breadth-first-search