BFS搜索在二维网格中的Java最短路径

huangapple go评论81阅读模式
英文:

BFS search in 2D grid Java shortest path

问题

以下是您的代码的翻译部分:

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;
}

请注意,代码翻译可能会受到代码格式的影响,但逻辑和代码结构应该保持不变。

英文:

I've managed to come up with a working BFS algorithm that returns the entire traversal path, however I'm unsure of how to get the shortest path.

This is my code:

public ArrayList&lt;Node&gt; get_neighbours(Node node, Grid grid) {
ArrayList&lt;Node&gt; neighbours = new ArrayList&lt;&gt;();
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&lt;4; i++) {
int rr = node.getR() + dr[i];
int cc = node.getC() + dc[i];
if (rr &lt; 0 || cc &lt; 0) continue;
if (rr &gt;= R || cc &gt;= C) continue;
if (grid.getNodes()[rr][cc].getVal() == &quot;V&quot;) continue;
if (grid.getNodes()[rr][cc].getVal() == &quot;X&quot;) continue;
Node neighbour = grid.getNodes()[rr][cc];
neighbours.add(neighbour);
}
return neighbours;
}
public Queue&lt;Node&gt; find_path_bfs(Node start, Node end, Grid grid) {
Queue&lt;Node&gt; queue = new LinkedList&lt;&gt;();
Queue&lt;Node&gt; path = new LinkedList&lt;&gt;();
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&lt;Node&gt; adj_nodes = get_neighbours(node, grid);
for (Node n : adj_nodes) {
if (!(n.getVal() == &quot;V&quot;)) {
queue.add(n);
n.setVal(&quot;V&quot;);
}
}
}
return path;
}

I took a look at this post, that suggests saving the path to the current node as well, but I'm not sure how to implement this in Java as I would have to have a queue that stores both a Node and a List of Nodes together as one item. My Java is a little rusty, so I'm not sure if this is possible or if there is a better way.

答案1

得分: 2

您的问题是,您目前正在将Queue&lt;Node&gt; path变量用作已访问列表,而不是路径列表。您可以在前进过程中构建路径,而是存储对每个子节点父节点的引用,然后通过这些引用进行回溯。可以像这样做:

public ArrayList&lt;Node&gt; find_path_bfs(Node start, Node end, Grid grid) {

    Queue&lt;Node&gt; queue = new LinkedList&lt;&gt;();
    List&lt;Node&gt; path = new ArrayList&lt;&gt;();

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

    Map&lt;Node, Node&gt; parentMap = new HashMap&lt;&gt;();

    Node node = start;
    parentMap.put(start, null); // 起始节点没有父节点,因此我们在此结束路径重建
    while (!queue.isEmpty()) {
        node = queue.remove();

        if (node == end) break;

        ArrayList&lt;Node&gt; adj_nodes = get_neighbours(node, grid);
        for (Node n : adj_nodes) {
            if (!(n.getVal() == &quot;V&quot;)) {
                queue.add(n);
                parentMap.put(n, node); // 将当前节点标记为邻居的父节点
                n.setVal(&quot;V&quot;);
            }
        }
    }

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

    return path;
}

我将path更改为ArrayList,这样您可以在开头插入元素(因为您是从最后一个节点重建路径,而不是第一个节点)。或者,您也可以将其保留为队列,并反转元素的顺序。

英文:

Your issue is that right now you're using the Queue&lt;Node&gt; path variable as a visited list, rather than a path list. Instead of building the path as you go, store references to each child node's parent and then traverse back through this. Something like this:

public ArrayList&lt;Node&gt; find_path_bfs(Node start, Node end, Grid grid) {
Queue&lt;Node&gt; queue = new LinkedList&lt;&gt;();
List&lt;Node&gt; path = new ArrayList&lt;&gt;();
queue.add(start);
grid.mark_visited(start.getR(), start.getC());
Map&lt;Node, Node&gt; parentMap = new HashMap&lt;&gt;();
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&lt;Node&gt; adj_nodes = get_neighbours(node, grid);
for (Node n : adj_nodes) {
if (!(n.getVal() == &quot;V&quot;)) {
queue.add(n);
parentMap.put(n, node); // mark current node as parent to neighbor
n.setVal(&quot;V&quot;);
}
}
}
Node curr = node;
while (curr != null) {
path.add(0, curr);
curr = parentMap.get(curr);
}
return path;
}

I changed path to an ArrayList so that you can insert at the beginning (since you're reconstructing the path from the last node, rather than the first one). Alternatively, you could keep it as a Queue and reverse the order of the elements.

huangapple
  • 本文由 发表于 2020年4月9日 11:08:11
  • 转载请务必保留本文链接:https://go.coder-hub.com/61113331.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定