英文:
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<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 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<Node> path
变量用作已访问列表,而不是路径列表。您可以在前进过程中构建路径,而是存储对每个子节点父节点的引用,然后通过这些引用进行回溯。可以像这样做:
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); // 起始节点没有父节点,因此我们在此结束路径重建
while (!queue.isEmpty()) {
node = queue.remove();
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); // 将当前节点标记为邻居的父节点
n.setVal("V");
}
}
}
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<Node> 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<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;
}
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论