Java 8x8网格上的广度优先搜索 [英] Breadth-first search on an 8x8 grid in Java
问题描述
我想做的是计算使用最短路径到达目标所需的移动次数.必须使用广度优先搜索来完成.我将8x8网格放入2d数组，其中填充了四个字符之一，E表示空白(可以移动到这些位置)，B表示被阻止(不能在此处移动)，R表示机器人(起点)，或者G为目标.该算法必须按从上到下，从左到右，然后从下到下的顺序检查可移动空间，我相信我做得正确.检查节点后，它将其内容更改为"B".如果无法达到目标，则应返回0.
What I'm trying to do is count how many moves it takes to get to the goal using the shortest path. It must be done using a breadth first search. I put the 8x8 grid into a 2d array which is filled with one of four chars, E for empty (can move into these spots), B for blocked (can't move here), R for robot (starting point), or G for goal. The algorithm had to check for movable spaces in the order up, left, right, then down, which I believe I've done correctly. After a node is checked it changes its contents to a 'B'. If the goal cannot be reached, 0 should be returned.
我已经更改了代码，以实现Kshitij告诉我的内容，并且效果很好.我实在太累了，以至于在每个新数据集大声笑之后，我没有初始化队列.感谢您的帮助！
I have changed my code to implement what Kshitij told me, and it works beautifully. I was just too tired to see that I wasn't initializing my queue after every new data set lol. Thanks for the help!
public static int bfSearch(){
Queue <int []> queue = new LinkedList <int []> ();
int [] start = {roboty,robotx,0};
queue.add(start);
while (queue.peek() != null){
int [] array = queue.remove();
if(array[0]-1 >= 0 && grid[array[0]-1][array[1]] != 'B'){
if (grid[array[0]-1][array[1]] == 'G'){
return array[2]+1;
}
else{
grid[array[0]-1][array[1]] = 'B';
int [] temp = {array[0]-1, array[1], array[2]+1};
queue.add(temp);
}
}
if(array[1]-1 >= 0 && grid[array[0]][array[1]-1] != 'B'){
if (grid[array[0]][array[1]-1] == 'G'){
return array[2]+1;
}
else{
grid[array[0]][array[1]-1] = 'B';
int [] temp = {array[0], array[1]-1, array[2]+1};
queue.add(temp);
}
}
if(array[1]+1 <= 7 && grid[array[0]][array[1]+1] != 'B'){
if (grid[array[0]][array[1]+1] == 'G'){
return array[2]+1;
}
else{
grid[array[0]][array[1]+1] = 'B';
int [] temp = {array[0], array[1]+1, array[2]+1};
queue.add(temp);
}
}
if(array[0]+1 <= 7 && grid[array[0]+1][array[1]] != 'B'){
if (grid[array[0]+1][array[1]] == 'G'){
return array[2]+1;
}
else{
grid[array[0]+1][array[1]] = 'B';
int [] temp = {array[0]+1, array[1], array[2]+1};
queue.add(temp);
}
}
}
return 0;
}
推荐答案
您需要在队列中存储2个内容.让我们将队列中的每个项目称为一个节点.
You'll need to store 2 things in your queue. Let's call each item in your queue a node.
- 职位(您已经存储)
- 计数(从起始位置到达该位置所需的动作)
您可以通过将开始位置的计数分配为0来开始.
You start off by assigning the count of your start position to 0.
算法的工作方式是:
- 您从队列中弹出一个节点
- 您确定可以从刚刚弹出的节点指定的位置去哪里.也就是说，如果您将其视为动态生成树"，则可以确定从队列中弹出的节点的子节点
- 您将这些子级添加到队列中.
在第3步中，将节点子代添加到队列时，必须确定需要添加到该节点的计数.此计数只是count of the parent node (that you popped in step 1) + 1
In your 3rd step, when you add a node child to the queue, you'd have to determine the count that needs to be added to this node. This count is simply the count of the parent node (that you popped in step 1) + 1
最后，您的返回值将是与带有目标位置的节点关联的计数.
Finally, your return value would be the count associated with the node that carries the destination position.
例如，让我们使用4x4网格工作，其中位置[0,0]是起始位置，位置[0,3]是目的地.
For instance, lets work with a 4x4 grid, where position [0,0] is the start, and position [0,3] is the destination.
S E E B
E B E E
B B B E
G E E E
最初，您的队列将是:
[{(0, 0), 0}]
其中()内的值是位置，{}内的第二个值是计数.
where the value inside the () is the position, and the second value inside the {} is the count.
您从队列中弹出此节点，并确定可以到达位置(0,1)和(1,0).因此，您将项目{(0, 1), 1}和{(1, 0), 1}添加到队列中.请注意，计数为1，因为弹出节点的计数为0，我们将其增加了1.您的队列现在如下所示:
You pop this node from your queue, and you determine that you can get to positions (0,1) and (1,0). So you add items {(0, 1), 1} and {(1, 0), 1} to the queue. Note that the count is 1 because the count of the popped node was 0 and we incremented that by 1. Your queue now looks like:
[{(0, 1), 1}, {(1, 0), 1}]
您弹出第一个元素，意识到它没有可行的子元素，因此继续前进.
You pop the first element, realize that it has no viable children, so you move on.
您弹出剩余的元素，并发现它为您提供了一个您可以到达的节点，位置为(2，0).由于您弹出的节点的计数为1，因此将与count = 1 + 1 = 2配对的这个新位置添加到队列中.
You pop the remaining element, and find out that it gives you one node you can get to, at position (2, 0). Since the node you popped has count 1, you add this new position paired with count = 1 + 1 = 2 to the queue.
最终，您将从队列中弹出目标节点，计数为9.
Eventually, you'll pop the goal node from your queue, and it's count will be 9.
修改
如果要获取从源到目标的路径，则当前的编码将无法正常使用.您需要使用计数来维护大小为8x8的单独2D数组，而不是在节点本身中对其进行编码.当您最终找到目标的计数时，您将使用2D计数数组将其从目标回溯到源.本质上，如果您能以9个动作到达目的地，则可以以8个动作到达其相邻位置之一.因此，您找到了计数为8且与目的地相邻的位置.您反复重复此过程，直到获得源代码为止.
If you want to get the path from the source to the destination, the current encoding doesn't work as is. You'd need to maintain a separate 2D array of size 8x8 with the counts instead of encoding them in the node itself. And when you finally find the count for the destination, you backtrack from the destination to the source using he 2D count array. Essentially, if you can get to the destination in 9 moves, you can get to one of its adjacent positions in 8 moves. So you find the position that has count 8 and is adjacent to the destination. You iteratively repeat this until you get to the source.
您描述的在节点上添加额外元素的方法不起作用.我将它留给您找出原因，因为这是家庭作业:)
The method you described, where you add an extra element to the nodes does not work. I'll leave it for you to find out why, since this is homework :)
这篇关于Java 8x8网格上的广度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
