Я думаю, что мой BFS добавляет все действительные координаты в список, а не только кратчайший путь - PullRequest
Новая
       12

Я думаю, что мой BFS добавляет все действительные координаты в список, а не только кратчайший путь

0 голосов
/ 04 ноября 2019

Итак, я работаю над алгоритмом BFS, чтобы найти кратчайший путь в 2-мерном двоичном лабиринте и распечатать путь в виде координат. Код выполняется, но где-то должны быть некоторые ошибки.

В основном, координаты лабиринта имеют либо истинные, либо ложные значения (где стены ложные). Координаты в лабиринте даны в виде пользовательского класса с именем Pos.

Моя цель - найти путь, добавить точки в список (в форме Pos) и вернуть список массивов 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];
    }   

}

Код запускается в другом классе, который читает лабиринт из файла .in и затем запускает мой алгоритм на указанном лабиринте. Если возвращается ArrayList<Pos> path, он напечатает каждый элемент. Если нет, то просто печатается «Не решаемо». Допустим, у меня есть файл 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 раза. Любая помощь с устранением неполадок, это очень ценится.

1 Ответ

1 голос
/ 04 ноября 2019

Ваша проблема в том, что 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;
...