广度优先搜索Java中的8x8网格

Question

我要做的是计算使用最短路径到达目标需要多少动作.必须使用广度优先搜索来完成.我将8x8网格放入一个2d数组,其中填充了四个字符之一,E表示空(可以移动到这些点),B表示阻塞(无法移动到此处),R表示机器人(起始点)或G为了目标.该算法必须按顺序向上,向左,向右,然后向下检查可移动空间,我相信我已经正确完成了.检查节点后,它将其内容更改为"B".如果无法达到目标,则应返回0.

我已经改变了我的代码来实现Kshitij告诉我的内容,并且它的工作非常精彩.我太累了,看不到我在每个新数据集后都没有初始化我的队列.谢谢您的帮助!

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

Answer 1

您需要在队列中存储2件事.让我们将队列中的每个项目称为一个节点.

1. 位置(你已经存储)
2. count(从起始位置到达此位置所需的移动)

首先,将起始位置的计数分配给0.

算法的工作方式是:

1. 从队列中弹出一个节点
2. 您可以确定从刚刚弹出的节点指定的位置开始的位置.也就是说,如果您将其视为"即时创建树",那么您将确定从队列中弹出的节点的子节点
3. 您将这些子项添加到队列中.

在第3步中,将节点子节点添加到队列时,您必须确定需要添加到此节点的计数.这个计数就是这个count of the parent node (that you popped in step 1) + 1

最后,您的返回值将是与承载目标位置的节点关联的计数.

例如,让我们使用4x4网格,其中position [0,0]是开始,位置[0,3]是目的地.

S E E B
E B E E
B B B E
G E E E

最初,您的队列将是:

[{(0, 0), 0}]

其中的值()是位置,其中的第二个值{}是计数.

您从队列中弹出此节点,然后确定可以到达位置(0,1)和(1,0).所以你添加项目{(0, 1), 1}和{(1, 0), 1}队列.请注意,计数为1,因为弹出节点的计数为0,我们将其递增1.您的队列现在看起来像:

[{(0, 1), 1},  {(1, 0), 1}]

你弹出第一个元素,意识到它没有可行的孩子,所以你继续前进.

你弹出剩余的元素,并发现它给你一个你可以到达的节点,在位置(2,0).由于您弹出的节点计数为1,因此您将此新位置与count = 1 + 1 = 2配对添加到队列中.

最终,您将从队列中弹出目标节点,它的计数将为9.

编辑

如果要获取从源到目标的路径,则当前编码不会按原样运行.您需要使用计数维护一个大小为8x8的单独2D数组,而不是在节点本身中对它们进行编码.当您最终找到目的地的计数时,您使用2D计数阵列从目的地回溯到源.基本上,如果你可以通过9次移动到达目的地,你可以通过8次移动到达其中一个相邻位置.因此,您会找到计数为8且与目的地相邻的位置.你迭代地重复这个,直到你到达源头.

您描述的方法,其中向节点添加额外元素不起作用.我会留给你找出原因,因为这是作业:)