Как составить список пути используя алгоритм BFS?

Question

[carabia]

Доброго времени суток!
Использую алгоритм поиска в ширину для определения кратчайшего пути в двумерном массиве. Работает корректно,
однако не могу получить путь, пройденный от источника к месту назначения в виде очереди или списка.

public class SearchMazeBFS {

    private static final int ROW = 9;
    private static final int COL = 10;
    private int[] rowNum = new int[] { -1, 0, 0, 1 };
    private int[] colNum = new int[] { 0, -1, 1, 0 };

    private static class Point {
        private Point(int row, int col) {
            this.x = row;
            this.y = col;
        }

        private int x;
        private int y;
    }

    private static class QueueNode {
        private QueueNode(Point src, int d) {
            this.pt = src;
            this.dist = d;
        }

        private Point pt;
        private int dist;
    }

    private boolean isValid(int row, int col) {
        return (((row >= 0) && (row < ROW)) && ((col >= 0) && (col < COL)));
    }

    private int BFS(int mat[][], Point src, Point dest) {
        if ((mat[src.x][src.y] == 0) || (mat[dest.x][dest.y] == 0))
            return Integer.MAX_VALUE;

        boolean[][] visited = new boolean[ROW][COL];

        visited[src.x][src.y] = true;

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

        QueueNode s = new QueueNode(src, 0);
        q.add(s);

        while (!q.isEmpty()) {
            QueueNode curr = q.peek();
            Point pt = curr.pt;

            if (pt.x == dest.x && pt.y == dest.y) {
                return curr.dist;
            }

            q.poll();

            for (int i = 0; i < 4; i++) {
                int row = pt.x + rowNum[i];
                int col = pt.y + colNum[i];

                if ((isValid(row, col) && mat[row][col] == 1)
                        && !visited[row][col]) {
                    visited[row][col] = true;
                    QueueNode adjCell = new QueueNode(new Point(row, col),
                            curr.dist + 1);
                    q.add(adjCell);
                }
            }
        }

        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        SearchMazeBFS smbfs = new SearchMazeBFS();
        int[][] mat = new int[][] {
                { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },
                { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
                { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
                { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
                { 1, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
                { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
                { 1, 1, 0, 0, 0, 0, 1, 0, 0, 1 }
        };

        Point source = new SearchMazeBFS.Point(0, 2);
        Point dest = new SearchMazeBFS.Point(2, 0);

        int dist = smbfs.BFS(mat, source, dest);

        if (dist != Integer.MAX_VALUE)
            System.out.println("Shortest Path is " + dist);
        else
            System.out.println("Shortest Path doesn't exist");
    }
}

Comments

[Satangelus]

вопрос между делом, старенький А* чем не подошел?

Answer 1

[Wataru]

Надо для каждой вершины хранить предыдущую. Запишите это значение, когда кладете вершину в очередь. Для вершины (row, col) у вас в коде предыдущая (pt.x, pt.y).

После, когда нашли расстояние до конечной вершины можно создать массив этой длины и заполнить его с конца. Нужен указатель, который указывает на конечную вершину. Двигаете его в предыдущую для текущей вершины, пока не придете в начало или известное количество шагов (уже найденное расстояние).

Comments

[carabia]

Спасибо. У меня получилось сделать обход по предыдущим вершинам следующим способом.

Добавил в класс QueueNode поле QueueNode parent, первой вершине указал null.
Новой вершине передаю предыдущую через конструктор

new QueueNode(new Point(row, col), curr.dist + 1, curr)

Когда нашел расстояние вызываю метод printPath(curr) и циклом обрабатываю каждого parent

void printPath(QueueNode queueNode) {
        while (queueNode != null) {
            System.out.println(queueNode.pt.y + " " + queueNode.pt.x);
            queueNode = queueNode.parent;
        }
    }

Не подскажете более оптимальный способ?

[Wataru]

carabia, я бы сделал 2 2D массива prev_row и prev_col. Заполнял бы их при помещении вершины в очередь.

При восстановлении вывести текущие x и y, потом перезаписать их (не забыть использовать временную переменную, чтобы не брать новое значение x и старое значение y как индексы для получения нового y).

Хотя это не сильно-то оптимальнее.

Еще, комментарий - вы выводете путь в обратном порядке. Надо заполнять массив с конца вместо вывода.

Answer 2

[Mercury13]

Вместо
boolean[][] visited = new boolean[ROW][COL];

надо сделать такое:

static final byte DIR_UNKNOWN = 0;
static final byte DIR_UP = 1;
...

byte[][] bestDirection = new boolean[ROW][COL];  // изначально заполнено DIR_UNKNOWN

for (int dir = DIR_UP; dir <= DIR_RIGHT; ++dir) {
  ...
  bestDirection[row][col] = dir;
}

Добравшись до финиша, делаем обратный ход. А именно: определяем, какой bestDirection у финиша, и если он, например, DIR_UP — смещаемся на 1 вниз. И так далее, пока не доберёмся до старта.

Если финишей много — возможно, лучше будет начинать с них, внеся их в очередь в случайном порядке. А потом, когда поиск доберётся до старта, сделать обратный ход.