BFS поиск в 2D сетке Java кратчайший путь - PullRequest
Новая
       7

BFS поиск в 2D сетке Java кратчайший путь

0 голосов
/ 09 апреля 2020

Мне удалось придумать работающий алгоритм BFS, который возвращает весь путь обхода, однако я не уверен, как получить кратчайший путь.

Это мой code: 

public ArrayList<Node> get_neighbours(Node node, Grid grid) {

        ArrayList<Node> neighbours = new ArrayList<>();

        int R = grid.getRl();
        int C = grid.getCl();

        int[] dr = new int[]{-1, +1, 0, 0};
        int[] dc = new int[]{0, 0, +1, -1};

        for (int i=0; i<4; i++) {
            int rr = node.getR() + dr[i];
            int cc = node.getC() + dc[i];

            if (rr < 0 || cc < 0) continue;
            if (rr >= R || cc >= C) continue;

            if (grid.getNodes()[rr][cc].getVal() == "V") continue;
            if (grid.getNodes()[rr][cc].getVal() == "X") continue;

            Node neighbour = grid.getNodes()[rr][cc];
            neighbours.add(neighbour);
        }

        return neighbours;

    }

    public Queue<Node> find_path_bfs(Node start, Node end, Grid grid) {

        Queue<Node> queue = new LinkedList<>();
        Queue<Node> path = new LinkedList<>();

        queue.add(start);
        grid.mark_visited(start.getR(), start.getC());

        while (!queue.isEmpty()) {
            Node node = queue.remove();
            path.add(node);

            if (node == end) break;

            ArrayList<Node> adj_nodes = get_neighbours(node, grid);
            for (Node n : adj_nodes) {
                if (!(n.getVal() == "V")) {
                    queue.add(n);
                    n.setVal("V");
                }
            }
        }
        return path;
    }

Я посмотрел на эту запись , в которой также предлагается сохранить путь к текущему узлу, но я не уверен, как реализовать это в Java поскольку у меня должна быть очередь, в которой и узел, и список узлов хранятся вместе как один элемент. Мой Java немного ржавый, поэтому я не уверен, возможно ли это или есть лучший способ.

1 Ответ

0 голосов
/ 09 апреля 2020

Ваша проблема в том, что сейчас вы используете переменную Queue<Node> path в качестве списка посещений, а не списка путей. Вместо того чтобы строить путь, как вы go, сохраняйте ссылки на родительский узел каждого дочернего узла, а затем проходите через это. Примерно так: 

public ArrayList<Node> find_path_bfs(Node start, Node end, Grid grid) {

    Queue<Node> queue = new LinkedList<>();
    List<Node> path = new ArrayList<>();

    queue.add(start);
    grid.mark_visited(start.getR(), start.getC());

    Map<Node, Node> parentMap = new HashMap<>();

    Node node = start;
    parentMap.put(start, null); // start node has no parent, so we end path reconstruction here
    while (!queue.isEmpty()) {
        node = queue.remove();
        // path.add(node);

        if (node == end) break;

        ArrayList<Node> adj_nodes = get_neighbours(node, grid);
        for (Node n : adj_nodes) {
            if (!(n.getVal() == "V")) {
                queue.add(n);
                parentMap.put(n, node); // mark current node as parent to neighbor
                n.setVal("V");
            }
        }
    }

    Node curr = node;
    while (curr != null) {
        path.add(0, curr);
        curr = parentMap.get(curr);
    }

    return path;
}

Я изменил путь на ArrayList, чтобы вы могли вставлять его в начале (так как вы восстанавливаете путь из последнего узла, а не из первого). В качестве альтернативы, вы можете сохранить его как очередь и изменить порядок элементов в обратном порядке.

...